Olympiad problems

2002 AMC 12/AHSME, 13

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$

1966 IMO Shortlist, 54

Tags: last digit , number theory , decimal representation , digit , modular arithmetic

We take $100$ consecutive natural numbers $a_{1},$ $a_{2},$ $...,$ $a_{100}.$ Determine the last two digits of the number $a_{1}^{8}+a_{2}^{8}+...+a_{100}^{8}.$

PEN H Problems, 59

Tags: diophantine equation , modular arithmetic

Solve the equation $28^x =19^y +87^z$, where $x, y, z$ are integers.

1989 IMO Longlists, 93

Tags: modular arithmetic , number theory , prime number , sequence , power of number

Prove that for each positive integer $ n$ there exist $ n$ consecutive positive integers none of which is an integral power of a prime number.

1988 India National Olympiad, 6

Tags: polynomial , modular arithmetic , algebra

If $ a_0,a_1,\dots,a_{50}$ are the coefficients of the polynomial \[ \left(1\plus{}x\plus{}x^2\right)^{25}\] show that $ a_0\plus{}a_2\plus{}a_4\plus{}\cdots\plus{}a_{50}$ is even.

2009 All-Russian Olympiad, 4

Tags: modular arithmetic , combinatorics

There are n cups arranged on the circle. Under one of cups is hiden a coin. For every move, it is allowed to choose 4 cups and verify if the coin lies under these cups. After that, the cups are returned into its former places and the coin moves to one of two neigbor cups. What is the minimal number of moves we need in order to eventually find where the coin is?

2002 Romania Team Selection Test, 3

Tags: modular arithmetic , number theory

Let $n$ be a positive integer. $S$ is the set of nonnegative integers $a$ such that $1<a<n$ and $a^{a-1}-1$ is divisible by $n$. Prove that if $S=\{ n-1 \}$ then $n=2p$ where $p$ is a prime number. [i]Mihai Cipu and Nicolae Ciprian Bonciocat[/i]

1993 Turkey MO (2nd round), 1

Tags: modular arithmetic

Prove that there is a number such that its decimal represantation ends with 1994 and it can be written as $1994\cdot 1993^{n}$ ($n\in{Z^{+}}$)

1998 India Regional Mathematical Olympiad, 2

Tags: modular arithmetic , number theory , prime number

Let $n$ be a positive integer and $p_1, p_2, p_3, \ldots p_n$ be $n$ prime numbers all larger than $5$ such that $6$ divides $p_1 ^2 + p_2 ^2 + p_3 ^2 + \cdots p_n ^2$. prove that $6$ divides $n$.

2011 Laurențiu Duican, 4

Tags: modular arithmetic , arithmetic , base 10 , combinatorics

Let be two natural numbers $ m\ge n $ and a nonnegative integer $ r<2^n. $ How many numbers of $ m $ digits, each digit being either the number $ 1 $ or $ 2, $ are there whose residue modulo $ 2^n $ is $ r? $ [i]Dorel Miheț[/i]

2011 National Olympiad First Round, 6

Tags: modular arithmetic

For how many primes $p$, $|p^4-86|$ is also prime? $\textbf{(A)}\ 0 \qquad\textbf{(B)}\ 1 \qquad\textbf{(C)}\ 2 \qquad\textbf{(D)}\ 3 \qquad\textbf{(E)}\ 4$

2010 Korea National Olympiad, 4

Tags: modular arithmetic , number theory

There are $ 2010 $ people sitting around a round table. First, we give one person $ x $ a candy. Next, we give candies to $1$ st person, $1+2$ th person, $ 1+2+3$ th person, $\cdots$ , and $1+2+\cdots + 2009 $ th person clockwise from $ x $. Find the number of people who get at least one candy.

2013 AMC 10, 19

Tags: modular arithmetic

In base $10$, the number $2013$ ends in the digit $3$. In base $9$, on the other hand, the same number is written as $(2676)_9$ and ends in the digit $6$. For how many positive integers $b$ does the base-$b$ representation of $2013$ end in the digit $3$? $\textbf{(A) }6\qquad \textbf{(B) }9\qquad \textbf{(C) }13\qquad \textbf{(D) }16\qquad \textbf{(E) }18\qquad$

