Olympiad problems

1976 AMC 12/AHSME, 15

Tags: modular arithmetic

If $r$ is the remainder when each of the numbers $1059,~1417,$ and $2312$ is divided by $d$, where $d$ is an integer greater than $1$, then $d-r$ equals $\textbf{(A) }1\qquad\textbf{(B) }15\qquad\textbf{(C) }179\qquad\textbf{(D) }d-15\qquad \textbf{(E) }d-1$

2003 China National Olympiad, 1

Tags: modular arithmetic , number theory

Find all integer triples $(a,m,n)$ such that $a^m+1|a^n+203$ where $a,m>1$. [i]Chen Yonggao[/i]

2008 India National Olympiad, 2

Tags: quadratic , modular arithmetic , number theory , equation , diophantine equation

Find all triples $ \left(p,x,y\right)$ such that $ p^x\equal{}y^4\plus{}4$, where $ p$ is a prime and $ x$ and $ y$ are natural numbers.

2004 India IMO Training Camp, 2

Tags: modular arithmetic , number theory

Determine all integers $a$ such that $a^k + 1$ is divisible by $12321$ for some $k$

2011 ELMO Shortlist, 2

Tags: modular arithmetic , number theory

Let $p\ge5$ be a prime. Show that \[\sum_{k=0}^{(p-1)/2}\binom{p}{k}3^k\equiv 2^p - 1\pmod{p^2}.\] [i]Victor Wang.[/i]

1967 IMO Longlists, 38

Tags: modular arithmetic , number theory , perfect cube , diophantine equation

Does there exist an integer such that its cube is equal to $3n^2 + 3n + 7,$ where $n$ is an integer.

2006 China Team Selection Test, 2

Tags: modular arithmetic , number theory

Prove that for any given positive integer $m$ and $n$, there is always a positive integer $k$ so that $2^k-m$ has at least $n$ different prime divisors.

2006 India IMO Training Camp, 1

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

Find all triples $(a,b,c)$ such that $a,b,c$ are integers in the set $\{2000,2001,\ldots,3000\}$ satisfying $a^2+b^2=c^2$ and $\text{gcd}(a,b,c)=1$.

2020 Durer Math Competition Finals, 1

Tags: induction , modular arithmetic , strong induction , relatively prime , prime number , number theory

Show that, for any fixed integer $\,n \geq 1,\,$ the sequence \[ 2, \; 2^2, \; 2^{2^2}, \; 2^{2^{2^2}}, \ldots (\mbox{mod} \; n) \] is eventually constant. [The tower of exponents is defined by $a_1 = 2, \; a_{i+1} = 2^{a_i}$. Also $a_i \; (\mbox{mod} \; n)$ means the remainder which results from dividing $a_i$ by $n$.]

2010 ISI B.Stat Entrance Exam, 2

Tags: modular arithmetic

Let $a,b,c,d$ be distinct digits such that the product of the $2$-digit numbers $\overline{ab}$ and $\overline{cb}$ is of the form $\overline{ddd}$. Find all possible values of $a+b+c+d$.

2013 China National Olympiad, 2

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

For any positive integer $n$ and $0 \leqslant i \leqslant n$, denote $C_n^i \equiv c(n,i)\pmod{2}$, where $c(n,i) \in \left\{ {0,1} \right\}$. Define \[f(n,q) = \sum\limits_{i = 0}^n {c(n,i){q^i}}\] where $m,n,q$ are positive integers and $q + 1 \ne {2^\alpha }$ for any $\alpha \in \mathbb N$. Prove that if $f(m,q)\left| {f(n,q)} \right.$, then $f(m,r)\left| {f(n,r)} \right.$ for any positive integer $r$.

2004 Germany Team Selection Test, 3

Tags: modular arithmetic , number theory , decimal representation , perfect square

Let $ b$ be an integer greater than $ 5$. For each positive integer $ n$, consider the number \[ x_n = \underbrace{11\cdots1}_{n \minus{} 1}\underbrace{22\cdots2}_{n}5, \] written in base $ b$. Prove that the following condition holds if and only if $ b \equal{} 10$: [i]there exists a positive integer $ M$ such that for any integer $ n$ greater than $ M$, the number $ x_n$ is a perfect square.[/i] [i]Proposed by Laurentiu Panaitopol, Romania[/i]

2014 Purple Comet Problems, 24

Tags: modular arithmetic

Let $S=2^3+3^4+5^4+7^4+\cdots+17497^4$ be the sum of the fourth powers of the first $2014$ prime numbers. Find the remainder when $S$ is divided by $240$.

