Olympiad problems

2004 Iran MO (2nd round), 4

$\mathbb{N}$ is the set of positive integers. Determine all functions $f:\mathbb{N}\to\mathbb{N}$ such that for every pair $(m,n)\in\mathbb{N}^2$ we have that: \[f(m)+f(n) \ | \ m+n .\]

2021/2022 Tournament of Towns, P1

Tags: prime number , number theory

Let us call a positive integer $k{}$ interesting if the product of the first $k{}$ primes is divisible by $k{}$. For example the product of the first two primes is $2\cdot3 = 6$, it is divisible by 2, hence 2 is an interesting integer. What is the maximal possible number of consecutive interesting integers? [i]Boris Frenkin[/i]

2010 China Team Selection Test, 2

Tags: factorial , prime number , number theory

Prove that there exists a sequence of unbounded positive integers $a_1\leq a_2\leq a_3\leq\cdots$, such that there exists a positive integer $M$ with the following property: for any integer $n\geq M$, if $n+1$ is not prime, then any prime divisor of $n!+1$ is greater than $n+a_n$.

2022 IMO Shortlist, N6

Tags: prime , prime number , number theory , prime factorization , function

Let $Q$ be a set of prime numbers, not necessarily finite. For a positive integer $n$ consider its prime factorization: define $p(n)$ to be the sum of all the exponents and $q(n)$ to be the sum of the exponents corresponding only to primes in $Q$. A positive integer $n$ is called [i]special[/i] if $p(n)+p(n+1)$ and $q(n)+q(n+1)$ are both even integers. Prove that there is a constant $c>0$ independent of the set $Q$ such that for any positive integer $N>100$, the number of special integers in $[1,N]$ is at least $cN$. (For example, if $Q=\{3,7\}$, then $p(42)=3$, $q(42)=2$, $p(63)=3$, $q(63)=3$, $p(2022)=3$, $q(2022)=1$.)

1987 Czech and Slovak Olympiad III A, 2

Tags: number of solutions , diophantine equation , prime number , number theory

Given a prime $p>3$ and an odd integer $n>0$, show that the equation $$xyz=p^n(x+y+z)$$ has at least $3(n+1)$ different solutions up to symmetry. (That is, if $(x',y',z')$ is a solution and $(x'',y'',z'')$ is a permutation of the previous, they are considered to be the same solution.)

2010 Contests, 1

Tags: prime number , number theory

$a)$ Let $p$ and $q$ be distinct prime numbers such that $p+q^2$ divides $p^2+q$. Prove that $p+q^2$ divides $pq-1$. $b)$ Find all prime numbers $p$ such that $p+121$ divides $p^2+11$.

2014 Romania Team Selection Test, 4

Tags: prime number , number theory , relatively prime , induction , function

