Olympiad problems

2017 JBMO Shortlist, NT2

Determine all positive integers n such that $n^2/ (n - 1)!$

2019 China Team Selection Test, 4

Tags: divisibility , number theory

Call a sequence of positive integers $\{a_n\}$ good if for any distinct positive integers $m,n$, one has $$\gcd(m,n) \mid a_m^2 + a_n^2 \text{ and } \gcd(a_m,a_n) \mid m^2 + n^2.$$ Call a positive integer $a$ to be $k$-good if there exists a good sequence such that $a_k = a$. Does there exists a $k$ such that there are exactly $2019$ $k$-good positive integers?

2019 Poland - Second Round, 4

Tags: positive integer , number theory , divisibility

Let $a_1, a_2, \ldots, a_n$ ($n\ge 3$) be positive integers such that $gcd(a_1, a_2, \ldots, a_n)=1$ and for each $i\in \lbrace 1,2,\ldots, n \rbrace$ we have $a_i|a_1+a_2+\ldots+a_n$. Prove that $a_1a_2\ldots a_n | (a_1+a_2+\ldots+a_n)^{n-2}$.

2019 Bundeswettbewerb Mathematik, 2

Tags: digit , divisible , divisibility , number theory

The lettes $A,C,F,H,L$ and $S$ represent six not necessarily distinct decimal digits so that $S \ne 0$ and $F \ne 0$. We form the two six-digit numbers $SCHLAF$ and $FLACHS$. Show that the difference of these two numbers is divisible by $271$ if and only if $C=L$ and $H=A$. [i]Remark:[/i] The words "Schlaf" and "Flachs" are German for "sleep" and "flax".

2021 China Team Selection Test, 2

Tags: number theory , number sequence , divisibility

Given distinct positive integer $ a_1,a_2,…,a_{2020} $. For $ n \ge 2021 $, $a_n$ is the smallest number different from $a_1,a_2,…,a_{n-1}$ which doesn't divide $a_{n-2020}...a_{n-2}a_{n-1}$. Proof that every number large enough appears in the sequence.

1997 Slovenia National Olympiad, Problem 2

Tags: divisibility , number theory

Let $a$ be an integer and $p$ a prime number that divides both $5a-1$ and $a-10$. Show that $p$ also divides $a-3$.

1969 IMO Longlists, 49

Tags: number theory , divisibility , combinatorics , invariant

$(NET 4)$ A boy has a set of trains and pieces of railroad track. Each piece is a quarter of circle, and by concatenating these pieces, the boy obtained a closed railway. The railway does not intersect itself. In passing through this railway, the train sometimes goes in the clockwise direction, and sometimes in the opposite direction. Prove that the train passes an even number of times through the pieces in the clockwise direction and an even number of times in the counterclockwise direction. Also, prove that the number of pieces is divisible by $4.$

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?

2013 Brazil Team Selection Test, 3

Tags: modular arithmetic , number theory , divisibility

Let $x$ and $y$ be positive integers. If ${x^{2^n}}-1$ is divisible by $2^ny+1$ for every positive integer $n$, prove that $x=1$.

2018 China Team Selection Test, 5

Tags: binomial coefficient , number theory , divisibility

Given a positive integer $k$, call $n$ [i]good[/i] if among $$\binom{n}{0},\binom{n}{1},\binom{n}{2},...,\binom{n}{n}$$ at least $0.99n$ of them are divisible by $k$. Show that exists some positive integer $N$ such that among $1,2,...,N$, there are at least $0.99N$ good numbers.

2000 Moldova National Olympiad, Problem 1

Tags: divisibility , determinant , number theory

Let $1=d_1<d_2<\ldots<d_{2m}=n$ be the divisors of a positive integer $n$, where $n$ is not a perfect square. Consider the determinant $$D=\begin{vmatrix}n+d_1&n&\ldots&n\\n&n+d_2&\ldots&n\\\ldots&\ldots&&\ldots\\n&n&\ldots&n+d_{2m}\end{vmatrix}.$$ (a) Prove that $n^m$ divides $D$. (b) Prove that $1+d_1+d_2+\ldots+d_{2m}$ divides $D$.

1992 IMO Longlists, 2

Tags: number theory , relatively prime , divisibility

