Olympiad problems

2001 JBMO ShortLists, 7

Prove that there are are no positive integers $x$ and $y$ such that $x^5+y^5+1=(x+2)^5+(y-3)^5$. [hide="Note"] The restriction $x,y$ are positive isn't necessary.[/hide]

2012 ELMO Shortlist, 5

Tags: quadratic , combinatorics , modular arithmetic

Form the infinite graph $A$ by taking the set of primes $p$ congruent to $1\pmod{4}$, and connecting $p$ and $q$ if they are quadratic residues modulo each other. Do the same for a graph $B$ with the primes $1\pmod{8}$. Show $A$ and $B$ are isomorphic to each other. [i]Linus Hamilton.[/i]

2013 Iran MO (3rd Round), 3

Tags: modular arithmetic , number theory

Let $p>3$ a prime number. Prove that there exist $x,y \in \mathbb Z$ such that $p = 2x^2 + 3y^2$ if and only if $p \equiv 5, 11 \; (\mod 24)$ (20 points)

2010 Hong kong National Olympiad, 3

Tags: number theory , modular arithmetic , floor function

Let $n$ be a positive integer. Let $a$ be an integer such that $\gcd (a,n)=1$. Prove that \[\frac{a^{\phi (n)}-1}{n}=\sum_{i\in R}\frac{1}{ai}\left[\frac{ai}{n}\right]\pmod{n}\] where $R$ is the reduced residue system of $n$ with each element a positive integer at most $n$.

1971 IMO Longlists, 22

Tags: invariant , modular arithmetic , combinatorics

We are given an $n \times n$ board, where $n$ is an odd number. In each cell of the board either $+1$ or $-1$ is written. Let $a_k$ and $b_k$ denote them products of numbers in the $k^{th}$ row and in the $k^{th}$ column respectively. Prove that the sum $a_1 +a_2 +\cdots+a_n +b_1 +b_2 +\cdots+b_n$ cannot be equal to zero.

1999 Romania Team Selection Test, 3

Tags: modular arithmetic , algebra , binomial coefficient , quadratic , special factorizations , floor function , induction

Prove that for any positive integer $n$, the number \[ S_n = {2n+1\choose 0}\cdot 2^{2n}+{2n+1\choose 2}\cdot 2^{2n-2}\cdot 3 +\cdots + {2n+1 \choose 2n}\cdot 3^n \] is the sum of two consecutive perfect squares. [i]Dorin Andrica[/i]

2012 IberoAmerican, 1

Tags: modular arithmetic , strong induction , induction , algebra

Let $a,b,c,d$ be integers such that the number $a-b+c-d$ is odd and it divides the number $a^2-b^2+c^2-d^2$. Show that, for every positive integer $n$, $a-b+c-d$ divides $a^n-b^n+c^n-d^n$.

2010 Contests, 2

Tags: modular arithmetic , algebra , polynomial , number theory

For any set $A=\{a_1,a_2,\cdots,a_m\}$, let $P(A)=a_1a_2\cdots a_m$. Let $n={2010\choose99}$, and let $A_1, A_2,\cdots,A_n$ be all $99$-element subsets of $\{1,2,\cdots,2010\}$. Prove that $2010|\sum^{n}_{i=1}P(A_i)$.

2001 Federal Competition For Advanced Students, Part 2, 1

Tags: floor function , modular arithmetic , algebra

Prove that $\frac{1}{25} \sum_{k=0}^{2001} \left[ \frac{2^k}{25}\right]$ is a positive integer.

2005 MOP Homework, 1

Tags: function , number theory , modular arithmetic , polynomial , parameterization , algebra

Let $n$ be a natural number and $f_1$, $f_2$, ..., $f_n$ be polynomials with integers coeffcients. Show that there exists a polynomial $g(x)$ which can be factored (with at least two terms of degree at least $1$) over the integers such that $f_i(x)+g(x)$ cannot be factored (with at least two terms of degree at least $1$) over the integers for every $i$.

1999 Finnish National High School Mathematics Competition, 1

Tags: number theory , calculus , modular arithmetic , integration

Show that the equation $x^3 + 2y^2 + 4z = n$ has an integral solution $(x, y, z)$ for all integers $n.$

2008 AIME Problems, 15

Tags: number theory , modular arithmetic , intermediate number theory

Find the largest integer $ n$ satisfying the following conditions: (i) $ n^2$ can be expressed as the difference of two consecutive cubes; (ii) $ 2n\plus{}79$ is a perfect square.