Let $f$ be the function of the set of positive integers into itself, defined by $f(1) = 1$, $f(2n) = f(n)$ and $f(2n + 1) = f(n) + f(n + 1)$. Show that, for any positive integer $n$, the number of positive odd integers m such that $f(m) = n$ is equal to the number of positive integers[color=#0000FF][b] less or equal to [/b][/color]$n$ and coprime to $n$. [color=#FF0000][mod: the initial statement said less than $n$, which is wrong.][/color]

2017 Junior Balkan Team Selection Tests - Romania, 1

Tags: prime number , number theory

Let $n$ and $k$ be two positive integers such that $1\leq n \leq k$. Prove that, if $d^k+k$ is a prime number for each positive divisor $d$ of $n$, then $n+k$ is a prime number.

2016 Korea Summer Program Practice Test, 3

Tags: primitive root , prime number , decimal representation , number theory , prime

Let $p > 10^9$ be a prime number such that $4p + 1$ is also prime. Prove that the decimal expansion of $\frac{1}{4p+1}$ contains all the digits $0,1, \ldots, 9$.

2022 IMC, 6

Tags: prime number , number theory , modular arithmetic

Let $p \geq 3$ be a prime number. Prove that there is a permutation $(x_1,\ldots, x_{p-1})$ of $(1,2,\ldots,p-1)$ such that $x_1x_2 + x_2x_3 + \cdots + x_{p-2}x_{p-1} \equiv 2 \pmod p$.

1973 AMC 12/AHSME, 18

Tags: prime number , number theory , probability , modular arithmetic

If $ p \geq 5$ is a prime number, then $ 24$ divides $ p^2 \minus{} 1$ without remainder $ \textbf{(A)}\ \text{never} \qquad \textbf{(B)}\ \text{sometimes only} \qquad \textbf{(C)}\ \text{always} \qquad$ $ \textbf{(D)}\ \text{only if } p \equal{}5 \qquad \textbf{(E)}\ \text{none of these}$

2022 Kazakhstan National Olympiad, 2

Tags: prime number , number theory

Given a prime number $p$. It is known that for each integer $a$ such that $1<a<p/2$ there exist integer $b$ such that $p/2<b<p$ and $p|ab-1$. Find all such $p$.

2017 Romania National Olympiad, 4

Tags: digit , prime number , prime , number theory

Find all prime numbers with $n \ge 3$ digits, having the property: for every $k \in \{1, 2, . . . , n -2\}$, deleting any $k$ of its digits leaves a prime number.

2000 Taiwan National Olympiad, 1

Tags: euler , quadratic , prime number , number theory , modular arithmetic , function

Suppose that for some $m,n\in\mathbb{N}$ we have $\varphi (5^m-1)=5^n-1$, where $\varphi$ denotes the Euler function. Show that $(m,n)>1$.

2020 Federal Competition For Advanced Students, P2, 3

Tags: prime number , sequence , number theory

Let $a$ be a fixed positive integer and $(e_n)$ the sequence, which is defined by $e_0=1$ and $$ e_n=a + \prod_{k=0}^{n-1} e_k$$ for $n \geq 1$. Prove that (a) There exist infinitely many prime numbers that divide one element of the sequence. (b) There exists one prime number that does not divide an element of the sequence. (Theresia Eisenkölbl)

2021 2nd Memorial "Aleksandar Blazhevski-Cane", 2

Tags: prime number , number theory

Let $p$ be a prime number and $F=\left \{0,1,2,...,p-1 \right \}$. Let $A$ be a proper subset of $F$ that satisfies the following property: if $a,b \in A$, then $ab+1$ (mod $p$) $ \in A$. How many elements can $A$ have? (Justify your answer.)

2010 India IMO Training Camp, 8

Tags: prime number , number theory

Call a positive integer [b]good[/b] if either $N=1$ or $N$ can be written as product of [i]even[/i] number of prime numbers, not necessarily distinct. Let $P(x)=(x-a)(x-b),$ where $a,b$ are positive integers. (a) Show that there exist distinct positive integers $a,b$ such that $P(1),P(2),\cdots ,P(2010)$ are all good numbers. (b) Suppose $a,b$ are such that $P(n)$ is a good number for all positive integers $n$. Prove that $a=b$.

2021 Serbia Team Selection Test, P3

Tags: system of equations , prime number , diophantine equation , number theory

Given is a prime number $p$. Find the number of positive integer solutions $(a, b, c, d)$ of the system of equations $ac+bd = p(a+c)$ and $bc-ad = p(b-d)$.

2020 ITAMO, 5

Tags: prime number , function , number theory

Le $S$ be the set of positive integers greater than or equal to $2$. A function $f: S\rightarrow S$ is italian if $f$ satifies all the following three conditions: 1) $f$ is surjective 2) $f$ is increasing in the prime numbers(that is, if $p_1<p_2$ are prime numbers, then $f(p_1)<f(p_2)$) 3) For every $n\in S$ the number $f(n)$ is the product of $f(p)$, where $p$ varies among all the primes which divide $n$ (For instance, $f(360)=f(2^3\cdot 3^2\cdot 5)=f(2)\cdot f(3)\cdot f(5)$). Determine the maximum and the minimum possible value of $f(2020)$, when $f$ varies among all italian functions.

1987 IMO, 3

Tags: prime number , polynomial , number theory , algebra

Let $n\ge2$ be an integer. Prove that if $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le\sqrt{n\over3}$, then $k^2+k+n$ is prime for all integers $k$ such that $0\le k\le n-2$.

2011 Bosnia And Herzegovina - Regional Olympiad, 2

Tags: prime number , number theory

If $p>2$ is prime number and $m$ and $n$ are positive integers such that $$\frac{m}{n}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{p-1}$$ Prove that $p$ divides $m$

2017 India PRMO, 23

Tags: prime number , algebra , number theory

Suppose an integer $x$, a natural number $n$ and a prime number $p$ satisfy the equation $7x^2-44x+12=p^n$. Find the largest value of $p$.

2019 Switzerland Team Selection Test, 4

Tags: prime number , number theory , polynomial , algebra

Let $p$ be a prime number. Find all polynomials $P$ with integer coefficients with the following properties: $(a)$ $P(x)>x$ for all positive integers $x$. $(b)$ The sequence defined by $p_0:=p$, $p_{n+1}:=P(p_n)$ for all positive integers $n$, satisfies the property that for all positive integers $m$ there exists some $l\geq 0$ such that $m\mid p_l$.

PEN C Problems, 4

Tags: inequalities , quadratic , prime number , quadratic residue , number theory , floor function

Let $M$ be an integer, and let $p$ be a prime with $p>25$. Show that the set $\{M, M+1, \cdots, M+ 3\lfloor \sqrt{p} \rfloor -1\}$ contains a quadratic non-residue to modulus $p$.

2002 Turkey MO (2nd round), 1

Tags: quadratic , prime number , modular arithmetic , number theory

Find all prime numbers $p$ for which the number of ordered pairs of integers $(x, y)$ with $0\leq x, y < p$ satisfying the condition \[y^2 \equiv x^3 - x \pmod p\] is exactly $p.$