Olympiad problems

1969 IMO Longlists, 23

$(FRA 6)$ Consider the integer $d = \frac{a^b-1}{c}$, where $a, b$, and $c$ are positive integers and $c \le a.$ Prove that the set $G$ of integers that are between $1$ and $d$ and relatively prime to $d$ (the number of such integers is denoted by $\phi(d)$) can be partitioned into $n$ subsets, each of which consists of $b$ elements. What can be said about the rational number $\frac{\phi(d)}{b}?$

2005 India IMO Training Camp, 2

Tags: divisibility , functional equation , algebra , function , 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]

2003 Federal Math Competition of S&M, Problem 1

Tags: divisibility , recursion , floor function , number theory

Prove that the number $\left\lfloor\left(5+\sqrt{35}\right)^{2n-1}\right\rfloor$ is divisible by $10^n$ for each $n\in\mathbb N$.

2007 Gheorghe Vranceanu, 1

Tags: algebra , divisibility , number theory , induction

Let $ \left( x_n\right)_{n\ge 1} $ be a sequence of integers defined recursively as $ x_{n+2}=5x_{n+1}-x_n. $ Prove that $ \left( x_n\right)_{n\ge 1} $ has a subsequence whose terms are multiples of $ 22 $ if $ \left( x_n\right)_{n\ge 1} $ has a term that is multiple of $ 22. $

2012 Bogdan Stan, 4

Tags: gcd , divisibility , matrix , induction , linear algebra

Prove that the elements of any natural power of a $ 2\times 2 $ special linear integer matrix are pairwise coprime, with the possible exception of the pairs that form the diagonals. [i]Vasile Pop[/i]

2011 Peru IMO TST, 3

Tags: divisibility , number theory , modular arithmetic

Let $a, b$ be integers, and let $P(x) = ax^3+bx.$ For any positive integer $n$ we say that the pair $(a,b)$ is $n$-good if $n | P(m)-P(k)$ implies $n | m - k$ for all integers $m, k.$ We say that $(a,b)$ is $very \ good$ if $(a,b)$ is $n$-good for infinitely many positive integers $n.$ [list][*][b](a)[/b] Find a pair $(a,b)$ which is 51-good, but not very good. [*][b](b)[/b] Show that all 2010-good pairs are very good.[/list] [i]Proposed by Okan Tekman, Turkey[/i]

2008 Germany Team Selection Test, 3

Tags: divisibility , function , modular arithmetic , number theory

Find all surjective functions $ f: \mathbb{N} \to \mathbb{N}$ such that for every $ m,n \in \mathbb{N}$ and every prime $ p,$ the number $ f(m + n)$ is divisible by $ p$ if and only if $ f(m) + f(n)$ is divisible by $ p$. [i]Author: Mohsen Jamaali and Nima Ahmadi Pour Anari, Iran[/i]

2023 Romania Team Selection Test, P3

Tags: number theory , divisibility , factorial

Given a positive integer $a,$ prove that $n!$ is divisible by $n^2 + n + a$ for infinitely many positive integers $n.{}$ [i]Proposed by Andrei Bâra[/i]

2021 China Team Selection Test, 2

Tags: number sequence , divisibility , number theory

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.

1984 IMO, 2

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

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

Tags: divisibility , exponential , number theory , modular arithmetic

For all positive integers $n$, show that there exists a positive integer $m$ such that $n$ divides $2^{m} + m$. [i]Proposed by Juhan Aru, Estonia[/i]

1992 IMO Shortlist, 19

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

Let $ f(x) \equal{} x^8 \plus{} 4x^6 \plus{} 2x^4 \plus{} 28x^2 \plus{} 1.$ Let $ p > 3$ be a prime and suppose there exists an integer $ z$ such that $ p$ divides $ f(z).$ Prove that there exist integers $ z_1, z_2, \ldots, z_8$ such that if \[ g(x) \equal{} (x \minus{} z_1)(x \minus{} z_2) \cdot \ldots \cdot (x \minus{} z_8),\] then all coefficients of $ f(x) \minus{} g(x)$ are divisible by $ p.$

2017 Germany Team Selection Test, 3

Tags: divisibility , number theory , function

Denote by $\mathbb{N}$ the set of all positive integers. Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all positive integers $m$ and $n$, the integer $f(m)+f(n)-mn$ is nonzero and divides $mf(m)+nf(n)$. [i]Proposed by Dorlir Ahmeti, Albania[/i]

2017 Bosnia Herzegovina Team Selection Test, 2

Tags: divisibility , number theory , function

Denote by $\mathbb{N}$ the set of all positive integers. Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all positive integers $m$ and $n$, the integer $f(m)+f(n)-mn$ is nonzero and divides $mf(m)+nf(n)$. [i]Proposed by Dorlir Ahmeti, Albania[/i]

1985 Traian Lălescu, 1.1

Tags: divisibility , polynomial , algebra

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.

2008 Greece Team Selection Test, 1

Tags: divisibility , polynomial , algebra

Find all possible values of $a\in \mathbb{R}$ and $n\in \mathbb{N^*}$ such that $f(x)=(x-1)^n+(x-2)^{2n+1}+(1-x^2)^{2n+1}+a$ is divisible by $\phi (x)=x^2-x+1$

2010 Germany Team Selection Test, 1

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

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]

2019 Kazakhstan National Olympiad, 4

Tags: divisibility , number theory

Find all positive integers $n,k,a_1,a_2,...,a_k$ so that $n^{k+1}+1$ is divisible by $(na_1+1)(na_2+1)...(na_k+1)$

1988 IMO Longlists, 1

Tags: sequence , divisibility , linear recurrence , algebra , linear algebra , modular arithmetic

An integer sequence is defined by \[{ a_n = 2 a_{n-1} + a_{n-2}}, \quad (n > 1), \quad a_0 = 0, a_1 = 1.\] Prove that $2^k$ divides $a_n$ if and only if $2^k$ divides $n$.

1982 IMO Shortlist, 16

Tags: diophantine equation , divisibility , number theory , equation

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

2006 France Team Selection Test, 3

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

Let $a$, $b$ be positive integers such that $b^n+n$ is a multiple of $a^n+n$ for all positive integers $n$. Prove that $a=b$. [i]Proposed by Mohsen Jamali, Iran[/i]

2022 SAFEST Olympiad, 2

Tags: divisibility , integer , number theory

Let $n \geq 2$ be an integer. Prove that if $$\frac{n^2+4^n+7^n}{n}$$ is an integer, then it is divisible by 11.

1990 IMO Shortlist, 7

Tags: functional equation , arithmetic sequence , divisibility , algebra , polynomial , number theory

Let $ f(0) \equal{} f(1) \equal{} 0$ and \[ f(n\plus{}2) \equal{} 4^{n\plus{}2} \cdot f(n\plus{}1) \minus{} 16^{n\plus{}1} \cdot f(n) \plus{} n \cdot 2^{n^2}, \quad n \equal{} 0, 1, 2, \ldots\] Show that the numbers $ f(1989), f(1990), f(1991)$ are divisible by $ 13.$

Russian TST 2015, P1

Tags: divisibility , number theory

Find all pairs of natural numbers $(a,b)$ satisfying the following conditions: [list] [*]$b-1$ is divisible by $a+1$ and [*]$a^2+a+2$ is divisible by $b$. [/list]

2019 Poland - Second Round, 4

Tags: positive integer , divisibility , number theory

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