Olympiad problems

2001 Junior Balkan Team Selection Tests - Romania, 1

Let $n$ be a non-negative integer. Find all non-negative integers $a,b,c,d$ such that \[a^2+b^2+c^2+d^2=7\cdot 4^n\]

2009 Mexico National Olympiad, 2

Tags: induction , modular arithmetic , number theory

In boxes labeled $0$, $1$, $2$, $\dots$, we place integers according to the following rules: $\bullet$ If $p$ is a prime number, we place it in box $1$. $\bullet$ If $a$ is placed in box $m_a$ and $b$ is placed in box $m_b$, then $ab$ is placed in the box labeled $am_b+bm_a$. Find all positive integers $n$ that are placed in the box labeled $n$.

2013 Korea - Final Round, 5

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

Two coprime positive integers $ a, b $ are given. Integer sequence $ \{ a_n \}, \{b_n \} $ satisties \[ (a+b \sqrt2 )^{2n} = a_n + b_n \sqrt2 \] Find all prime numbers $ p $ such that there exist positive integer $ n \le p $ satisfying $ p | b_n $.

2013 India IMO Training Camp, 1

Tags: modular arithmetic , diophantine equation , number theory

A positive integer $a$ is called a [i]double number[/i] if it has an even number of digits (in base 10) and its base 10 representation has the form $a = a_1a_2 \cdots a_k a_1 a_2 \cdots a_k$ with $0 \le a_i \le 9$ for $1 \le i \le k$, and $a_1 \ne 0$. For example, $283283$ is a double number. Determine whether or not there are infinitely many double numbers $a$ such that $a + 1$ is a square and $a + 1$ is not a power of $10$.

2005 International Zhautykov Olympiad, 1

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

Prove that the equation $ x^{5} \plus{} 31 \equal{} y^{2}$ has no integer solution.

1993 India Regional Mathematical Olympiad, 5

Tags: modular arithmetic

Show that $19^{93} - 13^{99}$ is a positive integer divisible by $162$.

2012 ELMO Shortlist, 1

Tags: modular arithmetic , quadratic , algorithm , number theory

Find all positive integers $n$ such that $4^n+6^n+9^n$ is a square. [i]David Yang, Alex Zhu.[/i]

PEN H Problems, 51

Tags: diophantine equation , modular arithmetic

Prove that the product of five consecutive positive integers is never a perfect square.

1991 IMO Shortlist, 14

Tags: modular arithmetic , number theory , quadratic , perfect square , discriminant

Let $ a, b, c$ be integers and $ p$ an odd prime number. Prove that if $ f(x) \equal{} ax^2 \plus{} bx \plus{} c$ is a perfect square for $ 2p \minus{} 1$ consecutive integer values of $ x,$ then $ p$ divides $ b^2 \minus{} 4ac.$

2005 USAMO, 2

Tags: modular arithmetic , diophantine equation , algebra

Prove that the system \begin{align*} x^6+x^3+x^3y+y & = 147^{157} \\ x^3+x^3y+y^2+y+z^9 & = 157^{147} \end{align*} has no solutions in integers $x$, $y$, and $z$.

2014 NIMO Problems, 1

Tags: function , geometry , 3d geometry , modular arithmetic , number theory , prime factorization , logarithm

Let $\eta(m)$ be the product of all positive integers that divide $m$, including $1$ and $m$. If $\eta(\eta(\eta(10))) = 10^n$, compute $n$. [i]Proposed by Kevin Sun[/i]

2003 Iran MO (3rd Round), 15

Tags: linear algebra , matrix , inequalities , vector , analytic geometry , modular arithmetic

Assume $m\times n$ matrix which is filled with just 0, 1 and any two row differ in at least $n/2$ members, show that $m \leq 2n$. ( for example the diffrence of this two row is only in one index 110 100) [i]Edited by Myth[/i]

2000 Balkan MO, 3

Tags: rectangle , modular arithmetic , geometry

How many $1 \times 10\sqrt 2$ rectangles can be cut from a $50\times 90$ rectangle using cuts parallel to its edges?

2008 IMO Shortlist, 4

Tags: binomial coefficient , number theory , modular arithmetic

Let $ n$ be a positive integer. Show that the numbers \[ \binom{2^n \minus{} 1}{0},\; \binom{2^n \minus{} 1}{1},\; \binom{2^n \minus{} 1}{2},\; \ldots,\; \binom{2^n \minus{} 1}{2^{n \minus{} 1} \minus{} 1}\] are congruent modulo $ 2^n$ to $ 1$, $ 3$, $ 5$, $ \ldots$, $ 2^n \minus{} 1$ in some order. [i]Proposed by Duskan Dukic, Serbia[/i]

