Olympiad problems

2005 Georgia Team Selection Test, 6

Let $ A$ be the subset of the set of positive integers, having the following $ 2$ properties: 1) If $ a$ belong to $ A$,than all of the divisors of $ a$ also belong to $ A$; 2) If $ a$ and $ b$, $ 1 < a < b$, belong to $ A$, than $ 1 \plus{} ab$ is also in $ A$; Prove that if $ A$ contains at least $ 3$ positive integers, than $ A$ contains all positive integers.

2009 Irish Math Olympiad, 3

Tags: number theory , diophantine equation , modular arithmetic

Find all pairs $(a,b)$ of positive integers such that $(ab)^2 - 4(a+b)$ is the square of an integer.

2007 IMO Shortlist, 3

Tags: combinatorics , counting , triplets , modular arithmetic

Find all positive integers $ n$ for which the numbers in the set $ S \equal{} \{1,2, \ldots,n \}$ can be colored red and blue, with the following condition being satisfied: The set $ S \times S \times S$ contains exactly $ 2007$ ordered triples $ \left(x, y, z\right)$ such that: [b](i)[/b] the numbers $ x$, $ y$, $ z$ are of the same color, and [b](ii)[/b] the number $ x \plus{} y \plus{} z$ is divisible by $ n$. [i]Author: Gerhard Wöginger, Netherlands[/i]

2007 Junior Balkan MO, 4

Tags: quadratic , number theory , modular arithmetic

Prove that if $ p$ is a prime number, then $ 7p+3^{p}-4$ is not a perfect square.

2012 AIME Problems, 1

Tags: modular arithmetic

Find the number of ordered pairs of positive integer solutions $(m,n)$ to the equation $20m+12n=2012.$

2013 Harvard-MIT Mathematics Tournament, 10

Tags: modular arithmetic , hmmt

Let $N$ be a positive integer whose decimal representation contains $11235$ as a contiguous substring, and let $k$ be a positive integer such that $10^k>N$. Find the minimum possible value of \[\dfrac{10^k-1}{\gcd(N,10^k-1)}.\]

2010 AMC 12/AHSME, 23

Tags: number theory , modular arithmetic , polynomial , algebra

The number obtained from the last two nonzero digits of $ 90!$ is equal to $ n$. What is $ n$? $ \textbf{(A)}\ 12 \qquad \textbf{(B)}\ 32 \qquad \textbf{(C)}\ 48 \qquad \textbf{(D)}\ 52 \qquad \textbf{(E)}\ 68$

2012 Korea National Olympiad, 3

Tags: quadratic , modular arithmetic , number theory

Find all triples $(m,p,q)$ where $ m $ is a positive integer and $ p , q $ are primes. \[ 2^m p^2 + 1 = q^5 \]

PEN H Problems, 10

Tags: modular arithmetic , diophantine equation

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

2010 Turkey MO (2nd round), 2

Tags: number theory , modular arithmetic , algebra , polynomial

For integers $a$ and $b$ with $0 \leq a,b < {2010}^{18}$ let $S$ be the set of all polynomials in the form of $P(x)=ax^2+bx.$ For a polynomial $P$ in $S,$ if for all integers n with $0 \leq n <{2010}^{18}$ there exists a polynomial $Q$ in $S$ satisfying $Q(P(n)) \equiv n \pmod {2010^{18}},$ then we call $P$ as a [i]good polynomial.[/i] Find the number of [i]good polynomials.[/i]

2003 Turkey MO (2nd round), 1

Tags: modular arithmetic , greatest common divisor , diophantine equation , number theory

Suppose that $2^{2n+1}+ 2^{n}+1=x^{k}$, where $k\geq2$ and $n$ are positive integers. Find all possible values of $n$.

2009 Indonesia MO, 3

Tags: modular arithmetic , number theory , relatively prime

A pair of integers $ (m,n)$ is called [i]good[/i] if \[ m\mid n^2 \plus{} n \ \text{and} \ n\mid m^2 \plus{} m\] Given 2 positive integers $ a,b > 1$ which are relatively prime, prove that there exists a [i]good[/i] pair $ (m,n)$ with $ a\mid m$ and $ b\mid n$, but $ a\nmid n$ and $ b\nmid m$.

1992 Iran MO (2nd round), 1

Tags: modular arithmetic , number theory

Prove that for any positive integer $t,$ \[1+2^t+3^t+\cdots+9^t - 3(1 + 6^t +8^t )\] is divisible by $18.$

2006 IberoAmerican Olympiad For University Students, 7

