Olympiad problems

2012 Indonesia TST, 4

Find all odd prime $p$ such that $1+k(p-1)$ is prime for all integer $k$ where $1 \le k \le \dfrac{p-1}{2}$.

2003 Iran MO (3rd Round), 27

Tags: number theory proposed , number theory

$ S\subset\mathbb N$ is called a square set, iff for each $ x,y\in S$, $ xy\plus{}1$ is square of an integer. a) Is $ S$ finite? b) Find maximum number of elements of $ S$.

1988 India National Olympiad, 2

Tags: number theory proposed , number theory

Prove that the product of 4 consecutive natural numbers cannot be a perfect cube.

2001 Romania Team Selection Test, 1

Tags: algebra , polynomial , number theory proposed , number theory

Let $n$ be a positive integer and $f(x)=a_mx^m+\ldots + a_1X+a_0$, with $m\ge 2$, a polynomial with integer coefficients such that: a) $a_2,a_3\ldots a_m$ are divisible by all prime factors of $n$, b) $a_1$ and $n$ are relatively prime. Prove that for any positive integer $k$, there exists a positive integer $c$, such that $f(c)$ is divisible by $n^k$.

2010 Iran Team Selection Test, 12

Tags: algebra , polynomial , function , number theory proposed , number theory

Prove that for each natural number $m$, there is a natural number $N$ such that for each $b$ that $2\leq b\leq1389$ sum of digits of $N$ in base $b$ is larger than $m$.

2005 Bundeswettbewerb Mathematik, 2

Tags: calculus , number theory proposed , number theory

Let $a$ be such an integer, that $3a$ can be written in the form $x^2 + 2y^2$, with integers $x$ and $y$. Prove that the number $a$ can also be written in this form. [b]Additional problems:[/b] [b]a)[/b] Find a general (necessary and sufficent) criterion for an integer $n$ to be of that form. [b]b)[/b] In how many ways can the integer $n$ be represented in that way?

2003 Baltic Way, 17

Tags: ceiling function , number theory proposed , number theory

All the positive divisors of a positive integer $n$ are stored into an increasing array. Mary is writing a programme which decides for an arbitrarily chosen divisor $d > 1$ whether it is a prime. Let $n$ have $k$ divisors not greater than $d$. Mary claims that it suffices to check divisibility of $d$ by the first $\left\lceil\frac{k}{2}\right\rceil$ divisors of $n$: $d$ is prime if and only if none of them but $1$ divides $d$. Is Mary right?

1977 IMO Longlists, 11

Tags: pigeonhole principle , modular arithmetic , number theory proposed , number theory

Let $n$ and $z$ be integers greater than $1$ and $(n,z)=1$. Prove: (a) At least one of the numbers $z_i=1+z+z^2+\cdots +z^i,\ i=0,1,\ldots ,n-1,$ is divisible by $n$. (b) If $(z-1,n)=1$, then at least one of the numbers $z_i$ is divisible by $n$.

2016 Ukraine Team Selection Test, 4

Tags: induction , modular arithmetic , number theory proposed , number theory

Find all positive integers $a$ such that for any positive integer $n\ge 5$ we have $2^n-n^2\mid a^n-n^a$.

2001 Baltic Way, 17

Tags: number theory proposed , number theory , Combinatorial Number Theory

Let $n$ be a positive integer. Prove that at least $2^{n-1}+n$ numbers can be chosen from the set $\{1, 2, 3,\ldots ,2^n\}$ such that for any two different chosen numbers $x$ and $y$, $x+y$ is not a divisor of $x\cdot y$.

2012 Cono Sur Olympiad, 3

Tags: symmetry , number theory , relatively prime , number theory proposed

3. Show that there do not exist positive integers $a$, $b$, $c$ and $d$, pairwise co-prime, such that $ab+cd$, $ac+bd$ and $ad+bc$ are odd divisors of the number $(a+b-c-d)(a-b+c-d)(a-b-c+d)$.

2000 Korea - Final Round, 1

Tags: floor function , modular arithmetic , quadratics , number theory proposed , number theory

Let $p$ be a prime such that $p \equiv 1 (\text {mod}4)$. Evaluate \[\sum_{k=1}^{p-1} \left( \left \lfloor \frac{2k^2}{p}\right \rfloor - 2 \left \lfloor {\frac{k^2}{p}}\right \rfloor \right)\]

2007 Italy TST, 3

Tags: inequalities , geometry , geometric transformation , reflection , number theory , prime numbers , number theory proposed

Let $p \geq 5$ be a prime. (a) Show that exists a prime $q \neq p$ such that $q| (p-1)^{p}+1$ (b) Factoring in prime numbers $(p-1)^{p}+1 = \prod_{i=1}^{n}p_{i}^{a_{i}}$ show that: \[\sum_{i=1}^{n}p_{i}a_{i}\geq \frac{p^{2}}2 \]