2006 Hungary-Israel Binational, 1

Tags: modular arithmetic , induction , number theory

If natural numbers $ x$, $ y$, $ p$, $ n$, $ k$ with $ n > 1$ odd and $ p$ an odd prime satisfy $ x^n \plus{} y^n \equal{} p^k$, prove that $ n$ is a power of $ p$.

PEN A Problems, 72

Tags: modular arithmetic , number theory , divisibility theory

Determine all pairs $(n,p)$ of nonnegative integers such that [list] [*] $p$ is a prime, [*] $n<2p$, [*] $(p-1)^{n} + 1$ is divisible by $n^{p-1}$. [/list]

2015 District Olympiad, 4

Tags: modular arithmetic , number theory , arithmetic

[b]a)[/b] Show that the three last digits of $ 1038^2 $ are equal with $ 4. $ [b]b)[/b] Show that there are infinitely many perfect squares whose last three digits are equal with $ 4. $ [b]c)[/b] Prove that there is no perfect square whose last four digits are equal to $ 4. $

2014 ELMO Shortlist, 6

Tags: modular arithmetic , number theory

Show that the numerator of \[ \frac{2^{p-1}}{p+1} - \left(\sum_{k = 0}^{p-1}\frac{\binom{p-1}{k}}{(1-kp)^2}\right) \] is a multiple of $p^3$ for any odd prime $p$. [i]Proposed by Yang Liu[/i]

2012 Serbia National Math Olympiad, 1

Tags: modular arithmetic , number theory

Find all natural numbers $n$ for which there is a permutation $(p_1,p_2,...,p_n)$ of numbers $(1,2,...,n)$ such that sets $\{p_1 +1, p_2 + 2,..., p_n +n\}$ and $\{p_1-1, p_2-2,...,p_n -n\}$ are complete residue systems $\mod n$.

2011 USA Team Selection Test, 5

Tags: induction , modular arithmetic , function , limit , algebra , polynomial , binomial theorem

Let $c_n$ be a sequence which is defined recursively as follows: $c_0 = 1$, $c_{2n+1} = c_n$ for $n \geq 0$, and $c_{2n} = c_n + c_{n-2^e}$ for $n > 0$ where $e$ is the maximal nonnegative integer such that $2^e$ divides $n$. Prove that \[\sum_{i=0}^{2^n-1} c_i = \frac{1}{n+2} {2n+2 \choose n+1}.\]

PEN E Problems, 20

Tags: modular arithmetic , number theory

Verify that, for each $r \ge 1$, there are infinitely many primes $p$ with $p \equiv 1 \; \pmod{2^r}$.

2009 China Team Selection Test, 3

Tags: modular arithmetic , inequalities , number theory

Prove that for any odd prime number $ p,$ the number of positive integer $ n$ satisfying $ p|n! \plus{} 1$ is less than or equal to $ cp^\frac{2}{3}.$ where $ c$ is a constant independent of $ p.$

2012 ELMO Shortlist, 1

Tags: modular arithmetic , quadratic , algorithm , number theory

Find all positive integers $n$ such that $4^n+6^n+9^n$ is a square. [i]David Yang, Alex Zhu.[/i]

PEN A Problems, 52

Tags: quadratic , modular arithmetic , divisibility theory

Let $d$ be any positive integer not equal to 2, 5, or 13. Show that one can find distinct $a$ and $b$ in the set $\{2,5,13,d\}$ such that $ab - 1$ is not a perfect square.

2014 Tuymaada Olympiad, 8

Tags: calculus , integration , analytic geometry , geometry , modular arithmetic , number theory

Let positive integers $a,\ b,\ c$ be pairwise coprime. Denote by $g(a, b, c)$ the maximum integer not representable in the form $xa+yb+zc$ with positive integral $x,\ y,\ z$. Prove that \[ g(a, b, c)\ge \sqrt{2abc}\] [i](M. Ivanov)[/i] [hide="Remarks (containing spoilers!)"] 1. It can be proven that $g(a,b,c)\ge \sqrt{3abc}$. 2. The constant $3$ is the best possible, as proved by the equation $g(3,3k+1,3k+2)=9k+5$. [/hide]