Olympiad problems

2007 Iran MO (3rd Round), 5

A hyper-primitive root is a k-tuple $ (a_{1},a_{2},\dots,a_{k})$ and $ (m_{1},m_{2},\dots,m_{k})$ with the following property: For each $ a\in\mathbb N$, that $ (a,m) \equal{} 1$, has a unique representation in the following form: \[ a\equiv a_{1}^{\alpha_{1}}a_{2}^{\alpha_{2}}\dots a_{k}^{\alpha_{k}}\pmod{m}\qquad 1\leq\alpha_{i}\leq m_{i}\] Prove that for each $ m$ we have a hyper-primitive root.

2005 IberoAmerican, 3

Tags: modular arithmetic , algebra , number theory , divisibility

Let $p > 3$ be a prime. Prove that if \[ \sum_{i=1 }^{p-1}{1\over i^p} = {n\over m}, \] with $\gdc(n,m) = 1$, then $p^3$ divides $n$.

2006 Germany Team Selection Test, 3

Tags: modular arithmetic , number theory

Is the following statement true? For each positive integer $n$, we can find eight nonnegative integers $a$, $b$, $c$, $d$, $e$, $f$, $g$, $h$ such that $n=\frac{2^a-2^b}{2^c-2^d}\cdot\frac{2^e-2^f}{2^g-2^h}$.

Kvant 2023, M2757

Tags: number theory , modular arithmetic

Let $p{}$ be a prime number. There are $p{}$ integers $a_0,\ldots,a_{p-1}$ around a circle. In one move, it is allowed to select some integer $k{}$ and replace the existing numbers via the operation $a_i\mapsto a_i-a_{i+k}$ where indices are taken modulo $p{}.$ Find all pairs of natural numbers $(m, n)$ with $n>1$ such that for any initial set of $p{}$ numbers, after performing any $m{}$ moves, the resulting $p{}$ numbers will all be divisible by $n{}.$ [i]Proposed by P. Kozhevnikov[/i]

2012 South East Mathematical Olympiad, 1

Tags: modular arithmetic , number theory

A nonnegative integer $m$ is called a “six-composited number” if $m$ and the sum of its digits are both multiples of $6$. How many “six-composited numbers” that are less than $2012$ are there?

1999 Gauss, 12

Tags: gauss , modular arithmetic

Five students named Fred, Gail, Henry, Iggy, and Joan are seated around a circular table in that order. To decide who goes first in a game, they play “countdown”. Henry starts by saying ‘34’, with Iggy saying ‘33’. If they continue to count down in their circular order, who will eventually say ‘1’? $\textbf{(A)}\ \text{Fred} \qquad \textbf{(B)}\ \text{Gail} \qquad \textbf{(C)}\ \text{Henry} \qquad \textbf{(D)}\ \text{Iggy} \qquad \textbf{(E)}\ \text{Joan}$

2012 Romanian Master of Mathematics, 1

Tags: induction , modular arithmetic , graph theory , combinatorics

Given a finite number of boys and girls, a [i]sociable set of boys[/i] is a set of boys such that every girl knows at least one boy in that set; and a [i]sociable set of girls[/i] is a set of girls such that every boy knows at least one girl in that set. Prove that the number of sociable sets of boys and the number of sociable sets of girls have the same parity. (Acquaintance is assumed to be mutual.) [i](Poland) Marek Cygan[/i]

2008 USA Team Selection Test, 9

Tags: algebra , polynomial , 3d geometry , modular arithmetic , algorithm , function , geometry

Let $ n$ be a positive integer. Given an integer coefficient polynomial $ f(x)$, define its [i]signature modulo $ n$[/i] to be the (ordered) sequence $ f(1), \ldots , f(n)$ modulo $ n$. Of the $ n^n$ such $ n$-term sequences of integers modulo $ n$, how many are the signature of some polynomial $ f(x)$ if a) $ n$ is a positive integer not divisible by the square of a prime. b) $ n$ is a positive integer not divisible by the cube of a prime.

2014 Contests, 2

Tags: modular arithmetic , number theory

Find all integers $n$, $n>1$, with the following property: for all $k$, $0\le k < n$, there exists a multiple of $n$ whose digits sum leaves a remainder of $k$ when divided by $n$.

2013 India Regional Mathematical Olympiad, 4

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

A polynomial is called Fermat polynomial if it can be written as the sum of squares of two polynomials with integer coefficients. Suppose that $f(x)$ is a Fermat polynomial such that $f(0)=1000$. Prove that $f(x)+2x$ is not a fermat polynomial

PEN B Problems, 4

Tags: modular arithmetic , primitive root

Let $g$ be a Fibonacci primitive root $\pmod{p}$. i.e. $g$ is a primitive root $\pmod{p}$ satisfying $g^2 \equiv g+1\; \pmod{p}$. Prove that [list=a] [*] $g-1$ is also a primitive root $\pmod{p}$. [*] if $p=4k+3$ then $(g-1)^{2k+3} \equiv g-2 \pmod{p}$, and deduce that $g-2$ is also a primitive root $\pmod{p}$. [/list]

1994 Baltic Way, 18