2007 Iran MO (3rd Round), 3

Tags: modular arithmetic , number theory proposed , number theory

Let $ n$ be a natural number, and $ n \equal{} 2^{2007}k\plus{}1$, such that $ k$ is an odd number. Prove that \[ n\not|2^{n\minus{}1}\plus{}1\]

1982 Dutch Mathematical Olympiad, 4

Tags: number theory , greatest common divisor , calculus , integration , number theory proposed

Determine $ \gcd (n^2\plus{}2,n^3\plus{}1)$ for $ n\equal{}9^{753}$.

2011 Regional Competition For Advanced Students, 4

Tags: number theory , least common multiple , induction , number theory proposed

Define the sequence $(a_n)_{n=1}^\infty$ of positive integers by $a_1=1$ and the condition that $a_{n+1}$ is the least integer such that \[\mathrm{lcm}(a_1, a_2, \ldots, a_{n+1})>\mathrm{lcm}(a_1, a_2, \ldots, a_n)\mbox{.}\] Determine the set of elements of $(a_n)$.

2006 Iran MO (3rd Round), 1

Tags: modular arithmetic , abstract algebra , number theory , least common multiple , function , group theory , number theory proposed

$n$ is a natural number. $d$ is the least natural number that for each $a$ that $gcd(a,n)=1$ we know $a^{d}\equiv1\pmod{n}$. Prove that there exist a natural number that $\mbox{ord}_{n}b=d$

2011 Romania Team Selection Test, 4

Tags: number theory proposed , number theory

Show that: a) There are infinitely many positive integers $n$ such that there exists a square equal to the sum of the squares of $n$ consecutive positive integers (for instance, $2$ is one such number as $5^2=3^2+4^2$). b) If $n$ is a positive integer which is not a perfect square, and if $x$ is an integer number such that $x^2+(x+1)^2+...+(x+n-1)^2$ is a perfect square, then there are infinitely many positive integers $y$ such that $y^2+(y+1)^2+...+(y+n-1)^2$ is a perfect square.

2009 Iran MO (2nd Round), 2

Tags: inequalities , induction , number theory proposed , number theory

Let $ a_1<a_2<\cdots<a_n $ be positive integers such that for every distinct $1\leq{i,j}\leq{n}$ we have $ a_j-a_i $ divides $ a_i $. Prove that \[ ia_j\leq{ja_i} \qquad \text{ for } 1\leq{i}<j\leq{n} \]

2000 JBMO ShortLists, 2

Tags: geometry , number theory proposed , number theory

Find all the positive perfect cubes that are not divisible by $10$ such that the number obtained by erasing the last three digits is also a perfect cube.

2010 Contests, 4

Tags: number theory proposed , number theory

Let $r$ be a positive integer and let $N$ be the smallest positive integer such that the numbers $\frac{N}{n+r}\binom{2n}{n}$, $n=0,1,2,\ldots $, are all integer. Show that $N=\frac{r}{2}\binom{2r}{r}$.

2014 China Team Selection Test, 4

Tags: number theory proposed , number theory , Vieta Jumping

Let $k$ be a fixed odd integer, $k>3$. Prove: There exist infinitely many positive integers $n$, such that there are two positive integers $d_1, d_2$ satisfying $d_1,d_2$ each dividing $\frac{n^2+1}{2}$, and $d_1+d_2=n+k$.

2010 Turkey MO (2nd round), 2

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

For integers $a$ and $b$ with $0 \leq a,b < {2010}^{18}$ let $S$ be the set of all polynomials in the form of $P(x)=ax^2+bx.$ For a polynomial $P$ in $S,$ if for all integers n with $0 \leq n <{2010}^{18}$ there exists a polynomial $Q$ in $S$ satisfying $Q(P(n)) \equiv n \pmod {2010^{18}},$ then we call $P$ as a [i]good polynomial.[/i] Find the number of [i]good polynomials.[/i]

2009 Kazakhstan National Olympiad, 1

Tags: number theory proposed , number theory

Prove that for any natural $n \geq 2$, the number $ \underbrace{2^{2^{\cdots^2}}}_{n \textrm{ times}}- \underbrace{2^{2^{\cdots^2}}}_{n-1 \textrm{ times}}$ is divisible by $n$. I know, that it is a very old problem :blush: but it is a problem from olympiad.

2009 Romania Team Selection Test, 3

Tags: quadratics , algebra , polynomial , search , number theory proposed , number theory

Show that there are infinitely many pairs of prime numbers $(p,q)$ such that $p\mid 2^{q-1}-1$ and $q\mid 2^{p-1}-1$.