Olympiad problems

2023 Indonesia TST, 1

Find all positive integers $n>2$ such that $$ n! \mid \prod_{ p<q\le n, p,q \, \text{primes}} (p+q)$$

1969 IMO Shortlist, 19

Tags: number theory , relatively prime , periodic sequence , divisibility

$(FRA 2)$ Let $n$ be an integer that is not divisible by any square greater than $1.$ Denote by $x_m$ the last digit of the number $x^m$ in the number system with base $n.$ For which integers $x$ is it possible for $x_m$ to be $0$? Prove that the sequence $x_m$ is periodic with period $t$ independent of $x.$ For which $x$ do we have $x_t = 1$. Prove that if $m$ and $x$ are relatively prime, then $0_m, 1_m, . . . , (n-1)_m$ are different numbers. Find the minimal period $t$ in terms of $n$. If n does not meet the given condition, prove that it is possible to have $x_m = 0 \neq x_1$ and that the sequence is periodic starting only from some number $k > 1.$

2023 Ukraine National Mathematical Olympiad, 11.1

Tags: number theory , divisibility

Set $M$ contains $n \ge 2$ positive integers. It's known that for any two different $a, b \in M$, $a^2+1$ is divisible by $b$. What is the largest possible value of $n$? [i]Proposed by Oleksiy Masalitin[/i]

2024 Kyiv City MO Round 1, Problem 3

Tags: game , number theory , combinatorics , divisibility

Let $n>1$ be a given positive integer. Petro and Vasyl play the following game. They take turns making moves and Petro goes first. In one turn, a player chooses one of the numbers from $1$ to $n$ that wasn't selected before and writes it on the board. The first player after whose turn the product of the numbers on the board will be divisible by $n$ loses. Who wins if every player wants to win? Find answer for each $n>1$. [i]Proposed by Mykhailo Shtandenko, Anton Trygub[/i]

2021 Science ON Seniors, 1

Tags: algebra , number theory , divisibility

Find all sequences of positive integers $(a_n)_{n\ge 1}$ which satisfy $$a_{n+2}(a_{n+1}-1)=a_n(a_{n+1}+1)$$ for all $n\in \mathbb{Z}_{\ge 1}$. [i](Bogdan Blaga)[/i]

2015 IMO Shortlist, N3

Tags: number theory , divisibility

Let $m$ and $n$ be positive integers such that $m>n$. Define $x_k=\frac{m+k}{n+k}$ for $k=1,2,\ldots,n+1$. Prove that if all the numbers $x_1,x_2,\ldots,x_{n+1}$ are integers, then $x_1x_2\ldots x_{n+1}-1$ is divisible by an odd prime.

1984 IMO Longlists, 43

Tags: number theory , equation , divisibility , power of 2

Let $a,b,c,d$ be odd integers such that $0<a<b<c<d$ and $ad=bc$. Prove that if $a+d=2^k$ and $b+c=2^m$ for some integers $k$ and $m$, then $a=1$.

2010 Bosnia And Herzegovina - Regional Olympiad, 3

Tags: number theory , divisibility

If $a$ and $b$ are positive integers such that $ab \mid a^2+b^2$ prove that $a=b$

2023 4th Memorial "Aleksandar Blazhevski-Cane", P6

Tags: number theory , divisibility , positive integer , function

Denote by $\mathbb{N}$ the set of positive integers. Find all functions $f:\mathbb{N} \rightarrow \mathbb{N}$ such that: [b]•[/b] For all positive integers $a> 2023^{2023}$ it holds that $f(a) \leq a$. [b]•[/b] $\frac{a^2f(b)+b^2f(a)}{f(a)+f(b)}$ is a positive integer for all $a,b \in \mathbb{N}$. [i]Proposed by Nikola Velov[/i]

2011 N.N. Mihăileanu Individual, 1

Tags: number theory , divisibility

[b]a)[/b] Prove that $ 4040100 $ divides $ 2009\cdot 2011^{2011}+1. $ [i]Gabriel Iorgulescu[/i] [b]b)[/b] Let be three natural numbers $ x,y,z $ with the property that $ (1+\sqrt 2)^x=y^2+2z^2+2yz\sqrt 2. $ Show that $ x $ is even. [i]Marius Cavachi[/i]

2016 Middle European Mathematical Olympiad, 4

Tags: functional equation , function , divisibility , algebra , number theory

Find all $f : \mathbb{N} \to \mathbb{N} $ such that $f(a) + f(b)$ divides $2(a + b - 1)$ for all $a, b \in \mathbb{N}$. Remark: $\mathbb{N} = \{ 1, 2, 3, \ldots \} $ denotes the set of the positive integers.

1998 IMO, 4

Tags: number theory , divisibility , polynomial

Determine all pairs $(x,y)$ of positive integers such that $x^{2}y+x+y$ is divisible by $xy^{2}+y+7$.

2014 Bosnia And Herzegovina - Regional Olympiad, 4

Tags: combinatorics , divisibility

