Olympiad problems

2003 India National Olympiad, 4

Find all $7$-digit numbers which use only the digits $5$ and $7$ and are divisible by $35$.

2007 National Olympiad First Round, 22

Tags: modular arithmetic

Let $n$ and $m$ be integers such that $n\leq 2007 \leq m$ and $n^n \equiv -1 \equiv m^m \pmod 5$. What is the least possible value of $m-n$? $ \textbf{(A)}\ 4 \qquad\textbf{(B)}\ 5 \qquad\textbf{(C)}\ 6 \qquad\textbf{(D)}\ 7 \qquad\textbf{(E)}\ 8 $

2012 Iran Team Selection Test, 1

Tags: modular arithmetic , polynomial , number theory , lucas theorem

Find all positive integers $n \geq 2$ such that for all integers $i,j$ that $ 0 \leq i,j\leq n$ , $i+j$ and $ {n\choose i}+ {n \choose j}$ have same parity. [i]Proposed by Mr.Etesami[/i]

2009 Iran Team Selection Test, 11

Tags: modular arithmetic , number theory

Let $n$ be a positive integer. Prove that \[ 3^{\dfrac{5^{2^n}-1}{2^{n+2}}} \equiv (-5)^{\dfrac{3^{2^n}-1}{2^{n+2}}} \pmod{2^{n+4}}. \]

1986 IMO, 1

Tags: perfect square , quadratic , modular arithmetic , number theory , system of equations

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

2003 Moldova Team Selection Test, 1

Tags: modular arithmetic , ratio , number theory , relatively prime

Each side of an arbitrarly triangle is divided into $ 2002$ congruent segments. After that, each vertex is joined with all "division" points on the opposite side. Prove that the number of the regions formed, in which the triangle is divided, is divisible by $ 6$. [i]Proposer[/i]: [b]Dorian Croitoru[/b]

PEN A Problems, 37

Tags: number theory , greatest common divisor , modular arithmetic , relatively prime , divisibility theory

If $n$ is a natural number, prove that the number $(n+1)(n+2)\cdots(n+10)$ is not a perfect square.

2011 Morocco TST, 1

Tags: modular arithmetic , number theory , equation , lte lemma

Find all pairs $(m,n)$ of nonnegative integers for which \[m^2 + 2 \cdot 3^n = m\left(2^{n+1} - 1\right).\] [i]Proposed by Angelo Di Pasquale, Australia[/i]

MathLinks Contest 7th, 3.1

Tags: modular arithmetic , algebra , polynomial

Let $ p$ be a prime and let $ d \in \left\{0,\ 1,\ \ldots,\ p\right\}$. Prove that \[ \sum_{k \equal{} 0}^{p \minus{} 1}{\binom{2k}{k \plus{} d}}\equiv r \pmod{p}, \]where $ r \equiv p\minus{}d \pmod 3$, $ r\in\{\minus{}1,0,1\}$.

1986 India National Olympiad, 4

Tags: modular arithmetic , algebra , number theory

Find the least natural number whose last digit is 7 such that it becomes 5 times larger when this last digit is carried to the beginning of the number.

2009 Czech and Slovak Olympiad III A, 1

Tags: modular arithmetic , number theory

Knowing that the numbers $p, 3p+2, 5p+4, 7p+6, 9p+8$, and $11p+10$ are all primes, prove that $6p+11$ is a composite number.

2011 National Olympiad First Round, 26

Tags: modular arithmetic

The integers $0 \leq a < 2^{2008}$ and $0 \leq b < 8$ satisfy the equivalence $7(a+2^{2008}b) \equiv 1 \pmod{2^{2011}}$. Then $b$ is $\textbf{(A)}\ 3 \qquad\textbf{(B)}\ 5 \qquad\textbf{(C)}\ 6 \qquad\textbf{(D)}\ 7 \qquad\textbf{(E)}\ \text{None}$

1995 Polish MO Finals, 3

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

Let $p$ be a prime number, and define a sequence by: $x_i=i$ for $i=,0,1,2...,p-1$ and $x_n=x_{n-1}+x_{n-p}$ for $n \geq p$ Find the remainder when $x_{p^3}$ is divided by $p$.