2009 Putnam, A4

Tags: induction , modular arithmetic , greatest common divisor , quadratic , calculus , integration

Let $ S$ be a set of rational numbers such that (a) $ 0\in S;$ (b) If $ x\in S$ then $ x\plus{}1\in S$ and $ x\minus{}1\in S;$ and (c) If $ x\in S$ and $ x\notin\{0,1\},$ then $ \frac{1}{x(x\minus{}1)}\in S.$ Must $ S$ contain all rational numbers?

2004 Bundeswettbewerb Mathematik, 1

Tags: modular arithmetic , number theory

Let $k$ be a positive integer. A natural number $m$ is called [i]$k$-typical[/i] if each divisor of $m$ leaves the remainder $1$ when being divided by $k$. Prove: [b]a)[/b] If the number of all divisors of a positive integer $n$ (including the divisors $1$ and $n$) is $k$-typical, then $n$ is the $k$-th power of an integer. [b]b)[/b] If $k > 2$, then the converse of the assertion [b]a)[/b] is not true.

2014 Romania Team Selection Test, 2

Tags: induction , modular arithmetic , number theory , algebra

Let $n \ge 2$ be an integer. Show that there exist $n+1$ numbers $x_1, x_2, \ldots, x_{n+1} \in \mathbb{Q} \setminus \mathbb{Z}$, so that $\{ x_1^3 \} + \{ x_2^3 \} + \cdots + \{ x_n^3 \}=\{ x_{n+1}^3 \}$, where $\{ x \}$ is the fractionary part of $x$.

2002 IberoAmerican, 2

Tags: modular arithmetic , invariant , geometry , geometric transformation , reflection , calculus , integration

Given any set of $9$ points in the plane such that there is no $3$ of them collinear, show that for each point $P$ of the set, the number of triangles with its vertices on the other $8$ points and that contain $P$ on its interior is even.

2011 Preliminary Round - Switzerland, 3

Tags: pigeonhole principle , modular arithmetic , combinatorics

On a blackboard, there are $11$ positive integers. Show that one can choose some (maybe all) of these numbers and place "$+$" and "$-$" in between such that the result is divisible by $2011$.

2007 Pre-Preparation Course Examination, 22

Tags: modular arithmetic , number theory

Prove that for any positive integer $n \geq 3$ there exist positive integers $a_1,a_2,\cdots , a_n$ such that \[a_1a_2\cdots a_n \equiv a_i \pmod {a_i^2} \qquad \forall i \in \{1,2,\cdots ,n\}\]

1990 Baltic Way, 15

Tags: geometry , 3d geometry , modular arithmetic , algebra , factorization , difference of cubes , special factorizations

Prove that none of the numbers $2^{2^n}+ 1$, $n = 0, 1, 2, \dots$ is a perfect cube.

2013 China Girls Math Olympiad, 6

Tags: modular arithmetic , combinatorics

Let $S$ be a subset of $\{0,1,2,\ldots,98 \}$ with exactly $m\geq 3$ (distinct) elements, such that for any $x,y\in S$ there exists $z\in S$ satisfying $x+y \equiv 2z \pmod{99}$. Determine all possible values of $m$.

1992 AMC 12/AHSME, 17

Tags: modular arithmetic

The two digit integers from $19$ to $92$ are written consecutively to form the larger integer $N = 19202122\ldots909192$. If $3^{k}$ is the highest power of $3$ that is a factor of $N$, then $k =$ $ \textbf{(A)}\ 0\qquad\textbf{(B)}\ 1\qquad\textbf{(C)}\ 2\qquad\textbf{(D)}\ 3\qquad\textbf{(E)}\ \text{more than 3} $

2005 IMO Shortlist, 5

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]

1972 Canada National Olympiad, 5

Tags: modular arithmetic , euler

Prove that the equation $x^3+11^3=y^3$ has no solution in positive integers $x$ and $y$.

1998 Singapore Team Selection Test, 3

Tags: number theory , modular arithmetic , perfect square , perfect cube , arithmetic sequence

An infinite arithmetic progression whose terms are positive integers contains the square of an integer and the cube of an integer. Show that it contains the sixth power of an integer.