Olympiad problems

1989 IberoAmerican, 3

Show that the equation $2x^2-3x=3y^2$ has infinitely many solutions in positive integers.

2010 Germany Team Selection Test, 1

Tags: function , algebra , modular arithmetic , number theory , divisibility

Let $f$ be a non-constant function from the set of positive integers into the set of positive integer, such that $a-b$ divides $f(a)-f(b)$ for all distinct positive integers $a$, $b$. Prove that there exist infinitely many primes $p$ such that $p$ divides $f(c)$ for some positive integer $c$. [i]Proposed by Juhan Aru, Estonia[/i]

2003 National Olympiad First Round, 22

Tags: modular arithmetic

For which of the following integers $n$, there is at least one integer $x$ such that $x^2 \equiv -1 \pmod{n}$? $ \textbf{(A)}\ 97 \qquad\textbf{(B)}\ 98 \qquad\textbf{(C)}\ 99 \qquad\textbf{(D)}\ 100 \qquad\textbf{(E)}\ \text{None of the preceding} $

2010 Polish MO Finals, 2

Tags: modular arithmetic , quadratic , trigonometry , number theory

Prime number $p>3$ is congruent to $2$ modulo $3$. Let $a_k = k^2 + k +1$ for $k=1, 2, \ldots, p-1$. Prove that product $a_1a_2\ldots a_{p-1}$ is congruent to $3$ modulo $p$.

2012 Kosovo Team Selection Test, 1

Tags: modular arithmetic , combinatorics

A student had $18$ papers. He seleced some of these papers, then he cut each of them in $18$ pieces.He took these pieces and selected some of them, which he again cut in $18$ pieces each.The student took this procedure untill he got tired .After a time he counted the pieces and got $2012$ pieces .Prove that the student was wrong during the counting.

1997 Poland - Second Round, 4

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

There is a set with three elements: (2,3,5). It has got an interesting property: (2*3) mod 5=(2*5) mod 3=(3*5) mod 2. Prove that it is the only one set with such property.

2012 ELMO Shortlist, 8

Tags: function , modular arithmetic , induction , functional equation , algebra

Find all functions $f : \mathbb{Q} \to \mathbb{R}$ such that $f(x)f(y)f(x+y) = f(xy)(f(x) + f(y))$ for all $x,y\in\mathbb{Q}$. [i]Sammy Luo and Alex Zhu.[/i]

PEN B Problems, 3

Tags: primitive root , modular arithmetic

Show that for each odd prime $p$, there is an integer $g$ such that $1<g<p$ and $g$ is a primitive root modulo $p^n$ for every positive integer $n$.

2010 AIME Problems, 2

Tags: modular arithmetic

