Olympiad problems

2017 Finnish National High School Mathematics Comp, 1

By dividing the integer $m$ by the integer $n, 22$ is the quotient and $5$ the remainder. As the division of the remainder with $n$ continues, the new quotient is $0.4$ and the new remainder is $0.2$. Find $m$ and $n$.

2007 Iran MO (3rd Round), 5

Tags: induction , algorithm , geometry , geometric transformation , number theory , Euclidean algorithm , relatively prime

Look at these fractions. At firs step we have $ \frac{0}{1}$ and $ \frac{1}{0}$, and at each step we write $ \frac{a\plus{}b}{c\plus{}d}$ between $ \frac{a}{b}$ and $ \frac{c}{d}$, and we do this forever \[ \begin{array}{ccccccccccccccccccccccccc}\frac{0}{1}&&&&&&&&\frac{1}{0}\\ \frac{0}{1}&&&&\frac{1}{1}&&&&\frac{1}{0}\\ \frac{0}{1}&&\frac{1}{2}&&\frac{1}{1}&&\frac{2}{1}&&\frac{1}{0}\\ \frac{0}{1}&\frac{1}{3}&\frac{1}{2}&\frac{2}{3}&\frac{1}{1}&\frac{3}{2}&\frac{2}{1}&\frac{3}{1}&\frac{1}{0}\\ &&&&\dots\end{array}\] a) Prove that each of these fractions is irreducible. b) In the plane we have put infinitely many circles of diameter 1, over each integer on the real line, one circle. The inductively we put circles that each circle is tangent to two adjacent circles and real line, and we do this forever. Prove that points of tangency of these circles are exactly all the numbers in part a(except $ \frac{1}{0}$). [img]http://i2.tinypic.com/4m8tmbq.png[/img] c) Prove that in these two parts all of positive rational numbers appear. If you don't understand the numbers, look at [url=http://upload.wikimedia.org/wikipedia/commons/2/21/Arabic_numerals-en.svg]here[/url].

1999 Dutch Mathematical Olympiad, 5

Tags: algorithm , greatest common divisor , number theory , Euclidean algorithm

Let $c$ be a nonnegative integer, and define $a_n = n^2 + c$ (for $n \geq 1)$. Define $d_n$ as the greatest common divisor of $a_n$ and $a_{n + 1}$. (a) Suppose that $c = 0$. Show that $d_n = 1,\ \forall n \geq 1$. (b) Suppose that $c = 1$. Show that $d_n \in \{1,5\},\ \forall n \geq 1$. (c) Show that $d_n \leq 4c + 1,\ \forall n \geq 1$.

1985 AIME Problems, 13

Tags: number theory , greatest common divisor , algorithm , algebra , polynomial , Euclidean algorithm

The numbers in the sequence 101, 104, 109, 116, $\dots$ are of the form $a_n = 100 + n^2$, where $n = 1$, 2, 3, $\dots$. For each $n$, let $d_n$ be the greatest common divisor of $a_n$ and $a_{n + 1}$. Find the maximum value of $d_n$ as $n$ ranges through the positive integers.

2014 Online Math Open Problems, 14

Tags: Online Math Open , algorithm , number theory , greatest common divisor , Euclidean algorithm

What is the greatest common factor of $12345678987654321$ and $12345654321$? [i]Proposed by Evan Chen[/i]

1996 All-Russian Olympiad, 2

Tags: analytic geometry , vector , algorithm , number theory , Euclidean algorithm , combinatorics proposed , combinatorics

On a coordinate plane are placed four counters, each of whose centers has integer coordinates. One can displace any counter by the vector joining the centers of two of the other counters. Prove that any two preselected counters can be made to coincide by a finite sequence of moves. [i]Р. Sadykov[/i]

Russian TST 2018, P3

Tags: IMO Shortlist , number theory , Euclidean algorithm

Let $p$ be an odd prime number and $\mathbb{Z}_{>0}$ be the set of positive integers. Suppose that a function $f:\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}\to\{0,1\}$ satisfies the following properties: [list] [*] $f(1,1)=0$. [*] $f(a,b)+f(b,a)=1$ for any pair of relatively prime positive integers $(a,b)$ not both equal to 1; [*] $f(a+b,b)=f(a,b)$ for any pair of relatively prime positive integers $(a,b)$. [/list] Prove that $$\sum_{n=1}^{p-1}f(n^2,p) \geqslant \sqrt{2p}-2.$$

2010 Contests, 1

Tags: algorithm , number theory , Euclidean algorithm , number theory unsolved

Let $a,b$ be two positive integers and $a>b$.We know that $\gcd(a-b,ab+1)=1$ and $\gcd(a+b,ab-1)=1$. Prove that $(a-b)^2+(ab+1)^2$ is not a perfect square.

1982 IMO Longlists, 7

Tags: LaTeX , modular arithmetic , algorithm , floor function , number theory , greatest common divisor , Euclidean algorithm

Find all solutions $(x, y) \in \mathbb Z^2$ of the equation \[x^3 - y^3 = 2xy + 8.\]

1990 AIME Problems, 3

Tags: ratio , algorithm , number theory , Euclidean algorithm

Let $ P_1$ be a regular $ r$-gon and $ P_2$ be a regular $ s$-gon $ (r\geq s\geq 3)$ such that each interior angle of $ P_1$ is $ \frac {59}{58}$ as large as each interior angle of $ P_2$. What's the largest possible value of $ s$?

1998 All-Russian Olympiad, 8

Tags: algorithm , number theory , least common multiple , Euclidean algorithm , number theory proposed

Two distinct positive integers $a,b$ are written on the board. The smaller of them is erased and replaced with the number $\frac{ab}{|a-b|}$. This process is repeated as long as the two numbers are not equal. Prove that eventually the two numbers on the board will be equal.

1954 AMC 12/AHSME, 4

Tags: algorithm , number theory , Euclidean algorithm

If the Highest Common Divisor of $ 6432$ and $ 132$ is diminished by $ 8$, it will equal: $ \textbf{(A)}\ \minus{}6 \qquad \textbf{(B)}\ 6 \qquad \textbf{(C)}\ \minus{}2 \qquad \textbf{(D)}\ 3 \qquad \textbf{(E)}\ 4$

2011 Spain Mathematical Olympiad, 2

Tags: function , algorithm , group theory , abstract algebra , induction , number theory , Euclidean algorithm

Each rational number is painted either white or red. Call such a coloring of the rationals [i]sanferminera[/i] if for any distinct rationals numbers $x$ and $y$ satisfying one of the following three conditions: [list=1][*]$xy=1$, [*]$x+y=0$, [*]$x+y=1$,[/list]we have $x$ and $y$ painted different colors. How many sanferminera colorings are there?

2005 Postal Coaching, 4

Tags: number theory , greatest common divisor , algorithm , Euclidean algorithm , number theory solved

Let $m,n$ be natural numbers and let $d = gcd(m,n)$. Let $x = 2^{m} -1$ and $y= 2^n +1$ (a) If $\frac{m}{d}$ is odd, prove that $gcd(x,y) = 1$ (b) If $\frac{m}{d}$ is even, Find $gcd(x,y)$