2010 Kazakhstan National Olympiad, 4

Tags: modular arithmetic , number theory , geometry

It is given that for some $n \in \mathbb{N}$ there exists a natural number $a$, such that $a^{n-1} \equiv 1 \pmod{n}$ and that for any prime divisor $p$ of $n-1$ we have $a^{\frac{n-1}{p}} \not \equiv 1 \pmod{n}$. Prove that $n$ is a prime.

2002 AMC 10, 24

Tags: number theory , prime factorization , search , modular arithmetic

What is the maximum value of $n$ for which there is a set of distinct positive integers $k_1,k_2,\ldots,k_n$ for which \[k_1^2+k_2^2+\ldots+k_n^2=2002?\] $\textbf{(A) }14\qquad\textbf{(B) }15\qquad\textbf{(C) }16\qquad\textbf{(D) }17\qquad\textbf{(E) }18$

1978 Romania Team Selection Test, 2

Tags: greatest common divisor , gcd , modular arithmetic , number theory

Suppose that $ k,l $ are natural numbers such that $ \gcd (11m-1,k)=\gcd (11m-1, l) , $ for any natural number $ m. $ Prove that there exists an integer $ n $ such that $ k=11^nl. $

2007 China Team Selection Test, 3

Tags: modular arithmetic , euler

Show that there exists a positive integer $ k$ such that $ k \cdot 2^{n} \plus{} 1$ is composite for all $ n \in \mathbb{N}_{0}$.

2001 Putnam, 5

Tags: modular arithmetic

Prove that there are unique positive integers $a$, $n$ such that $a^{n+1}-(a+1)^n=2001$.

2006 National Olympiad First Round, 19

Tags: modular arithmetic

How many real triples $(x,y,z)$ are there such that $x^4+y^4+z^4+1 = 4xyz$? $ \textbf{(A)}\ 0 \qquad\textbf{(B)}\ 4 \qquad\textbf{(C)}\ 6 \qquad\textbf{(D)}\ 10 \qquad\textbf{(E)}\ \text{Infinitely many} $

2005 Taiwan National Olympiad, 2

Tags: modular arithmetic , number theory

$x,y,z,a,b,c$ are positive integers that satisfy $xy \equiv a \pmod z$, $yz \equiv b \pmod x$, $zx \equiv c \pmod y$. Prove that $\min{\{x,y,z\}} \le ab+bc+ca$.

1996 Iran MO (3rd Round), 6

Tags: modular arithmetic , number theory

Find all pairs $(p,q)$ of prime numbers such that \[m^{3pq} \equiv m \pmod{3pq} \qquad \forall m \in \mathbb Z.\]

2009 India Regional Mathematical Olympiad, 6

Tags: modular arithmetic , number theory

In a book with page numbers from $ 1$ to $ 100$ some pages are torn off. The sum of the numbers on the remaining pages is $ 4949$. How many pages are torn off?

2012 Turkey Team Selection Test, 3

Tags: number theory , prime number , modular arithmetic

Let $\mathbb{Z^+}$ and $\mathbb{P}$ denote the set of positive integers and the set of prime numbers, respectively. A set $A$ is called $S-\text{proper}$ where $A, S \subset \mathbb{Z^+}$ if there exists a positive integer $N$ such that for all $a \in A$ and for all $0 \leq b <a$ there exist $s_1, s_2, \ldots, s_n \in S$ satisfying $ b \equiv s_1+s_2+\cdots+s_n \pmod a$ and $1 \leq n \leq N.$ Find a subset $S$ of $\mathbb{Z^+}$ for which $\mathbb{P}$ is $S-\text{proper}$ but $\mathbb{Z^+}$ is not.

1988 IMO Longlists, 85

Tags: invariant , combinatorics , modular arithmetic

Around a circular table an even number of persons have a discussion. After a break they sit again around the circular table in a different order. Prove that there are at least two people such that the number of participants sitting between them before and after a break is the same.

2005 Croatia National Olympiad, 1

Tags: modular arithmetic

Find all possible digits $x, y, z$ such that the number $\overline{13xy45z}$ is divisible by $792.$

2013 Princeton University Math Competition, 3

Tags: modular arithmetic , number theory

Find the smallest positive integer $x$ such that [list] [*] $x$ is $1$ more than a multiple of $3$, [*] $x$ is $3$ more than a multiple of $5$, [*] $x$ is $5$ more than a multiple of $7$, [*] $x$ is $9$ more than a multiple of $11$, and [*] $x$ is $2$ more than a multiple of $13$.[/list]