How namy subsets with $3$ elements of set $S=\{1,2,3,...,19,20\}$ exist, such that their product is divisible by $4$.

2021 Azerbaijan IMO TST, 1

Tags: number theory , sequence , divisibility

Given a positive integer $k$ show that there exists a prime $p$ such that one can choose distinct integers $a_1,a_2\cdots, a_{k+3} \in \{1, 2, \cdots ,p-1\}$ such that p divides $a_ia_{i+1}a_{i+2}a_{i+3}-i$ for all $i= 1, 2, \cdots, k$. [i]South Africa [/i]

2007 IMO Shortlist, 5

Tags: function , modular arithmetic , number theory , divisibility

Find all surjective functions $ f: \mathbb{N} \to \mathbb{N}$ such that for every $ m,n \in \mathbb{N}$ and every prime $ p,$ the number $ f(m + n)$ is divisible by $ p$ if and only if $ f(m) + f(n)$ is divisible by $ p$. [i]Author: Mohsen Jamaali and Nima Ahmadi Pour Anari, Iran[/i]

1966 IMO Shortlist, 42

Tags: sequence , divisibility , number theory

Given a finite sequence of integers $a_{1},$ $a_{2},$ $...,$ $a_{n}$ for $n\geq 2.$ Show that there exists a subsequence $a_{k_{1}},$ $a_{k_{2}},$ $...,$ $a_{k_{m}},$ where $1\leq k_{1}\leq k_{2}\leq...\leq k_{m}\leq n,$ such that the number $a_{k_{1}}^{2}+a_{k_{2}}^{2}+...+a_{k_{m}}^{2}$ is divisible by $n.$ [b]Note by Darij:[/b] Of course, the $1\leq k_{1}\leq k_{2}\leq ...\leq k_{m}\leq n$ should be understood as $1\leq k_{1}<k_{2}<...<k_{m}\leq n;$ else, we could take $m=n$ and $k_{1}=k_{2}=...=k_{m},$ so that the number $a_{k_{1}}^{2}+a_{k_{2}}^{2}+...+a_{k_{m}}^{2}=n^{2}a_{k_{1}}^{2}$ will surely be divisible by $n.$

2024 Brazil Cono Sur TST, 3

Tags: hensel s lemma , chinese remainder theorem , divisibility , quadratic residue , number theory

Find all positive integers $m$ that have some multiple of the form $x^2+5y^2+2024$, with $x$ and $y$ integers.

2024 Kyiv City MO Round 2, Problem 2

Tags: number theory , divisibility

Mykhailo wants to arrange all positive integers from $1$ to $2024$ in a circle so that each number is used exactly once and for any three consecutive numbers $a, b, c$ the number $a + c$ is divisible by $b + 1$. Can he do it? [i]Proposed by Fedir Yudin[/i]

2021 Cyprus JBMO TST, 1

Tags: divisibility , number theory

Find all positive integers $n$, such that the number \[ \frac{n^{2021}+101}{n^2+n+1}\] is an integer.

2000 Belarus Team Selection Test, 4.3

Tags: algebra , modular arithmetic , arithmetic sequence , divisibility , sum of digits

Prove that for every real number $M$ there exists an infinite arithmetic progression such that: - each term is a positive integer and the common difference is not divisible by 10 - the sum of the digits of each term (in decimal representation) exceeds $M$.

2011 All-Russian Olympiad, 1

Tags: floor function , combinatorics , divisibility

For some 2011 natural numbers, all the $\frac{2010\cdot 2011}{2}$ possible sums were written out on a board. Could it have happened that exactly one third of the written numbers were divisible by three and also exactly one third of them give a remainder of one when divided by three?

2022 Korea -Final Round, P5

Tags: number theory , divisibility , chinese remainder theorem , quadratic residue , hensel s lemma

Find all positive integers $m$ such that there exists integers $x$ and $y$ that satisfies $$m \mid x^2+11y^2+2022.$$

2022 CIIM, 4

Tags: counting , number theory , divisibility , permutation

Given a positive integer $n$, determine how many permutations $\sigma$ of the set $\{1, 2, \ldots , 2022n\}$ have the following property: for each $i \in \{1, 2, \ldots , 2021n + 1\}$, the number $$\sigma(i) + \sigma(i + 1) + \cdots + \sigma(i + n - 1)$$ is a multiple of $n$.

1997 Romania Team Selection Test, 2

Tags: modular arithmetic , number theory , divisibility , multiplicative nt , multiplicative order

Suppose that $A$ be the set of all positive integer that can write in form $a^2+2b^2$ (where $a,b\in\mathbb {Z}$ and $b$ is not equal to $0$). Show that if $p$ be a prime number and $p^2\in A$ then $p\in A$. [i]Marcel Tena[/i]

1998 Slovenia National Olympiad, Problem 1

Tags: number theory , divisibility

Show that for any integter $a$, the number $\frac{a^5}5+\frac{a^3}3+\frac{7a}{15}$ is an integer.