Olympiad problems

2015 China Team Selection Test, 3

Let $a,b$ be two integers such that their gcd has at least two prime factors. Let $S = \{ x \mid x \in \mathbb{N}, x \equiv a \pmod b \} $ and call $ y \in S$ irreducible if it cannot be expressed as product of two or more elements of $S$ (not necessarily distinct). Show there exists $t$ such that any element of $S$ can be expressed as product of at most $t$ irreducible elements.

2013 India Regional Mathematical Olympiad, 4

Tags: modular arithmetic , combinatorics

Find the number of $10$-tuples $(a_1,a_2,\dots,a_9,a_{10})$ of integers such that $|a_1|\leq 1$ and \[a_1^2+a_2^2+a_3^2+\cdots+a_{10}^2-a_1a_2-a_2a_3-a_3a_4-\cdots-a_9a_{10}-a_{10}a_1=2.\]

PEN J Problems, 11

Tags: function , modular arithmetic , inequalities , induction , floor function , number theory , logarithm

Prove that ${d((n^2 +1)}^2)$ does not become monotonic from any given point onwards.

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.$

2014 District Olympiad, 4

Tags: modular arithmetic , number theory , combinatorics

A $10$ digit positive integer is called a $\emph{cute}$ number if its digits are from the set $\{1,2,3\}$ and every two consecutive digits differ by $1$. [list=a] [*]Prove that exactly $5$ digits of a cute number are equal to $2$. [*]Find the total number of cute numbers. [*]Prove that the sum of all cute numbers is divisible by $1408$.[/list]

1989 APMO, 2

Tags: modular arithmetic , greatest common divisor , number theory

Prove that the equation \[ 6(6a^2 + 3b^2 + c^2) = 5n^2 \] has no solutions in integers except $a = b = c = n = 0$.

2023 Bosnia and Herzegovina Junior BMO TST, 2.

Tags: modular arithmetic , number theory

Determine all non negative integers $x$ and $y$ such that $6^x$ + $2^y$ + 2 is a perfect square.

2007 India IMO Training Camp, 2

Tags: modular arithmetic , diophantine equation , number theory

Find all integer solutions $(x,y)$ of the equation $y^2=x^3-p^2x,$ where $p$ is a prime such that $p\equiv 3 \mod 4.$

1983 Vietnam National Olympiad, 1

Tags: modular arithmetic , greatest common divisor , number theory

Are there positive integers $a, b$ with $b \ge 2$ such that $2^a + 1$ is divisible by $2^b - 1$?

1994 Baltic Way, 6

Tags: modular arithmetic , number theory

Prove that any irreducible fraction $p/q$, where $p$ and $q$ are positive integers and $q$ is odd, is equal to a fraction $\frac{n}{2^k-1}$ for some positive integers $n$ and $k$.

the 14th XMO, P4

Tags: combinatorics , modular arithmetic , grid

In an $n$ by $n$ grid, each cell is filled with an integer between $1$ and $6$. The outmost cells all contain the number $1$, and any two cells that share a vertex has difference not equal to $3$. For any vertex $P$ inside the grid (not including the boundary), there are $4$ cells that have $P$ has a vertex. If these four cells have exactly three distinct numbers $i$, $j$, $k$ (two cells have the same number), and the two cells with the same number have a common side, we call $P$ an $ijk$-type vertex. Let there be $A_{ijk}$ vertices that are $ijk$-type. Prove that $A_{123}\equiv A_{246} \pmod 2$.

2013 Moldova Team Selection Test, 1

Tags: modular arithmetic , number theory

Let $A=20132013...2013$ be formed by joining $2013$, $165$ times. Prove that $2013^2 \mid A$.

2002 AIME Problems, 12

Tags: modular arithmetic , function , complex number

Let $F(z)=\frac{z+i}{z-i}$ for all complex numbers $z\not= i,$ and let $z_n=F(z_{n-1})$ for all positive integers $n.$ Given that $z_0=\frac 1{137}+i$ and $z_{2002}=a+bi,$ where $a$ and $b$ are real numbers, find $a+b.$