Find the remainder when \[9 \times 99 \times 999 \times \cdots \times \underbrace{99\cdots9}_{\text{999 9's}}\] is divided by $ 1000$.

2003 AMC 10, 25

Tags: modular arithmetic

How many distinct four-digit numbers are divisible by $ 3$ and have $ 23$ as their last two digits? $ \textbf{(A)}\ 27 \qquad \textbf{(B)}\ 30 \qquad \textbf{(C)}\ 33 \qquad \textbf{(D)}\ 81 \qquad \textbf{(E)}\ 90$

1977 USAMO, 1

Tags: algebra , polynomial , modular arithmetic

Determine all pairs of positive integers $ (m,n)$ such that $ (1\plus{}x^n\plus{}x^{2n}\plus{}\cdots\plus{}x^{mn})$ is divisible by $ (1\plus{}x\plus{}x^2\plus{}\cdots\plus{}x^{m})$.

1997 Brazil Team Selection Test, Problem 3

Tags: modular arithmetic , linear algebra , matrix , number theory

Find all positive integers $x>1, y$ and primes $p,q$ such that $p^{x}=2^{y}+q^{x}$

2013 Online Math Open Problems, 20

Tags: modular arithmetic , calculus , integration , number theory , prime factorization

A positive integer $n$ is called [i]mythical[/i] if every divisor of $n$ is two less than a prime. Find the unique mythical number with the largest number of divisors. [i]Proposed by Evan Chen[/i]

2013 USA TSTST, 8

Tags: function , modular arithmetic , induction

Define a function $f: \mathbb N \to \mathbb N$ by $f(1) = 1$, $f(n+1) = f(n) + 2^{f(n)}$ for every positive integer $n$. Prove that $f(1), f(2), \dots, f(3^{2013})$ leave distinct remainders when divided by $3^{2013}$.

1993 IMO Shortlist, 2

Tags: modular arithmetic , number theory , divisibility , prime number , composite number

A natural number $n$ is said to have the property $P,$ if, for all $a, n^2$ divides $a^n - 1$ whenever $n$ divides $a^n - 1.$ a.) Show that every prime number $n$ has property $P.$ b.) Show that there are infinitely many composite numbers $n$ that possess property $P.$

2003 China Team Selection Test, 2

Tags: modular arithmetic , quadratic , number theory

Positive integer $n$ cannot be divided by $2$ and $3$, there are no nonnegative integers $a$ and $b$ such that $|2^a-3^b|=n$. Find the minimum value of $n$.

1984 IMO, 2

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

Find one pair of positive integers $a,b$ such that $ab(a+b)$ is not divisible by $7$, but $(a+b)^7-a^7-b^7$ is divisible by $7^7$.

2014 Bosnia Herzegovina Team Selection Test, 3

Tags: modular arithmetic , number theory

Find all nonnegative integer numbers such that $7^x- 2 \cdot 5^y = -1$

2007 IMO Shortlist, 3

Tags: modular arithmetic , number theory , divisibility , extremal combinatorics , additive combinatorics

Let $ X$ be a set of 10,000 integers, none of them is divisible by 47. Prove that there exists a 2007-element subset $ Y$ of $ X$ such that $ a \minus{} b \plus{} c \minus{} d \plus{} e$ is not divisible by 47 for any $ a,b,c,d,e \in Y.$ [i]Author: Gerhard Wöginger, Netherlands[/i]

2008 APMO, 4

Tags: function , induction , modular arithmetic , algebra , binary representation

Consider the function $ f: \mathbb{N}_0\to\mathbb{N}_0$, where $ \mathbb{N}_0$ is the set of all non-negative integers, defined by the following conditions : $ (i)$ $ f(0) \equal{} 0$; $ (ii)$ $ f(2n) \equal{} 2f(n)$ and $ (iii)$ $ f(2n \plus{} 1) \equal{} n \plus{} 2f(n)$ for all $ n\geq 0$. $ (a)$ Determine the three sets $ L \equal{} \{ n | f(n) < f(n \plus{} 1) \}$, $ E \equal{} \{n | f(n) \equal{} f(n \plus{} 1) \}$, and $ G \equal{} \{n | f(n) > f(n \plus{} 1) \}$. $ (b)$ For each $ k \geq 0$, find a formula for $ a_k \equal{} \max\{f(n) : 0 \leq n \leq 2^k\}$ in terms of $ k$.

2014 Taiwan TST Round 3, 1

Tags: analytic geometry , modular arithmetic , combinatorics

Consider a $6 \times 6$ grid. Define a [i]diagonal[/i] to be the six squares whose coordinates $(i,j)$ ($1 \le i,j \le 6)$ satisfy $i-j \equiv k \pmod 6$ for some $k=0,1,\dots,5$. Hence there are six diagonals. Determine if it is possible to fill it with the numbers $1,2,\dots,36$ (each exactly once) such that each row, each column, and each of the six diagonals has the same sum.

2005 Junior Balkan Team Selection Tests - Romania, 7

Tags: modular arithmetic , combinatorics

A phone company starts a new type of service. A new customer can choose $k$ phone numbers in this network which are call-free, whether that number is calling or is being called. A group of $n$ students want to use the service. (a) If $n\geq 2k+2$, show that there exist 2 students who will be charged when speaking. (b) It $n=2k+1$, show that there is a way to arrange the free calls so that everybody can speak free to anybody else in the group. [i]Valentin Vornicu[/i]

2011 Albania National Olympiad, 2

Tags: euler , modular arithmetic , number theory

Find all the values that can take the last digit of a "perfect" even number. (The natural number $n$ is called "perfect" if the sum of all its natural divisors is equal twice the number itself.For example: the number $6$ is perfect ,because $1+2+3+6=2\cdot6$).

1997 AIME Problems, 1

Tags: modular arithmetic , linear algebra , matrix , geometry , 3d geometry , algebra , difference of squares

How many of the integers between 1 and 1000, inclusive, can be expressed as the difference of the squares of two nonnegative integers?

2009 IMC, 4

Tags: modular arithmetic , polynomial , algebra

Let $p$ be a prime number and $\mathbf{W}\subseteq \mathbb{F}_p[x]$ be the smallest set satisfying the following : [list] (a) $x+1\in \mathbf{W}$ and $x^{p-2}+x^{p-3}+\cdots +x^2+2x+1\in \mathbf{W}$ (b) For $\gamma_1,\gamma_2$ in $\mathbf{W}$, we also have $\gamma(x)\in \mathbf{W}$, where $\gamma(x)$ is the remainder $(\gamma_1\circ \gamma_2)(x)\pmod {x^p-x}$.[/list] How many polynomials are in $\mathbf{W}?$