Olympiad problems

PEN R Problems, 4

The sidelengths of a polygon with $1994$ sides are $a_{i}=\sqrt{i^2 +4}$ $ \; (i=1,2,\cdots,1994)$. Prove that its vertices are not all on lattice points.

2011 IMO, 5

Tags: function , symmetry , modular arithmetic , number theory

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers $m$ and $n$, the difference $f(m) - f(n)$ is divisible by $f(m- n)$. Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$, the number $f(n)$ is divisible by $f(m)$. [i]Proposed by Mahyar Sefidgaran, Iran[/i]

2012 Indonesia TST, 4

Tags: greatest common divisor , modular arithmetic , number theory

Determine all integer $n > 1$ such that \[\gcd \left( n, \dfrac{n-m}{\gcd(n,m)} \right) = 1\] for all integer $1 \le m < n$.

2011 Lusophon Mathematical Olympiad, 2

Tags: modular arithmetic , inequalities , number theory

A non-negative integer $n$ is said to be [i]squaredigital[/i] if it equals the square of the sum of its digits. Find all non-negative integers which are squaredigital.

2015 Switzerland Team Selection Test, 12

Tags: modular arithmetic , probability , function , ratio , number theory

Given positive integers $m$ and $n$, prove that there is a positive integer $c$ such that the numbers $cm$ and $cn$ have the same number of occurrences of each non-zero digit when written in base ten.

2005 AMC 8, 20

Tags: number theory , least common multiple , modular arithmetic

Alice and Bob play a game involving a circle whose circumference is divided by 12 equally-spaced points. The points are numbered clockwise, from 1 to 12. Both start on point 12. Alice moves clockwise and Bob, counterclockwise. In a turn of the game, Alice moves 5 points clockwise and Bob moves 9 points counterclockwise. The game ends when they stop on the same point. How many turns will this take? $ \textbf{(A)}\ 6\qquad\textbf{(B)}\ 8\qquad\textbf{(C)}\ 12\qquad\textbf{(D)}\ 14\qquad\textbf{(E)}\ 24 $

2003 Italy TST, 1

Tags: modular arithmetic , number theory

Find all triples of positive integers $(a,b,p)$ with $a,b$ positive integers and $p$ a prime number such that $2^a+p^b=19^a$

2008 China National Olympiad, 3

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

Find all triples $(p,q,n)$ that satisfy \[q^{n+2} \equiv 3^{n+2} (\mod p^n) ,\quad p^{n+2} \equiv 3^{n+2} (\mod q^n)\] where $p,q$ are odd primes and $n$ is an positive integer.

2013 ELMO Shortlist, 2

Tags: algebra , polynomial , geometry , 3d geometry , modular arithmetic , number theory

For what polynomials $P(n)$ with integer coefficients can a positive integer be assigned to every lattice point in $\mathbb{R}^3$ so that for every integer $n \ge 1$, the sum of the $n^3$ integers assigned to any $n \times n \times n$ grid of lattice points is divisible by $P(n)$? [i]Proposed by Andre Arslan[/i]

2010 Romanian Masters In Mathematics, 1

Tags: induction , modular arithmetic , combinatorics

For a finite non empty set of primes $P$, let $m(P)$ denote the largest possible number of consecutive positive integers, each of which is divisible by at least one member of $P$. (i) Show that $|P|\le m(P)$, with equality if and only if $\min(P)>|P|$. (ii) Show that $m(P)<(|P|+1)(2^{|P|}-1)$. (The number $|P|$ is the size of set $P$) [i]Dan Schwarz, Romania[/i]

1997 All-Russian Olympiad, 1

Tags: modular arithmetic , number theory

Find all integer solutions of the equation $(x^2 - y^2)^2 = 1 + 16y$. [i]M. Sonkin[/i]

1987 Romania Team Selection Test, 2

Tags: modular arithmetic , ratio , number theory

Find all positive integers $A$ which can be represented in the form: \[ A = \left ( m - \dfrac 1n \right) \left( n - \dfrac 1p \right) \left( p - \dfrac 1m \right) \] where $m\geq n\geq p \geq 1$ are integer numbers. [i]Ioan Bogdan[/i]

2013 Bulgaria National Olympiad, 1

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]

2004 India Regional Mathematical Olympiad, 6

Tags: modular arithmetic , number theory , relatively prime

Let $p_1, p_2, \ldots$ be a sequence of primes such that $p_1 =2$ and for $n\geq 1, p_{n+1}$ is the largest prime factor of $p_1 p_2 \ldots p_n +1$ . Prove that $p_n \not= 5$ for any $n$.

2010 Singapore MO Open, 5

Tags: modular arithmetic , number theory

A prime number $p$ and integers $x, y, z$ with $0 < x < y < z < p$ are given. Show that if the numbers $x^3, y^3, z^3$ give the same remainder when divided by $p$, then $x^2 + y^2 + z^2$ is divisible by $x + y + z.$

2016 Bangladesh Mathematical Olympiad, 2