Tags: modular arithmetic , graph theory , combinatorics

There are $n>2$ lines given in the plane. No two of the lines are parallel and no three of them intersect at one point. Every point of intersection of these lines is labelled with a natural number between $1$ and $n-1$. Prove that, if and only if $n$ is even, it is possible to assign the labels in such a way that every line has all the numbers from $1$ to $n-1$ at its points of intersection with the other $n-1$ lines.

2002 AIME Problems, 4

Tags: modular arithmetic , geometry

Patio blocks that are hexagons $1$ unit on a side are used to outline a garden by placing the blocks edge to edge with $n$ on each side. The diagram indicates the path of blocks around the garden when $n=5.$ [asy] size(250);int i,j; real r=sqrt(3); for(i=0; i<6; i=i+1) { for(j=0; j<4; j=j+1) { draw(shift(((j*r)*dir(60*i+150)).x, ((j*r)*dir(60*i+150)).y)*shift((4r*dir(60i+30)).x,(4r*dir(60i+30)).y)*polygon(6)); }}[/asy] If $n=202,$ then the area of the garden enclosed by the path, not including the path itself, is $m(\sqrt{3}/2)$ square units, where $m$ is a positive integer. Find the remainder when $m$ is divided by $1000.$

2011 Postal Coaching, 5

Tags: modular arithmetic , number theory

Let $(a_n )_{n\ge 1}$ be a sequence of integers that satisﬁes \[a_n = a_{n-1} -\text{min}(a_{n-2} , a_{n-3} )\] for all $n \ge 4$. Prove that for every positive integer $k$, there is an $n$ such that $a_n$ is divisible by $3^k$ .

2001 National Olympiad First Round, 23

Tags: modular arithmetic , number theory , prime number

Which of the followings is false for the sequence $9,99,999,\dots$? $\textbf{(A)}$ The primes which do not divide any term of the sequence are finite. $\textbf{(B)}$ Infinitely many primes divide infinitely many terms of the sequence. $\textbf{(C)}$ For every positive integer $n$, there is a term which is divisible by at least $n$ distinct prime numbers. $\textbf{(D)}$ There is an inteter $n$ such that every prime number greater than $n$ divides infinitely many terms of the sequence. $\textbf{(E)}$ None of above

2013 AIME Problems, 6

Tags: perfect square , modular arithmetic , number theory

Find the least positive integer $N$ such that the set of $1000$ consecutive integers beginning with $1000 \cdot N$ contains no square of an integer.

2011 International Zhautykov Olympiad, 3

Tags: modular arithmetic , induction , number theory , logarithm

Let $\mathbb{N}$ denote the set of all positive integers. An ordered pair $(a;b)$ of numbers $a,b\in\mathbb{N}$ is called [i]interesting[/i], if for any $n\in\mathbb{N}$ there exists $k\in\mathbb{N}$ such that the number $a^k+b$ is divisible by $2^n$. Find all [i]interesting[/i] ordered pairs of numbers.

PEN A Problems, 100

Tags: calculus , integration , modular arithmetic , divisibility theory

Find all positive integers $n$ such that $n$ has exactly $6$ positive divisors $1<d_{1}<d_{2}<d_{3}<d_{4}<n$ and $1+n=5(d_{1}+d_{2}+d_{3}+d_{4})$.

2009 Indonesia TST, 1

Tags: induction , modular arithmetic , number theory

Prove that for all odd $ n > 1$, we have $ 8n \plus{} 4|C^{4n}_{2n}$.

2010 Contests, 4

Tags: modular arithmetic , induction , combinatorics

In a football season, even number $n$ of teams plays a simple series, i.e. each team plays once against each other team. Show that ona can group the series into $n-1$ rounds such that in every round every team plays exactly one match.

PEN A Problems, 41

Tags: modular arithmetic , divisibility theory

Show that there are infinitely many composite numbers $n$ such that $3^{n-1}-2^{n-1}$ is divisible by $n$.

1978 IMO Shortlist, 3

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

Let $ m$ and $ n$ be positive integers such that $ 1 \le m < n$. In their decimal representations, the last three digits of $ 1978^m$ are equal, respectively, to the last three digits of $ 1978^n$. Find $ m$ and $ n$ such that $ m \plus{} n$ has its least value.

2003 Turkey MO (2nd round), 1

Tags: greatest common divisor , modular arithmetic , 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$.

2013 National Olympiad First Round, 2

Tags: modular arithmetic , number theory , prime number

How many triples $(p,q,n)$ are there such that $1/p+2013/q = n/5$ where $p$, $q$ are prime numbers and $n$ is a positive integer? $ \textbf{(A)}\ 7 \qquad\textbf{(B)}\ 6 \qquad\textbf{(C)}\ 5 \qquad\textbf{(D)}\ 4 \qquad\textbf{(E)}\ 4 $

1999 CentroAmerican, 2

Tags: modular arithmetic , number theory

Find a positive integer $n$ with 1000 digits, all distinct from zero, with the following property: it's possible to group the digits of $n$ into 500 pairs in such a way that if the two digits of each pair are multiplied and then add the 500 products, it results a number $m$ that is a divisor of $n$.