2011 Brazil Team Selection Test, 4

Tags: modular arithmetic , divisibility , number theory

Let $a, b$ be integers, and let $P(x) = ax^3+bx.$ For any positive integer $n$ we say that the pair $(a,b)$ is $n$-good if $n | P(m)-P(k)$ implies $n | m - k$ for all integers $m, k.$ We say that $(a,b)$ is $very \ good$ if $(a,b)$ is $n$-good for infinitely many positive integers $n.$ [list][*][b](a)[/b] Find a pair $(a,b)$ which is 51-good, but not very good. [*][b](b)[/b] Show that all 2010-good pairs are very good.[/list] [i]Proposed by Okan Tekman, Turkey[/i]

2004 Baltic Way, 14

Tags: modular arithmetic , induction , geometry , combinatorics

We say that a pile is a set of four or more nuts. Two persons play the following game. They start with one pile of $n \geq 4$ nuts. During a move a player takes one of the piles that they have and split it into two nonempty sets (these sets are not necessarily piles, they can contain arbitrary number of nuts). If the player cannot move, he loses. For which values of $n$ does the first player have a winning strategy?

2017 Simon Marais Mathematical Competition, B2

Tags: modular arithmetic , diophantine equation , number theory

Find all prime numbers $p,q$, for which $p^{q+1}+q^{p+1}$ is a perfect square. [i]Proposed by P. Boyvalenkov[/i]

2006 IberoAmerican Olympiad For University Students, 7

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

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

2012 Korea National Olympiad, 1

Tags: induction , modular arithmetic , number theory

$ p >3 $ is a prime number such that $ p | 2^{p-1} -1 $ and $ p \not | 2^x - 1 $ for $ x = 1, 2, \cdots , p-2 $. Let $ p = 2k+3 $. Now we define sequence $ \{ a_n \} $ as \[ a_i = a_{i+k}= 2^i ( 1 \le i \le k ) , \ a_{j+2k} = a_j a_{j+k} \ ( j \ge 1 ) \] Prove that there exist $2k$ consecutive terms of sequence $ a_{x+1} , a_{x+2} , \cdots , a_{x+2k} $ such that for all $ 1 \le i < j \le 2k $, $ a_{x+i} \not \equiv a_{x+j} \ (mod \ p) $.

1979 USAMO, 5

Tags: modular arithmetic

A certain organization has $n$ members, and it has $n\plus{}1$ three-member committees, no two of which have identical member-ship. Prove that there are two committees which share exactly one member.

2007 USA Team Selection Test, 4

Tags: modular arithmetic , induction , number theory

Determine whether or not there exist positive integers $ a$ and $ b$ such that $ a$ does not divide $ b^n \minus{} n$ for all positive integers $ n$.

2010 N.N. Mihăileanu Individual, 4

Tags: modular arithmetic , discrete mathematics , square grid , locusts , pigeonhole principle , combinatorics

A square grid is composed of $ n^2\equiv 1\pmod 4 $ unit cells that contained each a locust that jumped the same amount of cells in the direccion of columns or lines, without leaving the grid. Prove that, as a result of this, at least two locusts landed on the same cell. [i]Marius Cavachi[/i]

1983 Dutch Mathematical Olympiad, 2

Tags: modular arithmetic , inequalities

Prove that if $ n$ is an odd positive integer, then the last two digits of $ 2^{2n}(2^{2n\plus{}1}\minus{}1)$ in base $ 10$ are $ 28$.

2009 BMO TST, 3

Tags: function , modular arithmetic , euler , number theory

For the give functions in $\mathbb{N}$: [b](a)[/b] Euler's $\phi$ function ($\phi(n)$- the number of natural numbers smaller than $n$ and coprime with $n$); [b](b)[/b] the $\sigma$ function such that the $\sigma(n)$ is the sum of natural divisors of $n$. solve the equation $\phi(\sigma(2^x))=2^x$.

2006 Finnish National High School Mathematics Competition, 3

Tags: modular arithmetic , number theory

The numbers $p, 4p^2 + 1,$ and $6p^2 + 1$ are primes. Determine $p.$

1977 Germany Team Selection Test, 4

Tags: modular arithmetic , divisibility , digit , decimal representation , digit sum

When $4444^{4444}$ is written in decimal notation, the sum of its digits is $ A.$ Let $B$ be the sum of the digits of $A.$ Find the sum of the digits of $ B.$ ($A$ and $B$ are written in decimal notation.)