Olympiad problems

2014 All-Russian Olympiad, 1

Call a natural number $n$ [i]good[/i] if for any natural divisor $a$ of $n$, we have that $a+1$ is also divisor of $n+1$. Find all good natural numbers. [i]S. Berlov[/i]

2017 Iran Team Selection Test, 4

Tags: number theory , prime number , modular arithmetic

We arranged all the prime numbers in the ascending order: $p_1=2<p_2<p_3<\cdots$. Also assume that $n_1<n_2<\cdots$ is a sequence of positive integers that for all $i=1,2,3,\cdots$ the equation $x^{n_i} \equiv 2 \pmod {p_i}$ has a solution for $x$. Is there always a number $x$ that satisfies all the equations? [i]Proposed by Mahyar Sefidgaran , Yahya Motevasel[/i]

2012 China Western Mathematical Olympiad, 1

Tags: modular arithmetic , prime number , number theory

Find the smallest positive integer $m$ satisfying the following condition: for all prime numbers $p$ such that $p>3$,have $105|9^{ p^2}-29^p+m.$ (September 28, 2012, Hohhot)

2007 Tuymaada Olympiad, 4

Tags: probability , limit , ratio , greatest common divisor , number theory , prime number , logarithm

Prove that there exists a positive $ c$ such that for every positive integer $ N$ among any $ N$ positive integers not exceeding $ 2N$ there are two numbers whose greatest common divisor is greater than $ cN$.

2018 Latvia Baltic Way TST, P16

Tags: prime number , number theory

Call a natural number [i]simple[/i] if it is not divisible by any square of a prime number (in other words it is square-free). Prove that there are infinitely many positive integers $n$ such that both $n$ and $n+1$ are [i]simple[/i].

2015 JBMO Shortlist, NT4

Tags: prime number , number theory

Find all prime numbers $a,b,c$ and positive integers $k$ satisfying the equation \[a^2+b^2+16c^2 = 9k^2 + 1.\] Proposed by Moldova

2009 Purple Comet Problems, 13

Tags: prime number , number theory

How many subsets of the set $\{1, 2, 3, \ldots, 12\}$ contain exactly one or two prime numbers?

2018 Mediterranean Mathematics OIympiad, 3

Tags: number theory , prime number

An integer $a\ge1$ is called [i]Aegean[/i], if none of the numbers $a^{n+2}+3a^n+1$ with $n\ge1$ is prime. Prove that there are at least 500 Aegean integers in the set $\{1,2,\ldots,2018\}$. (Proposed by Gerhard Woeginger, Austria)

2023 Poland - Second Round, 6

Tags: number theory , prime number , combinatorics , chessboard

Given a chessboard $n \times n$, where $n\geq 4$ and $p=n+1$ is a prime number. A set of $n$ unit squares is called [i]tactical[/i] if after putting down queens on these squares, no two queens are attacking each other. Prove that there exists a partition of the chessboard into $n-2$ tactical sets, not containing squares on the main diagonals. Queens are allowed to move horizontally, vertically and diagonally.

2022 Singapore MO Open, Q5

Tags: number theory , polynomial , modulo , prime number , algebra

Let $n\ge 2$ be a positive integer. For any integer $a$, let $P_a(x)$ denote the polynomial $x^n+ax$. Let $p$ be a prime number and define the set $S_a$ as the set of residues mod $p$ that $P_a(x)$ attains. That is, $$S_a=\{b\mid 0\le b\le p-1,\text{ and there is }c\text{ such that }P_a(c)\equiv b \pmod{p}\}.$$Show that the expression $\frac{1}{p-1}\sum\limits_{a=1}^{p-1}|S_a|$ is an integer. [i]Proposed by fattypiggy123[/i]

2013 Taiwan TST Round 1, 1

Tags: number theory , prime , prime number

Starting from 37, adding 5 before each previous term, forms the following sequence: \[37,537,5537,55537,555537,...\] How many prime numbers are there in this sequence?

2023 Germany Team Selection Test, 3

Tags: polynomial , number theory , prime number , algebra