Let $m$ be a positive integer and $x_0, y_0$ integers such that $x_0, y_0$ are relatively prime, $y_0$ divides $x_0^2+m$, and $x_0$ divides $y_0^2+m$. Prove that there exist positive integers $x$ and $y$ such that $x$ and $y$ are relatively prime, $y$ divides $x^2 + m$, $x$ divides $y^2 + m$, and $x + y \leq m+ 1.$

1962 IMO, 1

Tags: number theory , decimal representation , divisibility

Find the smallest natural number $n$ which has the following properties: a) Its decimal representation has a 6 as the last digit. b) If the last digit 6 is erased and placed in front of the remaining digits, the resulting number is four times as large as the original number $n$.

2006 Germany Team Selection Test, 2

Tags: factorial , modular arithmetic , number theory , divisibility , exponential , chinese remainder theorem

Find all positive integers $ n$ such that there exists a unique integer $ a$ such that $ 0\leq a < n!$ with the following property: \[ n!\mid a^n \plus{} 1 \] [i]Proposed by Carlos Caicedo, Colombia[/i]

2016 Switzerland Team Selection Test, Problem 11

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.

2019 ELMO Shortlist, N4

Tags: number theory , divisibility

A positive integer $b$ and a sequence $a_0,a_1,a_2,\dots$ of integers $0\le a_i<b$ is given. It is known that $a_0\neq 0$ and the sequence $\{a_i\}$ is eventually periodic but has infinitely many nonzero terms. Let $S$ be the set of positive integers $n$ so that $n\mid (a_0a_1\dots a_n)_b$. Given that $S$ is infinite, show that there are infinitely many primes that divide at least one element of $S$. [i]Proposed by Carl Schildkraut and Holden Mui[/i]

1984 IMO, 3

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

1967 IMO Shortlist, 1

Tags: binomial coefficient , number theory , divisibility

Let $k,m,n$ be natural numbers such that $m+k+1$ is a prime greater than $n+1$. Let $c_s=s(s+1)$. Prove that \[(c_{m+1}-c_k)(c_{m+2}-c_k)\ldots(c_{m+n}-c_k)\] is divisible by the product $c_1c_2\ldots c_n$.

2016 Saudi Arabia IMO TST, 2

Tags: divisibility

Let $a$ be a positive integer. Find all prime numbers $ p $ with the following property: there exist exactly $ p $ ordered pairs of integers $ (x, y)$, with $ 0 \leq x, y \leq p - 1 $, such that $ p $ divides $ y^2 - x^3 - a^2x $.

2016 Belarus Team Selection Test, 3

Tags: factorial , number theory , divisibility

Let $a$ and $b$ be positive integers such that $a! + b!$ divides $a!b!$. Prove that $3a \ge 2b + 2$.

2023 Thailand TST, 1

Tags: number theory , divisibility , prime

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

1969 IMO Shortlist, 13

Tags: modular arithmetic , number theory , divisibility , additive number theory

$(CZS 2)$ Let $p$ be a prime odd number. Is it possible to find $p-1$ natural numbers $n + 1, n + 2, . . . , n + p -1$ such that the sum of the squares of these numbers is divisible by the sum of these numbers?

Kvant 2022, M2714

Tags: number theory , polynomial , divisibility

Let $f{}$ and $g{}$ be polynomials with integers coefficients. The leading coefficient of $g{}$ is equal to 1. It is known that for infinitely many natural numbers $n{}$ the number $f(n)$ is divisible by $g(n)$ . Prove that $f(n)$ is divisible by $g(n)$ for all positive integers $n{}$ such that $g(n)\neq 0$. [i]From the folklore[/i]

2014 APMO, 3

Tags: quadratic residue , divisibility , hensel , surjective

Find all positive integers $n$ such that for any integer $k$ there exists an integer $a$ for which $a^3+a-k$ is divisible by $n$. [i]Warut Suksompong, Thailand[/i]

2024 VJIMC, 4

Tags: number theory , analytic number theory , divisibility

Let $p>2$ be a prime and let \[\mathcal{A}=\{n \in \mathbb{N}: 2p \mid n \text{ and } p^2\nmid n \text{ and } n \mid 3^n-1\}.\] Prove that \[\limsup_{k \to \infty} \frac{\vert \mathcal{A} \cap [1,k]\vert}{k} \le \frac{2\log 3}{p\log p}.\]