Tags: number theory , modular arithmetic , divisibility

(a) How many positive integer factors does $6000$ have? (b) How many positive integer factors of $6000$ are not perfect squares?

2014 South East Mathematical Olympiad, 3

Tags: modular arithmetic , number theory

Let $p$ be a primes ,$x,y,z $ be positive integers such that $x<y<z<p$ and $\{\frac{x^3}{p}\}=\{\frac{y^3}{p}\}=\{\frac{z^3}{p}\}$. Prove that $(x+y+z)|(x^5+y^5+z^5).$

2011 ELMO Shortlist, 1

Tags: modular arithmetic , number theory

Prove that $n^3-n-3$ is not a perfect square for any integer $n$. [i]Calvin Deng.[/i]

2002 AMC 10, 24

Tags: modular arithmetic , search , number theory , prime factorization

What is the maximum value of $n$ for which there is a set of distinct positive integers $k_1,k_2,\ldots,k_n$ for which \[k_1^2+k_2^2+\ldots+k_n^2=2002?\] $\textbf{(A) }14\qquad\textbf{(B) }15\qquad\textbf{(C) }16\qquad\textbf{(D) }17\qquad\textbf{(E) }18$

2008 China Team Selection Test, 2

Tags: modular arithmetic , relatively prime , number theory

Let $ n > 1$ be an integer, and $ n$ can divide $ 2^{\phi(n)} \plus{} 3^{\phi(n)} \plus{} \cdots \plus{} n^{\phi(n)},$ let $ p_{1},p_{2},\cdots,p_{k}$ be all distinct prime divisors of $ n$. Show that $ \frac {1}{p_{1}} \plus{} \frac {1}{p_{2}} \plus{} \cdots \plus{} \frac {1}{p_{k}} \plus{} \frac {1}{p_{1}p_{2}\cdots p_{k}}$ is an integer. ( where $ \phi(n)$ is defined as the number of positive integers $ \leq n$ that are relatively prime to $ n$.)

2002 Kazakhstan National Olympiad, 3

Tags: modular arithmetic , combinatorics , extremal combinatorics , maximization

Let $A = (a_1, a_2, \ldots, a_{2001})$ be a sequence of positive integers. Let $m$ be the number of 3-element subsequences $(a_i,a_j,a_k)$ with $1 \leq i < j < k \leq 2001$, such that $a_j = a_i + 1$ and $a_k = a_j + 1$. Considering all such sequences $A$, find the greatest value of $m$.

1984 AIME Problems, 12

Tags: function , modular arithmetic , floor function , geometry , geometric transformation , reflection

A function $f$ is defined for all real numbers and satisfies \[f(2 + x) = f(2 - x)\qquad\text{and}\qquad f(7 + x) = f(7 - x)\] for all real $x$. If $x = 0$ is a root of $f(x) = 0$, what is the least number of roots $f(x) = 0$ must have in the interval $-1000 \le x \le 1000$?

2006 India IMO Training Camp, 2

Tags: modular arithmetic , 3d geometry , analytic geometry , pigeonhole principle , number theory , geometry

Let $u_{jk}$ be a real number for each $j=1,2,3$ and each $k=1,2$ and let $N$ be an integer such that \[\max_{1\le k \le 2} \sum_{j=1}^3 |u_{jk}| \leq N\] Let $M$ and $l$ be positive integers such that $l^2 <(M+1)^3$. Prove that there exist integers $\xi_1,\xi_2,\xi_3$ not all zero, such that \[\max_{1\le j \le 3}\xi_j \le M\ \ \ \ \text{and} \ \ \ \left|\sum_{j=1}^3 u_{jk}\xi_k\right| \le \frac{MN}{l} \ \ \ \ \text{for k=1,2}\]

2012 Putnam, 4

Tags: inequalities , modular arithmetic , arithmetic sequence

Let $q$ and $r$ be integers with $q>0,$ and let $A$ and $B$ be intervals on the real line. Let $T$ be the set of all $b+mq$ where $b$ and $m$ are integers with $b$ in $B,$ and let $S$ be the set of all integers $a$ in $A$ such that $ra$ is in $T.$ Show that if the product of the lengths of $A$ and $B$ is less than $q,$ then $S$ is the intersection of $A$ with some arithmetic progression.

2013 Ukraine Team Selection Test, 10

Tags: number theory , modular arithmetic

Let $\mathbb{Z}$ and $\mathbb{Q}$ be the sets of integers and rationals respectively. a) Does there exist a partition of $\mathbb{Z}$ into three non-empty subsets $A,B,C$ such that the sets $A+B, B+C, C+A$ are disjoint? b) Does there exist a partition of $\mathbb{Q}$ into three non-empty subsets $A,B,C$ such that the sets $A+B, B+C, C+A$ are disjoint? Here $X+Y$ denotes the set $\{ x+y : x \in X, y \in Y \}$, for $X,Y \subseteq \mathbb{Z}$ and for $X,Y \subseteq \mathbb{Q}$.