Olympiad problems

1967 IMO, 3

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

2008 Brazil Team Selection Test, 1

Tags: Divisibility , IMO Shortlist , number theory

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]

2005 Federal Math Competition of S&M, Problem 1

Tags: power mean , Divisibility , algebra , number theory

Let $a$ and $b$ be positive integers and $K=\sqrt{\frac{a^2+b^2}2}$, $A=\frac{a+b}2$. If $\frac KA$ is a positive integer, prove that $a=b$.

2005 Taiwan TST Round 3, 3

Tags: modular arithmetic , number theory , Divisibility , remainder , IMO Shortlist

Given an integer ${n>1}$, denote by $P_{n}$ the product of all positive integers $x$ less than $n$ and such that $n$ divides ${x^2-1}$. For each ${n>1}$, find the remainder of $P_{n}$ on division by $n$. [i]Proposed by John Murray, Ireland[/i]

2025 6th Memorial "Aleksandar Blazhevski-Cane", P5

Tags: number theory , Divisibility , 2-adic valuation

Let $s < t$ be positive integers. Define a sequence by: $a_1 = s, a_2 = t$; $a_3$ is the smallest integer that's greater than $a_2$ and divisible by $a_1$; in general, $a_{n + 1}$ is the smallest integer greater than $a_n$ that's divisible by $a_1, a_2, ..., a_{n - 2}, a_{n - 1}$. [b]a)[/b] What is the maximum number of odd integers that can appear in such a sequence? (Justify your answer) [b]b)[/b] Prove that $a_{2025}$ is divisible by $2^{808}$, regardless of the choice of $s$ and $t$. Proposed by [i]Ilija Jovcevski[/i]

2023 Poland - Second Round, 1

Tags: number theory , Divisibility

Find all positive integers $b$ with the following property: there exists positive integers $a,k,l$ such that $a^k + b^l$ and $a^l + b^k$ are divisible by $b^{k+l}$ where $k \neq l$.

Kvant 2023, M2775

Tags: number theory , Divisibility

Is there an infinite periodic sequence of digits for which the following condition condition is fulfilled: for any natural number $n{}$ a natural number divisible by $2^n{}$ can be cut from this sequence of digits (as a word)? [i]Proposed by P. Kozhevnikov[/i]

2016 Turkey Team Selection Test, 5

Tags: function , number theory , functional equation , Divisibility

Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that for all $m,n \in \mathbb{N}$ holds $f(mn)=f(m)f(n)$ and $m+n \mid f(m)+f(n)$ .

2015 Czech and Slovak Olympiad III A, 6

Tags: Divisibility , number theory , combinatorics , pigeonhole principle

Integer $n>2$ is given. Find the biggest integer $d$, for which holds, that from any set $S$ consisting of $n$ integers, we can find three different (but not necesarilly disjoint) nonempty subsets, such that sum of elements of each of them is divisible by $d$.

2008 Brazil Team Selection Test, 1

Tags: modular arithmetic , number theory , Divisibility , IMO Shortlist , Hi

Let $b,n > 1$ be integers. Suppose that for each $k > 1$ there exists an integer $a_k$ such that $b - a^n_k$ is divisible by $k$. Prove that $b = A^n$ for some integer $A$. [i]Author: Dan Brown, Canada[/i]

2003 IMO Shortlist, 7

Tags: modular arithmetic , polynomial , Recurrence , Sequence , Divisibility , prime , IMO Shortlist

The sequence $a_0$, $a_1$, $a_2,$ $\ldots$ is defined as follows: \[a_0=2, \qquad a_{k+1}=2a_k^2-1 \quad\text{for }k \geq 0.\] Prove that if an odd prime $p$ divides $a_n$, then $2^{n+3}$ divides $p^2-1$. [hide="comment"] Hi guys , Here is a nice problem: Let be given a sequence $a_n$ such that $a_0=2$ and $a_{n+1}=2a_n^2-1$ . Show that if $p$ is an odd prime such that $p|a_n$ then we have $p^2\equiv 1\pmod{2^{n+3}}$ Here are some futher question proposed by me :Prove or disprove that : 1) $gcd(n,a_n)=1$ 2) for every odd prime number $p$ we have $a_m\equiv \pm 1\pmod{p}$ where $m=\frac{p^2-1}{2^k}$ where $k=1$ or $2$ Thanks kiu si u [i]Edited by Orl.[/i] [/hide]