Tags: function , algebra , modular arithmetic , search , trigonometry , calculus , integration

Consider the multiplicative group $A=\{z\in\mathbb{C}|z^{2006^k}=1, 0<k\in\mathbb{Z}\}$ of all the roots of unity of degree $2006^k$ for all positive integers $k$. Find the number of homomorphisms $f:A\to A$ that satisfy $f(f(x))=f(x)$ for all elements $x\in A$.

2010 Singapore Senior Math Olympiad, 5

Tags: combinatorics , modular arithmetic

Let $p$ be a prime number and let $a_1,a_2,\dots,a_k$ be distinct integers chosen from $1,2,\dots,p-1$. For $1\le i \le k$, let $f_i^{(n)}$ denote the remainder of the integer $na_1$ upon division by $p$, so $0\le f_i^{(n)}<p$. Define $S=\{n:1\le n \le p-1,f_1^{(n)}<\dots<f_k^{(n)}\}$ Show that $S$ has less than $\frac{2p}{k+1}$ elements.

2009 AMC 12/AHSME, 18

Tags: modular arithmetic , prime factorization , number theory

For $ k>0$, let $ I_k\equal{}10\ldots 064$, where there are $ k$ zeros between the $ 1$ and the $ 6$. Let $ N(k)$ be the number of factors of $ 2$ in the prime factorization of $ I_k$. What is the maximum value of $ N(k)$? $ \textbf{(A)}\ 6\qquad \textbf{(B)}\ 7\qquad \textbf{(C)}\ 8\qquad \textbf{(D)}\ 9\qquad \textbf{(E)}\ 10$

1976 AMC 12/AHSME, 19

Tags: analytic geometry , algorithm , graphing lines , algebra , polynomial , slope , modular arithmetic

A polynomial $p(x)$ has remainder three when divided by $x-1$ and remainder five when divided by $x-3$. The remainder when $p(x)$ is divided by $(x-1)(x-3)$ is $\textbf{(A) }x-2\qquad\textbf{(B) }x+2\qquad\textbf{(C) }2\qquad\textbf{(D) }8\qquad \textbf{(E) }15$

2010 Paenza, 1

Tags: modular arithmetic , number theory

a) Replace each letter in the following sum by a digit from $0$ to $9$, in such a way that the sum is correct. $\tab$ $\tab$ $ABC$ $\tab$ $\tab$ $DEF$ [u]$+GHI$[/u] $\tab$ $\tab$ $\tab$ $J J J$ Different letters must be replaced by different digits, and equal letters must be replaced by equal digits. Numbers $ABC$, $DEF$, $GHI$ and $JJJ$ cannot begin by $0$. b) Determine how many triples of numbers $(ABC,DEF,GHI)$ can be formed under the conditions given in a).

2009 Hanoi Open Mathematics Competitions, 4

Tags: number theory , modular arithmetic

Suppose that $a=2^b$, where $b=2^{10n+1}$. Prove that $a$ is divisible by 23 for any positive integer $n$

2002 Moldova National Olympiad, 1

Tags: modular arithmetic

Integers $ a_1,a_2,\ldots a_9$ satisfy the relations $ a_{k\plus{}1}\equal{}a_k^3\plus{}a_k^2\plus{}a_k\plus{}2$ for $ k\equal{}1,2,...,8$. Prove that among these numbers there exist three with a common divisor greater than $ 1$.

1999 Flanders Math Olympiad, 1

Tags: number theory , modular arithmetic

Determine all 6-digit numbers $(abcdef)$ so that $(abcdef) = (def)^2$ where $\left( x_1x_2...x_n \right)$ is no multiplication but an n-digit number.

2012 IMO Shortlist, N8

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

Prove that for every prime $p>100$ and every integer $r$, there exist two integers $a$ and $b$ such that $p$ divides $a^2+b^5-r$.

2009 Moldova Team Selection Test, 4

Tags: combinatorics , modular arithmetic

[color=darkblue]Let $ X$ be a group of people, where any two people are friends or enemies. Each pair of friends from $ X$ doesn't have any common friends, and any two enemies have exactly two common friends. Prove that each person from $ X$ has the same number of friends as others.[/color]

PEN S Problems, 29

Tags: algorithm , modular arithmetic

What is the rightmost nonzero digit of $1000000!$?

2014 Junior Balkan MO, 1

Tags: modular arithmetic , diophantine equation

Find all triples of primes $(p,q,r)$ satisfying $3p^{4}-5q^{4}-4r^{2}=26$.