Olympiad problems

2020 IMO Shortlist, N1

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]

2008 India Regional Mathematical Olympiad, 4

Tags: number theory , divisibility , natural number

Determine all the natural numbers $n$ such that $21$ divides $2^{2^{n}}+2^n+1.$

2020 Iran Team Selection Test, 5

Tags: fractional part , algebra , divisibility

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]

1985 Traian Lălescu, 1.1

Tags: divisibility , algebra , polynomial

Prove that for all $ n\ge 2 $ natural numbers there exist $ a_n\in\mathbb{Q} $ such that $$ X^{2n}+a_nX^n+1\Huge\vdots X^2+\frac{1}{2}X+1, $$ and that there isn´t any $ a_n\in\mathbb{R}\setminus\mathbb{Q} $ with this property.

2010 Bosnia And Herzegovina - Regional Olympiad, 3

Tags: number theory , divisibility , odd

Let $n$ be an odd positive integer bigger than $1$. Prove that $3^n+1$ is not divisible with $n$

Dumbest FE I ever created, 1.

Tags: function , number theory , functional equation , divisibility , euler s phi function

Determine all functions $f\colon\mathbb{Z}_{>0}\to\mathbb{Z}_{>0}$ such that, for all positive integers $m$ and $n$, $$ m^{\phi(n)}+n^{\phi(m)} \mid f(m)^n + f(n)^m$$

2018 USA TSTST, 8

Tags: number theory , divisibility

For which positive integers $b > 2$ do there exist infinitely many positive integers $n$ such that $n^2$ divides $b^n+1$? [i]Evan Chen and Ankan Bhattacharya[/i]

2009 Serbia Team Selection Test, 1

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]

1974 IMO, 3

Tags: binomial coefficient , number theory , summation , divisibility , modular arithmetic

Prove that for any n natural, the number \[ \sum \limits_{k=0}^{n} \binom{2n+1}{2k+1} 2^{3k} \] cannot be divided by $5$.

2018 South Africa National Olympiad, 5

Tags: number theory , divisibility , sequence

Determine all sequences $a_1, a_2, a_3, \dots$ of nonnegative integers such that $a_1 < a_2 < a_3 < \dots$ and $a_n$ divides $a_{n - 1} + n$ for all $n \geq 2$.

2022 Bulgaria JBMO TST, 3

Tags: number theory , coprime , divisibility , relatively prime

The integers $a$, $b$, $c$ and $d$ are such that $a$ and $b$ are relatively prime, $d\leq 2022$ and $a+b+c+d = ac + bd = 0$. Determine the largest possible value of $d$,

Fractal Edition 1, P1

Tags: divisibility , gyatt , skibidi , no

Is the number $1234567890987654321$ prime?

2014-2015 SDML (High School), 2

Tags: divisibility

Sally is thinking of a positive four-digit integer. When she divides it by any one-digit integer greater than $1$, the remainder is $1$. How many possible values are there for Sally's four-digit number?

1978 IMO Shortlist, 15

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

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

2003 Olympic Revenge, 2

Tags: number theory , sequence , recurrence relation , divisibility

Let $x_n$ the sequence defined by any nonnegatine integer $x_0$ and $x_{n+1}=1+\prod_{0 \leq i \leq n}{x_i}$ Show that there exists prime $p$ such that $p\not|x_n$ for any $n$.

2014 IFYM, Sozopol, 1

Tags: number theory , euler s totient function , divisibility

Find all pairs of natural numbers $(m,n)$, for which $m\mid 2^{\varphi(n)} +1$ and $n\mid 2^{\varphi (m)} +1$.

2022 Poland - Second Round, 3

Tags: number theory , prime number , modular congruences , divisibility

Positive integers $a,b,c$ satisfying the equation $$a^3+4b+c = abc,$$ where $a \geq c$ and the number $p = a^2+2a+2$ is a prime. Prove that $p$ divides $a+2b+2$.

2010 Germany Team Selection Test, 1

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

Let $f$ be a non-constant function from the set of positive integers into the set of positive integer, such that $a-b$ divides $f(a)-f(b)$ for all distinct positive integers $a$, $b$. Prove that there exist infinitely many primes $p$ such that $p$ divides $f(c)$ for some positive integer $c$. [i]Proposed by Juhan Aru, Estonia[/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.

1993 IMO Shortlist, 2

Tags: modular arithmetic , number theory , divisibility , prime number , composite number

A natural number $n$ is said to have the property $P,$ if, for all $a, n^2$ divides $a^n - 1$ whenever $n$ divides $a^n - 1.$ a.) Show that every prime number $n$ has property $P.$ b.) Show that there are infinitely many composite numbers $n$ that possess property $P.$

1984 IMO, 2

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

Find one pair of positive integers $a,b$ such that $ab(a+b)$ is not divisible by $7$, but $(a+b)^7-a^7-b^7$ is divisible by $7^7$.

2007 IMO Shortlist, 3

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

Let $ X$ be a set of 10,000 integers, none of them is divisible by 47. Prove that there exists a 2007-element subset $ Y$ of $ X$ such that $ a \minus{} b \plus{} c \minus{} d \plus{} e$ is not divisible by 47 for any $ a,b,c,d,e \in Y.$ [i]Author: Gerhard Wöginger, Netherlands[/i]

1962 All-Soviet Union Olympiad, 12

Tags: number theory , algebra , divisibility

Given unequal integers $x, y, z$ prove that $(x-y)^5 + (y-z)^5 + (z-x)^5$ is divisible by $5(x-y)(y- z)(z-x)$.

2018 Israel National Olympiad, 4

Tags: number theory , digit , digit sum , divisibility

The three-digit number 999 has a special property: It is divisible by 27, and its digit sum is also divisible by 27. The four-digit number 5778 also has this property, as it is divisible by 27 and its digit sum is also divisible by 27. How many four-digit numbers have this property?

2015 Harvard-MIT Mathematics Tournament, 4

Tags: algebra , divisibility , sequence

Compute the number of sequences of integers $(a_1,\ldots,a_{200})$ such that the following conditions hold. [list] [*] $0\leq a_1<a_2<\cdots<a_{200}\leq 202.$ [*] There exists a positive integer $N$ with the following property: for every index $i\in\{1,\ldots,200\}$ there exists an index $j\in\{1,\ldots,200\}$ such that $a_i+a_j-N$ is divisible by $203$. [/list]