1975 IMO, 2

Tags: modular arithmetic , number theory , sequence , additive number theory

Let $a_{1}, \ldots, a_{n}$ be an infinite sequence of strictly positive integers, so that $a_{k} < a_{k+1}$ for any $k.$ Prove that there exists an infinity of terms $ a_{m},$ which can be written like $a_m = x \cdot a_p + y \cdot a_q$ with $x,y$ strictly positive integers and $p \neq q.$

2005 IMO Shortlist, 4

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

Find all positive integers $ n$ such that there exists a unique integer $ a$ such that $ 0\leq a < n!$ with the following property: \[ n!\mid a^n \plus{} 1 \] [i]Proposed by Carlos Caicedo, Colombia[/i]

2012 India IMO Training Camp, 2

Tags: modular arithmetic , inequalities , number theory

Let $0<x<y<z<p$ be integers where $p$ is a prime. Prove that the following statements are equivalent: $(a) x^3\equiv y^3\pmod p\text{ and }x^3\equiv z^3\pmod p$ $(b) y^2\equiv zx\pmod p\text{ and }z^2\equiv xy\pmod p$

2005 Danube Mathematical Olympiad, 4

Tags: geometry , rectangle , modular arithmetic , combinatorics

Let $k$ and $n$ be positive integers. Consider an array of $2\left(2^n-1\right)$ rows by $k$ columns. A $2$-coloring of the elements of the array is said to be [i]acceptable[/i] if any two columns agree on less than $2^n-1$ entries on the same row. Given $n$, determine the maximum value of $k$ for an acceptable $2$-coloring to exist.

2005 Romania Team Selection Test, 1

Tags: induction , modular arithmetic , number theory

Solve the equation $3^x=2^xy+1$ in positive integers.

1993 Korea - Final Round, 3

Tags: modular arithmetic , number theory

Find the smallest $x \in\mathbb{N}$ for which $\frac{7x^{25}-10}{83}$ is an integer.

2002 Tournament Of Towns, 3

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

Show that if the last digit of the number $x^2+xy+y^2$ is $0$ (where $x,y\in\mathbb{N}$ ) then last two digits are zero.

2010 ELMO Shortlist, 5

Tags: modular arithmetic , number theory

Find the set $S$ of primes such that $p \in S$ if and only if there exists an integer $x$ such that $x^{2010} + x^{2009} + \cdots + 1 \equiv p^{2010} \pmod{p^{2011}}$. [i]Brian Hamrick.[/i]

2003 Manhattan Mathematical Olympiad, 4

Tags: algebra , polynomial , modular arithmetic , number theory

Let $p$ and $a$ be positive integer numbers having no common divisors except of $1$. Prove that $p$ is prime if and only if all the coefficients of the polynomial \[ F(x) = (x-a)^p - (x^p - a) \] are divisible by $p$.

1982 USAMO, 4

Tags: modular arithmetic , number theory

Prove that there exists a positive integer $k$ such that $k\cdot2^n+1$ is composite for every integer $n$.

PEN O Problems, 19

Tags: modular arithmetic

Let $m, n \ge 2$ be positive integers, and let $a_{1}, a_{2}, \cdots,a_{n}$ be integers, none of which is a multiple of $m^{n-1}$. Show that there exist integers $e_{1}, e_{2}, \cdots, e_{n}$, not all zero, with $\vert e_i \vert<m$ for all $i$, such that $e_{1}a_{1}+e_{2}a_{2}+ \cdots +e_{n}a_{n}$ is a multiple of $m^n$.

2011 Iran MO (3rd Round), 5

Tags: modular arithmetic , number theory

Suppose that $k$ is a natural number. Prove that there exists a prime number in $\mathbb Z_{[i]}$ such that every other prime number in $\mathbb Z_{[i]}$ has a distance at least $k$ with it.