Olympiad problems

2006 IMO Shortlist, 7

For all positive integers $n$, show that there exists a positive integer $m$ such that $n$ divides $2^{m} + m$. [i]Proposed by Juhan Aru, Estonia[/i]

2024 JBMO TST - Turkey, 5

Tags: perfect square , number theory , divisibility

Find all positive integer values of $n$ such that the value of the $$\frac{2^{n!}-1}{2^n-1}$$ is a square of an integer.

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]

2008 Germany Team Selection Test, 3

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]

1994 Bundeswettbewerb Mathematik, 2

Tags: sequence , number theory , divisibility

Let $k$ be an integer and define a sequence $a_0 , a_1 ,a_2 ,\ldots$ by $$ a_0 =0 , \;\; a_1 =k \;\;\text{and} \;\; a_{n+2} =k^{2}a_{n+1}-a_n \; \text{for} \; n\geq 0.$$ Prove that $a_{n+1} a_n +1$ divides $a_{n+1}^{2} +a_{n}^{2}$ for all $n$.

2012 APMO, 3

Tags: modular arithmetic , number theory , prime , divisibility

Determine all the pairs $ (p , n )$ of a prime number $ p$ and a positive integer $ n$ for which $ \frac{ n^p + 1 }{p^n + 1} $ is an integer.

2024 Turkey EGMO TST, 2

Tags: number theory , function , divisibility , functional equation

Find all functions $f:\mathbb{Z}^{+} \rightarrow \mathbb{Z}^{+}$ such that the conditions $\quad a) \quad a-b \mid f(a)-f(b)$ for all $a\neq b$ and $a,b \in \mathbb{Z}^{+}$ $\quad b) \quad f(\varphi(a))=\varphi(f(a))$ for all $a \in \mathbb{Z}^{+}$ where $\varphi$ is the Euler's totient function. holds

1988 IMO Longlists, 10

Tags: algebra , polynomial , modular arithmetic , number theory , divisibility

Let $ a$ be the greatest positive root of the equation $ x^3 \minus{} 3 \cdot x^2 \plus{} 1 \equal{} 0.$ Show that $ \left[a^{1788} \right]$ and $ \left[a^{1988} \right]$ are both divisible by 17. Here $ [x]$ denotes the integer part of $ x.$

1969 IMO Longlists, 43

Tags: modular arithmetic , number theory , divisibility

$(MON 4)$ Let $p$ and $q$ be two prime numbers greater than $3.$ Prove that if their difference is $2^n$, then for any two integers $m$ and $n,$ the number $S = p^{2m+1} + q^{2m+1}$ is divisible by $3.$

2019 IMEO, 5

Tags: divisibility , number theory

Find all pairs of positive integers $(s, t)$, so that for any two different positive integers $a$ and $b$ there exists some positive integer $n$, for which $$a^s + b^t | a^n + b^{n+1}.$$ [i]Proposed by Oleksii Masalitin (Ukraine)[/i]

2015 IFYM, Sozopol, 5

Tags: prime divisor , number theory , prime number , divisibility

Does there exist a natural number $n$ with exactly 3 different prime divisors $p$, $q$, and $r$, so that $p-1\mid n$, $qr-1\mid n$, $q-1\nmid n$, $r-1\nmid n$, and $3\nmid q+r$?

2020 Iran Team Selection Test, 5

Tags: fractional part , divisibility , algebra

For every positive integer $k>1$ prove that there exist a real number $x$ so that for every positive integer $n<1398$: $$\left\{x^n\right\}<\left\{x^{n-1}\right\} \Longleftrightarrow k\mid n.$$ [i]Proposed by Mohammad Amin Sharifi[/i]

1999 Romania Team Selection Test, 10

Tags: modular arithmetic , number theory , divisibility

Determine all positive integers $n$ for which there exists an integer $m$ such that ${2^{n}-1}$ is a divisor of ${m^{2}+9}$.

2022 Iran MO (3rd Round), 2

Tags: number theory , divisibility , sequence