2012 All-Russian Olympiad, 2

Tags: modular arithmetic , number theory

Does there exist natural numbers $a,b,c$ all greater than $10^{10}$ such that their product is divisible by each of these numbers increased by $2012$?

2002 Hong kong National Olympiad, 4

Tags: modular arithmetic , quadratic , number theory

Let $p$ be a prime number such that $p\equiv 1\pmod{4}$. Determine $\sum_{k=1}^{\frac{p-1}{2}}\left \lbrace \frac{k^2}{p} \right \rbrace$, where $\{x\}=x-[x]$.

2004 Manhattan Mathematical Olympiad, 2

Tags: quadratic , modular arithmetic , algebra

Assume $a,b,c$ are odd integers. Show that the quadratic equation \[ ax^2 + bx + c = 0 \] has no rational solutions. (A number is said to be [i]rational[/i], if it can be written as a fraction: $\frac{\text{integer}}{\text{integer}}$.)

2014 Tuymaada Olympiad, 1

Tags: modular arithmetic , greatest common divisor , least common multiple , relatively prime , number theory

Four consecutive three-digit numbers are divided respectively by four consecutive two-digit numbers. What minimum number of different remainders can be obtained? [i](A. Golovanov)[/i]

1990 IMO Longlists, 79

Tags: modular arithmetic , number theory , divisibility , orders and lte

Determine all integers $ n > 1$ such that \[ \frac {2^n \plus{} 1}{n^2} \] is an integer.

2005 IMO Shortlist, 6

Tags: modular arithmetic , number theory , divisibility , chinese remainder theorem

Let $a$, $b$ be positive integers such that $b^n+n$ is a multiple of $a^n+n$ for all positive integers $n$. Prove that $a=b$. [i]Proposed by Mohsen Jamali, Iran[/i]

2006 IMC, 2

Tags: modular arithmetic

Find the number of positive integers x satisfying the following two conditions: 1. $x<10^{2006}$ 2. $x^{2}-x$ is divisible by $10^{2006}$

2005 MOP Homework, 3

Tags: modular arithmetic , number theory

Prove that the equation $a^3-b^3=2004$ does not have any solutions in positive integers.

2006 India IMO Training Camp, 3

Tags: modular arithmetic , invariant , combinatorics

There are $ n$ markers, each with one side white and the other side black. In the beginning, these $ n$ markers are aligned in a row so that their white sides are all up. In each step, if possible, we choose a marker whose white side is up (but not one of the outermost markers), remove it, and reverse the closest marker to the left of it and also reverse the closest marker to the right of it. Prove that, by a finite sequence of such steps, one can achieve a state with only two markers remaining if and only if $ n \minus{} 1$ is not divisible by $ 3$. [i]Proposed by Dusan Dukic, Serbia[/i]

1983 IMO, 3

Tags: modular arithmetic , number theory , frobenius , additive number theory , additive combinatorics

Let $a,b$ and $c$ be positive integers, no two of which have a common divisor greater than $1$. Show that $2abc-ab-bc-ca$ is the largest integer which cannot be expressed in the form $xbc+yca+zab$, where $x,y,z$ are non-negative integers.

2007 IMO Shortlist, 7

Tags: modular arithmetic , number theory , prime factorization , factorial , combinatorial number theory

For a prime $ p$ and a given integer $ n$ let $ \nu_p(n)$ denote the exponent of $ p$ in the prime factorisation of $ n!$. Given $ d \in \mathbb{N}$ and $ \{p_1,p_2,\ldots,p_k\}$ a set of $ k$ primes, show that there are infinitely many positive integers $ n$ such that $ d\mid \nu_{p_i}(n)$ for all $ 1 \leq i \leq k$. [i]Author: Tejaswi Navilarekkallu, India[/i]

2005 Romania Team Selection Test, 1

Tags: geometry , rectangle , modular arithmetic , combinatorics

On a $2004 \times 2004$ chess table there are 2004 queens such that no two are attacking each other\footnote[1]{two queens attack each other if they lie on the same row, column or direction parallel with on of the main diagonals of the table}. Prove that there exist two queens such that in the rectangle in which the center of the squares on which the queens lie are two opposite corners, has a semiperimeter of 2004.