1990 IMO Shortlist, 21

Tags: number theory , Divisibility , binary representation , minimization , IMO Shortlist

Let $ n$ be a composite natural number and $ p$ a proper divisor of $ n.$ Find the binary representation of the smallest natural number $ N$ such that \[ \frac{(1 \plus{} 2^p \plus{} 2^{n\minus{}p})N \minus{} 1}{2^n}\] is an integer.

2016 Bosnia And Herzegovina - Regional Olympiad, 2

Tags: number theory , Divisibility , FBH , Perfect Square

Let $a$ and $b$ be two positive integers such that $2ab$ divides $a^2+b^2-a$. Prove that $a$ is perfect square

2021 Peru Iberoamerican Team Selection Test, P1

Tags: number theory , IMO Shortlist , Divisibility , cubefree , Hi

Find all positive integers $n\geq1$ such that there exists a pair $(a,b)$ of positive integers, such that $a^2+b+3$ is not divisible by the cube of any prime, and $$n=\frac{ab+3b+8}{a^2+b+3}.$$

2008 India Regional Mathematical Olympiad, 4

Tags: number theory , Divisibility , Natural Numbers

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

2016 Brazil Team Selection Test, 2

Tags: factorial , number theory , IMO Shortlist , Divisibility

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

2014 Ukraine Team Selection Test, 12

Tags: prime , number theory , Divisibility

Prove that for an arbitrary prime $p \ge 3$ the number of positive integers $n$, for which $p | n! +1$ does not exceed $cp^{2/3}$, where c is a constant that does not depend on $p$.

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 Junior Balkan Team Selection Tests - Romania, 1

Tags: number theory , Divisibility

Find all the positive integers $N$ with an even number of digits with the property that if we multiply the two numbers formed by cutting the number in the middle we get a number that is a divisor of $N$ ( for example $12$ works because $1 \cdot 2$ divides $12$)

2020 AMC 12/AHSME, 4

Tags: AMC , AMC 12 , 2020 AMC , 2020 AMC 12A , Divisibility , 2020 AMC 10A , AMC 10

How many $4$-digit positive integers (that is, integers between $1000$ and $9999$, inclusive) having only even digits are divisible by $5?$ $\textbf{(A) } 80 \qquad \textbf{(B) } 100 \qquad \textbf{(C) } 125 \qquad \textbf{(D) } 200 \qquad \textbf{(E) } 500$

2009 IMO Shortlist, 4

Tags: modular arithmetic , number theory , IMO Shortlist , Sequence , Divisibility

Find all positive integers $n$ such that there exists a sequence of positive integers $a_1$, $a_2$,$\ldots$, $a_n$ satisfying: \[a_{k+1}=\frac{a_k^2+1}{a_{k-1}+1}-1\] for every $k$ with $2\leq k\leq n-1$. [i]Proposed by North Korea[/i]

2014 IMO Shortlist, N6

Tags: IMO Shortlist , number theory , Divisibility , Modulo Arithmetic , counting in two ways , Integer Polynomial

Let $a_1 < a_2 < \cdots <a_n$ be pairwise coprime positive integers with $a_1$ being prime and $a_1 \ge n + 2$. On the segment $I = [0, a_1 a_2 \cdots a_n ]$ of the real line, mark all integers that are divisible by at least one of the numbers $a_1 , \ldots , a_n$ . These points split $I$ into a number of smaller segments. Prove that the sum of the squares of the lengths of these segments is divisible by $a_1$. [i]Proposed by Serbia[/i]

2008 IMO Shortlist, 2

Tags: combinatorics , permutation , Divisibility , IMO Shortlist

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]

2023 UMD Math Competition Part II, 3

Tags: number theory , combination , Divisibility

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

2016 Saudi Arabia BMO TST, 3

Tags: SAU , Divisibility

Let $ m $ and $ n $ be odd integers such that $n^2 - 1 $ is divisible by $m^2 + 1 - n^2 $. Prove that $ |m^2 + 1 - n^2 | $ is a perfect square.