For two rational numbers $r,s$ we say:$$r\mid s$$whenever there exists $k\in\mathbb{Z}$ such that:$$s=kr$$ ${(a_n)}_{n\in\mathbb{N}}$ is an increasing sequence of pairwise coprime natural numbers and ${(b_n)}_{n\in\mathbb{N}}$ is a sequence of distinct natural numbers. Assume that for all $n\in\mathbb{N}$ we have: $$\sum_{i=1}^{n}\frac{1}{a_i}\mid\sum_{i=1}^{n}\frac{1}{b_i}$$ Prove that [b]for all[/b] $n\in\mathbb{N}$ we have: $a_n=b_n$.

2024 Kyiv City MO Round 1, Problem 3

Tags: game , number theory , divisibility

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 $2024$ 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 $2024$ loses. Who wins if every player wants to win? [i]Proposed by Mykhailo Shtandenko[/i]

2018 India Regional Mathematical Olympiad, 5

Tags: algebra , number theory , divisibility

Find all natural numbers $n$ such that $1+[\sqrt{2n}]~$ divides $2n$. ( For any real number $x$ , $[x]$ denotes the largest integer not exceeding $x$. )

2019 Tournament Of Towns, 2

Tags: number theory , sum of powers , divisibility

Consider two positive integers $a$ and $b$ such that $a^{n+1} + b^{n+1}$ is divisible by $a^n + b^n$ for infinitely many positive integers $n$. Is it necessarily true that $a = b$? (Boris Frenkin)

2022 Germany Team Selection Test, 2

Tags: number theory , divisibility , cubefree

Find all positive integers $n\geq1$ such that there exists a pair $(a,b)$ of positive integers, such that $a^2+b+3$ is not divisible by the cube of any prime, and $$n=\frac{ab+3b+8}{a^2+b+3}.$$

2018 Brazil Team Selection Test, 3

Tags: combinatorics , counting , number theory , divisibility

Let $n > 10$ be an odd integer. Determine the number of ways to place the numbers $1, 2, \ldots , n$ around a circle so that each number in the circle divides the sum its two neighbors. (Two configurations such that one can be obtained from the other per rotation are to be counted only once.)

1990 IMO Shortlist, 23

Tags: modular arithmetic , number theory , divisibility , orders and lte

Determine all integers $ n > 1$ such that \[ \frac {2^n \plus{} 1}{n^2} \] is an integer.

2023 Romania Team Selection Test, P3

Tags: number theory , factorial , divisibility

Given a positive integer $a,$ prove that $n!$ is divisible by $n^2 + n + a$ for infinitely many positive integers $n.{}$ [i]Proposed by Andrei Bâra[/i]

1977 IMO Shortlist, 3

Tags: number theory , additive number theory , remainder , divisibility

Let $a,b$ be two natural numbers. When we divide $a^2+b^2$ by $a+b$, we the the remainder $r$ and the quotient $q.$ Determine all pairs $(a, b)$ for which $q^2 + r = 1977.$

2024 Singapore Senior Math Olympiad, Q4

Tags: number theory , divisibility

Suppose $p$ is a prime number and $x, y, z$ are integers satisfying $0 < x < y < z <p$. If $x^3, y^3, z^3$ have equal remainders when divided by $p$, prove that $x ^ 2 + y ^ 2 + z ^ 2$ is divisible by $x + y + z$.

2004 IMO Shortlist, 3

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

Find all functions $ f: \mathbb{N^{*}}\to \mathbb{N^{*}}$ satisfying \[ \left(f^{2}\left(m\right)+f\left(n\right)\right) \mid \left(m^{2}+n\right)^{2}\] for any two positive integers $ m$ and $ n$. [i]Remark.[/i] The abbreviation $ \mathbb{N^{*}}$ stands for the set of all positive integers: $ \mathbb{N^{*}}=\left\{1,2,3,...\right\}$. By $ f^{2}\left(m\right)$, we mean $ \left(f\left(m\right)\right)^{2}$ (and not $ f\left(f\left(m\right)\right)$). [i]Proposed by Mohsen Jamali, Iran[/i]

2009 Serbia National Math Olympiad, 4

Tags: combinatorics , permutation , divisibility

Let $n \in \mathbb N$ and $A_n$ set of all permutations $(a_1, \ldots, a_n)$ of the set $\{1, 2, \ldots , n\}$ for which \[k|2(a_1 + \cdots+ a_k), \text{ for all } 1 \leq k \leq n.\] Find the number of elements of the set $A_n$. [i]Proposed by Vidan Govedarica, Serbia[/i]