Olympiad problems

2018 Pan-African Shortlist, N2

A positive integer is called special if its digits can be arranged to form an integer divisible by $4$. How many of the integers from $1$ to $2018$ are special?

2015 IFYM, Sozopol, 1

Tags: prime number , divisibility , number theory

Let $p$, $q$ be two distinct prime numbers and $n$ be a natural number, such that $pq$ divides $n^{pq}+1$. Prove that, if $p^3 q^3$ divides $n^{pq}+1$, then $p^2$ or $q^2$ divides $n+1$.

2018 Polish Junior MO First Round, 3

Tags: number theory , prime number , divisibility

Prime numbers $a, b, c$ are bigger that $3$. Show that $(a - b)(b - c)(c - a)$ is divisible by $48$.

2010 Belarus Team Selection Test, 2.2

Tags: number theory , prime , divisibility

Let $p$ be a positive prime integer, $S(p)$ be the number of triples $(x,y,z)$ such that $x,y,z\in\{0,1,..., p-1\}$ and $x^2+y^2+z^2$ is divided by $p$. Prove that $S(p) \ge 2p- 1$. (I. Bliznets)

2014 Contests, 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]

1983 IMO Longlists, 9

Tags: combinatorics , algebra , partial order , sequence , divisibility

Consider the set of all strictly decreasing sequences of $n$ natural numbers having the property that in each sequence no term divides any other term of the sequence. Let $A = (a_j)$ and $B = (b_j)$ be any two such sequences. We say that $A$ precedes $B$ if for some $k$, $a_k < b_k$ and $a_i = b_i$ for $i < k$. Find the terms of the first sequence of the set under this ordering.

2008 Germany Team Selection Test, 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]

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

2011 IMO Shortlist, 3

Tags: number theory , algebra , function , divisibility

Let $n \geq 1$ be an odd integer. Determine all functions $f$ from the set of integers to itself, such that for all integers $x$ and $y$ the difference $f(x)-f(y)$ divides $x^n-y^n.$ [i]Proposed by Mihai Baluna, Romania[/i]

1974 Vietnam National Olympiad, 2

Tags: number theory , divisibility

i) How many integers $n$ are there such that $n$ is divisible by $9$ and $n+1$ is divisible by $25$? ii) How many integers $n$ are there such that $n$ is divisible by $21$ and $n+1$ is divisible by $165$? iii) How many integers $n$ are there such that $n$ is divisible by $9, n + 1$ is divisible by $25$, and $n + 2$ is divisible by $4$?

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.

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

2003 IMO Shortlist, 1

Tags: number theory , sequence , divisibility , modular arithmetic

Let $m$ be a fixed integer greater than $1$. The sequence $x_0$, $x_1$, $x_2$, $\ldots$ is defined as follows: \[x_i = \begin{cases}2^i&\text{if }0\leq i \leq m - 1;\\\sum_{j=1}^mx_{i-j}&\text{if }i\geq m.\end{cases}\] Find the greatest $k$ for which the sequence contains $k$ consecutive terms divisible by $m$ . [i]Proposed by Marcin Kuczma, Poland[/i]

1969 IMO Longlists, 25

Tags: number theory , divisibility , frobenius , additive number theory

$(GBR 2)$ Let $a, b, x, y$ be positive integers such that $a$ and $b$ have no common divisor greater than $1$. Prove that the largest number not expressible in the form $ax + by$ is $ab - a - b$. If $N(k)$ is the largest number not expressible in the form $ax + by$ in only $k$ ways, find $N(k).$

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]

2023 UMD Math Competition Part II, 3

Tags: combination , divisibility , number theory

Let $p$ be a prime, and $n > p$ be an integer. Prove that \[ \binom{n+p-1}{p} - \binom{n}{p} \] is divisible by $n$.

1982 IMO Longlists, 31

Tags: equation , number theory , diophantine equation , divisibility

Prove that if $n$ is a positive integer such that the equation \[ x^3-3xy^2+y^3=n \] has a solution in integers $x,y$, then it has at least three such solutions. Show that the equation has no solutions in integers for $n=2891$.

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.

2007 IMO Shortlist, 1

Tags: number theory , divisibility

Find all pairs of natural numbers $ (a, b)$ such that $ 7^a \minus{} 3^b$ divides $ a^4 \plus{} b^2$. [i]Author: Stephan Wagner, Austria[/i]

2004 German National Olympiad, 3

Tags: number theory , divisibility , digit , sum of digits

Prove that for every positive integer $n$ there is an $n$-digit number $z$ with none of its digits $0$ and such that $z$ is divisible by its sum of digits.

1997 Slovenia National Olympiad, Problem 1

Tags: number theory , divisibility

Suppose that $m,n$ are integers greater than $1$ such that $m+n-1$ divides $m^2+n^2-1$. Prove that $m+n-1$ cannot be a prime number.

1969 IMO Longlists, 49

Tags: number theory , combinatorics , divisibility , 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.$

1997 Moldova Team Selection Test, 3

Tags: number theory , pigeonhole principle , decimal representation , divisibility , multiple , digit

Prove that every integer $ k$ greater than 1 has a multiple that is less than $ k^4$ and can be written in the decimal system with at most four different digits.

2014 German National Olympiad, 2

Tags: combinatorics , number theory , divisibility , sequence , formula

For a positive integer $n$, let $y_n$ be the number of $n$-digit positive integers containing only the digits $2,3,5, 7$ and which do not have a $5$ directly to the right of a $2.$ If $r\geq 1$ and $m\geq 2$ are integers, prove that $y_{m-1}$ divides $y_{rm-1}.$

2018 Kyiv Mathematical Festival, 4

Tags: number theory , divisibility

Do there exist positive integers $a$ and $b$ such that each of the numbers $2^a+3^b,$ $3^a+5^b$ and $5^a+2^b$ is divisible by 29?