Olympiad problems

2015 USA Team Selection Test, 2

Prove that for every $n\in \mathbb N$, there exists a set $S$ of $n$ positive integers such that for any two distinct $a,b\in S$, $a-b$ divides $a$ and $b$ but none of the other elements of $S$. [i]Proposed by Iurie Boreico[/i]

2014 Baltic Way, 1

Tags: trigonometry , modular arithmetic , algebra

Show that \[\cos(56^{\circ}) \cdot \cos(2 \cdot 56^{\circ}) \cdot \cos(2^2\cdot 56^{\circ})\cdot . . . \cdot \cos(2^{23}\cdot 56^{\circ}) = \frac{1}{2^{24}} .\]

2005 MOP Homework, 4

Tags: modular arithmetic , algebra , binomial theorem , number theory

Let $p$ be an odd prime. Prove that \[\sum^{p-1}_{k=1} k^{2p-1} \equiv \frac{p(p+1)}{2}\pmod{p^2}.\]

2004 Romania Team Selection Test, 13

Tags: euler , modular arithmetic , inequalities , function , number theory , relatively prime

Let $m\geq 2$ be an integer. A positive integer $n$ has the property that for any positive integer $a$ coprime with $n$, we have $a^m - 1\equiv 0 \pmod n$. Prove that $n \leq 4m(2^m-1)$. Created by Harazi, modified by Marian Andronache.

2011 JBMO Shortlist, 1

Tags: number theory , algebra , integer equation , diophantine equation , modular arithmetic

Solve in positive integers the equation $1005^x + 2011^y = 1006^z$.

2007 IMO Shortlist, 2

Tags: modular arithmetic , number theory , divisibility

Let $b,n > 1$ be integers. Suppose that for each $k > 1$ there exists an integer $a_k$ such that $b - a^n_k$ is divisible by $k$. Prove that $b = A^n$ for some integer $A$. [i]Author: Dan Brown, Canada[/i]

2009 Unirea, 4

Tags: limit , trigonometry , geometry , modular arithmetic , probability , integration , logarithm

Evaluate the limit: \[ \lim_{n \to \infty}{n \cdot \sin{1} \cdot \sin{2} \cdot \dots \cdot \sin{n}}.\] Proposed to "Unirea" Intercounty contest, grade 11, Romania

2014 Contests, 1

Tags: modular arithmetic , greatest common divisor , least common multiple , relatively prime , number theory

Four consecutive three-digit numbers are divided respectively by four consecutive two-digit numbers. What minimum number of different remainders can be obtained? [i](A. Golovanov)[/i]

2011 China Western Mathematical Olympiad, 1

Tags: modular arithmetic , prime number , number theory

Does there exist any odd integer $n \geq 3$ and $n$ distinct prime numbers $p_1 , p_2, \cdots p_n$ such that all $p_i + p_{i+1} (i = 1,2,\cdots , n$ and $p_{n+1} = p_{1})$ are perfect squares?

1989 IMO Shortlist, 27

Tags: modular arithmetic , number theory , least common multiple , divisibility

Let $ m$ be a positive odd integer, $ m > 2.$ Find the smallest positive integer $ n$ such that $ 2^{1989}$ divides $ m^n \minus{} 1.$

2001 Poland - Second Round, 1

Tags: algebra , polynomial , modular arithmetic , number theory

Let $k,n>1$ be integers such that the number $p=2k-1$ is prime. Prove that, if the number $\binom{n}{2}-\binom{k}{2}$ is divisible by $p$, then it is divisible by $p^2$.

2012 ELMO Shortlist, 8

Tags: function , modular arithmetic , induction , functional equation , algebra

Find all functions $f : \mathbb{Q} \to \mathbb{R}$ such that $f(x)f(y)f(x+y) = f(xy)(f(x) + f(y))$ for all $x,y\in\mathbb{Q}$. [i]Sammy Luo and Alex Zhu.[/i]

1997 Brazil Team Selection Test, Problem 3

Tags: modular arithmetic , linear algebra , matrix , number theory

Find all positive integers $x>1, y$ and primes $p,q$ such that $p^{x}=2^{y}+q^{x}$

2013 APMO, 2

Tags: modular arithmetic , inequalities , quadratic , algebra , floor function , function

Determine all positive integers $n$ for which $\dfrac{n^2+1}{[\sqrt{n}]^2+2}$ is an integer. Here $[r]$ denotes the greatest integer less than or equal to $r$.

2014 Contests, 2

Tags: induction , modular arithmetic , number theory , algebra

Let $n \ge 2$ be an integer. Show that there exist $n+1$ numbers $x_1, x_2, \ldots, x_{n+1} \in \mathbb{Q} \setminus \mathbb{Z}$, so that $\{ x_1^3 \} + \{ x_2^3 \} + \cdots + \{ x_n^3 \}=\{ x_{n+1}^3 \}$, where $\{ x \}$ is the fractionary part of $x$.

2012 Iran Team Selection Test, 1

Tags: algebra , polynomial , modular arithmetic , induction , vieta , calculus

Suppose $p$ is an odd prime number. We call the polynomial $f(x)=\sum_{j=0}^n a_jx^j$ with integer coefficients $i$-remainder if $ \sum_{p-1|j,j>0}a_{j}\equiv i\pmod{p}$. Prove that the set $\{f(0),f(1),...,f(p-1)\}$ is a complete residue system modulo $p$ if and only if polynomials $f(x), (f(x))^2,...,(f(x))^{p-2}$ are $0$-remainder and the polynomial $(f(x))^{p-1}$ is $1$-remainder. [i]Proposed by Yahya Motevassel[/i]

2011 IMO Shortlist, 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]

1986 AIME Problems, 5

Tags: modular arithmetic , algorithm , algebra , polynomial , greatest common divisor , number theory , euclidean algorithm

What is that largest positive integer $n$ for which $n^3+100$ is divisible by $n+10$?

1989 Polish MO Finals, 1

Tags: modular arithmetic , combinatorics

An even number of politicians are sitting at a round table. After a break, they come back and sit down again in arbitrary places. Show that there must be two people with the same number of people sitting between them as before the break.. [b]Additional problem:[/b] Solve the problem when the number of people is in a form $6k+3$.