Let $f(x)$ be a monic polynomial of degree $2023$ with positive integer coefficients. Show that for any sufficiently large integer $N$ and any prime number $p>2023N$, the product \[f(1)f(2)\dots f(N)\] is at most $\binom{2023}{2}$ times divisible by $p$. [i]Proposed by Ashwin Sah[/i]

Russian TST 2015, P1

Tags: number theory , prime number

Prove that there exist two natural numbers $a,b$ such that $|a-m|+|b-n|>1000$ for any relatively prime natural numbers $m,n$.

STEMS 2023 Math Cat A, 8

Tags: prime number , computational , algebra

For how many pairs of primes $(p, q)$, is $p^2 + 2pq^2 + 1$ also a prime?

2006 Germany Team Selection Test, 1

Tags: prime number , number theory

Does there exist a natural number $n$ in whose decimal representation each digit occurs at least $2006$ times and which has the property that you can find two different digits in its decimal representation such that the number obtained from $n$ by interchanging these two digits is different from $n$ and has the same set of prime divisors as $n$ ?

2019 Singapore MO Open, 4

Tags: number theory , prime number , polynomial , algebra

Let $p \equiv 2 \pmod 3$ be a prime, $k$ a positive integer and $P(x) = 3x^{\frac{2p-1}{3}}+3x^{\frac{p+1}{3}}+x+1$. For any integer $n$, let $R(n)$ denote the remainder when $n$ is divided by $p$ and let $S = \{0,1,\cdots,p-1\}$. At each step, you can either (a) replaced every element $i$ of $S$ with $R(P(i))$ or (b) replaced every element $i$ of $S$ with $R(i^k)$. Determine all $k$ such that there exists a finite sequence of steps that reduces $S$ to $\{0\}$. [i]Proposed by fattypiggy123[/i]

2002 AMC 12/AHSME, 12

Tags: quadratic , vieta , algebra , number theory , prime number , special factorizations

Both roots of the quadratic equation $ x^2 \minus{} 63x \plus{} k \equal{} 0$ are prime numbers. The number of possible values of $ k$ is $ \textbf{(A)}\ 0 \qquad \textbf{(B)}\ 1 \qquad \textbf{(C)}\ 2 \qquad \textbf{(D)}\ 3 \qquad \textbf{(E)}\ \textbf{more than four}$

2014 IMO Shortlist, C4

Tags: combinatorics , algebra , prime number

Construct a tetromino by attaching two $2 \times 1$ dominoes along their longer sides such that the midpoint of the longer side of one domino is a corner of the other domino. This construction yields two kinds of tetrominoes with opposite orientations. Let us call them $S$- and $Z$-tetrominoes, respectively. Assume that a lattice polygon $P$ can be tiled with $S$-tetrominoes. Prove that no matter how we tile $P$ using only $S$- and $Z$-tetrominoes, we always use an even number of $Z$-tetrominoes. [i]Proposed by Tamas Fleiner and Peter Pal Pach, Hungary[/i]

2022 IMO Shortlist, N6

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

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

2014 All-Russian Olympiad, 1

2017 Iran Team Selection Test, 4

2012 China Western Mathematical Olympiad, 1

2007 Tuymaada Olympiad, 4

2018 Latvia Baltic Way TST, P16

2015 JBMO Shortlist, NT4

2009 Purple Comet Problems, 13

2018 Mediterranean Mathematics OIympiad, 3

2023 Poland - Second Round, 6

2022 Singapore MO Open, Q5

2013 Taiwan TST Round 1, 1

2023 Germany Team Selection Test, 3

Russian TST 2015, P1

STEMS 2023 Math Cat A, 8

2006 Germany Team Selection Test, 1

2019 Singapore MO Open, 4

2002 AMC 12/AHSME, 12

2014 IMO Shortlist, C4

2022 IMO Shortlist, N6

2013 All-Russian Olympiad, 3

2012 National Olympiad First Round, 26

1984 All Soviet Union Mathematical Olympiad, 386

2020 Turkey MO (2nd round), 4

2010 Singapore MO Open, 3

2016 Croatia Team Selection Test, Problem 4