Olympiad problems

2021 Baltic Way, 20

Let $n\ge 2$ be an integer. Given numbers $a_1, a_2, \ldots, a_n \in \{1,2,3,\ldots,2n\}$ such that $\operatorname{lcm}(a_i,a_j)>2n$ for all $1\le i<j\le n$, prove that $$a_1a_2\ldots a_n \mid (n+1)(n+2)\ldots (2n-1)(2n).$$

1969 IMO Longlists, 19

Tags: number theory , relatively prime , Periodic sequence , Divisibility , IMO Shortlist , IMO Longlist

$(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.$

2020 Macedonian Nationаl Olympiad, 1

Tags: number theory , fermat's little theorem , GCD , Divisibility , prime numbers

Let $a, b$ be positive integers and $p, q$ be prime numbers for which $p \nmid q - 1$ and $q \mid a^p - b^p$. Prove that $q \mid a - b$.

1999 IMO Shortlist, 1

Tags: number theory , Divisibility , prime , IMO Shortlist , IMO , IMO 1999 , Hi

Find all the pairs of positive integers $(x,p)$ such that p is a prime, $x \leq 2p$ and $x^{p-1}$ is a divisor of $ (p-1)^{x}+1$.

1978 IMO Shortlist, 15

Tags: modular arithmetic , algebra , polynomial , number theory , Divisibility , IMO Shortlist

Let $p$ be a prime and $A = \{a_1, \ldots , a_{p-1} \}$ an arbitrary subset of the set of natural numbers such that none of its elements is divisible by $p$. Let us define a mapping $f$ from $\mathcal P(A)$ (the set of all subsets of $A$) to the set $P = \{0, 1, \ldots, p - 1\}$ in the following way: $(i)$ if $B = \{a_{i_{1}}, \ldots , a_{i_{k}} \} \subset A$ and $\sum_{j=1}^k a_{i_{j}} \equiv n \pmod p$, then $f(B) = n,$ $(ii)$ $f(\emptyset) = 0$, $\emptyset$ being the empty set. Prove that for each $n \in P$ there exists $B \subset A$ such that $f(B) = n.$

2022 Indonesia TST, N

Tags: Order , number theory , identity , Divisibility

Given positive odd integers $m$ and $n$ where the set of all prime factors of $m$ is the same as the set of all prime factors $n$, and $n \vert m$. Let $a$ be an arbitrary integer which is relatively prime to $m$ and $n$. Prove that: \[ o_m(a) = o_n(a) \times \frac{m}{\gcd(m, a^{o_n(a)}-1)} \] where $o_k(a)$ denotes the smallest positive integer such that $a^{o_k(a)} \equiv 1$ (mod $k$) holds for some natural number $k > 1$.

2025 Bulgarian Spring Mathematical Competition, 9.4

Tags: functional equation , number theory , Divisibility , primes , Sophie Germain identity , function

Determine all functions $f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ such that $f(a) + 2ab + 2f(b)$ divides $f(a)^2 + 4f(b)^2$ for any positive integers $a$ and $b$.

2025 Bulgarian Winter Tournament, 12.3

Tags: function , Sequence , Divisibility , polynomial , large numbers , number theory

Determine all functions $f: \mathbb{Z}_{\geq 2025} \to \mathbb{Z}_{>0}$ such that $mn+1$ divides $f(m)f(n) + 1$ for any integers $m,n \geq 2025$ and there exists a polynomial $P$ with integer coefficients, such that $f(n) \leq P(n)$ for all $n\geq 2025$.

2010 Ukraine Team Selection Test, 6

Tags: number theory , Integer , Divisibility

Find all pairs of odd integers $a$ and $b$ for which there exists a natural number$ c$ such that the number $\frac{c^n+1}{2^na+b}$ is integer for all natural $n$.

2022 Germany Team Selection Test, 2

Tags: number theory , IMO Shortlist , Divisibility , cubefree , Hi

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}.$$

2012 Bogdan Stan, 2

Tags: GCD , LCM , Divisibility , number theory

For any $ a\in\mathbb{Z}_{\ge 0} $ make the notation $ a\mathbb{Z}_{\ge 0} =\{ an| n\in\mathbb{Z}_{\ge 0} \} . $ Prove that the following relations are equivalent: $ \text{(1)} a\mathbb{Z}_{\ge 0} \setminus b\mathbb{Z}_{\ge 0}\subset c\mathbb{Z}_{\ge 0} \setminus d\mathbb{Z}_{\ge 0} $ $ \text{(2)} b|a\text{ or } (c|a\text{ and } \text{lcm} (a,b) |\text{lcm} (a,d)) $ [i]Marin Tolosi[/i] and [i]Cosmin Nitu[/i]