Olympiad problems

2016 Indonesia TST, 2

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.

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]

2024 Middle European Mathematical Olympiad, 4

Tags: number theory , polynomial , sum of divisors , divisibility , factorization

Determine all polynomials $P(x)$ with integer coefficients such that $P(n)$ is divisible by $\sigma(n)$ for all positive integers $n$. (As usual, $\sigma(n)$ denotes the sum of all positive divisors of $n$.)

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]

Kvant 2020, M2616

Tags: number theory , divisibility

Let $p>5$ be a prime number. Prove that the sum \[\left(\frac{(p-1)!}{1}\right)^p+\left(\frac{(p-1)!}{2}\right)^p+\cdots+\left(\frac{(p-1)!}{p-1}\right)^p\]is divisible by $p^3$.

2006 Germany Team Selection Test, 2

Tags: modular arithmetic , factorial , 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]

2000 Belarus Team Selection Test, 4.3

Tags: algebra , arithmetic sequence , divisibility , sum of digits , modular arithmetic

Prove that for every real number $M$ there exists an infinite arithmetic progression such that: - each term is a positive integer and the common difference is not divisible by 10 - the sum of the digits of each term (in decimal representation) exceeds $M$.

1968 IMO Shortlist, 16

Tags: algebra , calculus , divisibility , polynomial , number theory

A polynomial $p(x) = a_0x^k + a_1x^{k-1} + \cdots + a_k$ with integer coefficients is said to be divisible by an integer $m$ if $p(x)$ is divisible by m for all integers $x$. Prove that if $p(x)$ is divisible by $m$, then $k!a_0$ is also divisible by $m$. Also prove that if $a_0, k,m$ are non-negative integers for which $k!a_0$ is divisible by $m$, there exists a polynomial $p(x) = a_0x^k+\cdots+ a_k$ divisible by $m.$

2020-IMOC, N4

Tags: number theory , divisibility

$\textbf{N4:} $ Let $a,b$ be two positive integers such that for all positive integer $n>2020^{2020}$, there exists a positive integer $m$ coprime to $n$ with \begin{align*} \text{ $a^n+b^n \mid a^m+b^m$} \end{align*} Show that $a=b$ [i]Proposed by ltf0501[/i]

2005 China Team Selection Test, 1

Tags: number theory , prime number , divisibility , power of 2 , prime divisor

Let $ b, m, n$ be positive integers such that $ b > 1$ and $ m \neq n.$ Prove that if $ b^m \minus{} 1$ and $ b^n \minus{} 1$ have the same prime divisors, then $ b \plus{} 1$ is a power of 2.

2018-IMOC, N3

Tags: divisibility , number theory

Find all pairs of positive integers $(x,y)$ so that $$\frac{(x^2-x+1)(y^2-y+1)}{xy}\in\mathbb N.$$

2016 India IMO Training Camp, 2

Tags: divisibility , number theory

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.

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

2000 Saint Petersburg Mathematical Olympiad, 10.7

Tags: number theory , prime number , divisibility

We'll call a positive integer "almost prime", if it is not divisible by any prime from the interval $[3,19]$. We'll call a number "very non-prime", if it has at least 2 primes from interval $[3,19]$ dividing it. What is the greatest amount of almost prime numbers can be selected, such that the sum of any two of them is a very non-prime number? [I]Proposed by S. Berlov, S. Ivanov[/i]

2016 Rioplatense Mathematical Olympiad, Level 3, 6

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

When the natural numbers are written one after another in an increasing way, you get an infinite succession of digits $123456789101112 ....$ Denote $A_k$ the number formed by the first $k$ digits of this sequence . Prove that for all positive integer $n$ there is a positive integer $m$ which simultaneously verifies the following three conditions: (i) $n$ divides $A_m$, (ii) $n$ divides $m$, (iii) $n$ divides the sum of the digits of $A_m$.

2024 India National Olympiad, 3

Tags: divisibility , modular arithmetic , number theory

Let $p$ be an odd prime and $a,b,c$ be integers so that the integers $$a^{2023}+b^{2023},\quad b^{2024}+c^{2024},\quad a^{2025}+c^{2025}$$ are divisible by $p$. Prove that $p$ divides each of $a,b,c$. $\quad$ Proposed by Navilarekallu Tejaswi

the 9th XMO, 3

Tags: number theory , divisibility

A sequence $\{a_n\} $ satisfies $a_1$ is a positive integer and $a_{n+1}$ is the largest odd integer that divides $2^n-1+a_n$ for all $n\geqslant 1$. Given a positive integer $r$ which is greater than $1$. Is it possible that there exists infinitely many pairs of ordered positive integers $(m,n)$ for which $m>n$ and $a_m = ra_n$? In other words, if you successfully find [b]an[/b] $a_1$ that yields infinitely many pairs of $(m,n)$ which work fine, you win and the answer is YES. Otherwise you have to proof NO for every possible $a_1$. @below, XMO stands for Xueersi Mathematical Olympiad, where Xueersi (学而思) is a famous tutoring camp in China.

2014 JBMO TST - Macedonia, 3

Tags: digit , divisibility , number theory

Find all positive integers $n$ which are divisible by 11 and satisfy the following condition: all the numbers which are generated by an arbitrary rearrangement of the digits of $n$, are also divisible by 11.

2005 Taiwan TST Round 3, 1

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

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]

2022 European Mathematical Cup, 1

Tags: number theory , modular arithmetic , divisibility , divisor

Determine all positive integers $n$ for which there exist positive divisors $a$, $b$, $c$ of $n$ such that $a>b>c$ and $a^2 - b^2$, $b^2 - c^2$, $a^2 - c^2$ are also divisors of $n$.