Olympiad problems

1996 All-Russian Olympiad, 2

Tags: euclidean algorithm , algorithm , vector , number theory , combinatorics , analytic geometry

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]

2015 Middle European Mathematical Olympiad, 4

Tags: factorization , euclidean algorithm , exponent , number theory , relatively prime

Find all pairs of positive integers $(m,n)$ for which there exist relatively prime integers $a$ and $b$ greater than $1$ such that $$\frac{a^m+b^m}{a^n+b^n}$$ is an integer.

1985 AIME Problems, 13

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

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.

2013 Finnish National High School Mathematics Competition, 2

Tags: algorithm , euclidean algorithm , greatest common divisor , number theory , inequalities , combinatorics

In a particular European city, there are only $7$ day tickets and $30$ day tickets to the public transport. The former costs $7.03$ euro and the latter costs $30$ euro. Aina the Algebraist decides to buy at once those tickets that she can travel by the public transport the whole three year (2014-2016, 1096 days) visiting in the city. What is the cheapest solution?

2009 Princeton University Math Competition, 8

Tags: relatively prime , euclidean algorithm , difference of squares , greatest common divisor , algebra , number theory , algorithm

Find the largest positive integer $k$ such that $\phi ( \sigma ( 2^k)) = 2^k$. ($\phi(n)$ denotes the number of positive integers that are smaller than $n$ and relatively prime to $n$, and $\sigma(n)$ denotes the sum of divisors of $n$). As a hint, you are given that $641|2^{32}+1$.

2010 Iran MO (2nd Round), 1

Tags: algorithm , euclidean algorithm , number theory

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.

2016 IMO Shortlist, N3

Tags: euclidean algorithm , number theory , algebra , polynomial

A set of positive integers is called [i]fragrant[/i] if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let $P(n)=n^2+n+1$. What is the least possible positive integer value of $b$ such that there exists a non-negative integer $a$ for which the set $$\{P(a+1),P(a+2),\ldots,P(a+b)\}$$ is fragrant?

2017 IMO Shortlist, N8

Tags: euclidean algorithm , number theory

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

2011 Tokio University Entry Examination, 2

Tags: algorithm , euclidean algorithm , number theory

Define real number $y$ as the fractional part of real number $x$ such that $0\leq y<1$ and $x-y$ is integer. Denote this by $<x>$. For real number $a$, define an infinite sequence $\{a_n\}\ (n=1,\ 2,\ 3,\ \cdots)$ inductively as follows. (i) $a_1=<a>$ (ii) If $a\n\neq 0$, then $a_{n+1}=\left<\frac{1}{a_n}\right>$, if $a_n=0$, then $a_{n+1}=0$. (1) For $a=\sqrt{2}$, find $a_n$. (2) For any natural number $n$, find real number $a\geq \frac 13$ such that $a_n=a$. (3) Let $a$ be a rational number. When we express $a=\frac{p}{q}$ with integer $p$, natural number $q$, prove that $a_n=0$ for any natural number $n\geq q$. [i]2011 Tokyo University entrance exam/Science, Problem 2[/i]

1982 IMO Longlists, 7

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

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

1990 AIME Problems, 3

Tags: algorithm , euclidean algorithm , number theory , ratio

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

2010 Contests, 1

Tags: algorithm , euclidean algorithm , number theory

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.

2009 Harvard-MIT Mathematics Tournament, 2

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

Suppose N is a $6$-digit number having base-$10$ representation $\underline{a}\text{ }\underline{b}\text{ }\underline{c}\text{ }\underline{d}\text{ }\underline{e}\text{ }\underline{f}$. If $N$ is $6/7$ of the number having base-$10$ representation $\underline{d}\text{ }\underline{e}\text{ }\underline{f}\text{ }\underline{a}\text{ }\underline{b}\text{ }\underline{c}$, find $N$.

2016 IMO, 4

Tags: number theory , algebra , euclidean algorithm , polynomial

A set of positive integers is called [i]fragrant[/i] if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let $P(n)=n^2+n+1$. What is the least possible positive integer value of $b$ such that there exists a non-negative integer $a$ for which the set $$\{P(a+1),P(a+2),\ldots,P(a+b)\}$$ is fragrant?

2014 Online Math Open Problems, 14

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

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

2018 CMIMC Individual Finals, 2

Tags: algorithm , euclidean algorithm , number theory

Determine the largest number of steps for $\gcd(k,76)$ to terminate over all choices of $0 < k < 76$, using the following algorithm for gcd. Give your answer in the form $(n,k)$ where $n$ is the maximal number of steps and $k$ is the $k$ which achieves this. If multiple $k$ work, submit the smallest one. \begin{tabular}{l} 1: \textbf{FUNCTION} $\text{gcd}(a,b)$: \\ 2: $\qquad$ \textbf{IF} $a = 0$ \textbf{RETURN} $b$ \\ 3: $\qquad$ \textbf{ELSE RETURN} $\text{gcd}(b \bmod a,a)$ \end{tabular}

2011 Turkey Team Selection Test, 1

Tags: algorithm , functional equation , euclidean algorithm , algebra , number theory , function , induction

Let $\mathbb{Q^+}$ denote the set of positive rational numbers. Determine all functions $f: \mathbb{Q^+} \to \mathbb{Q^+}$ that satisfy the conditions \[ f \left( \frac{x}{x+1}\right) = \frac{f(x)}{x+1} \qquad \text{and} \qquad f \left(\frac{1}{x}\right)=\frac{f(x)}{x^3}\] for all $x \in \mathbb{Q^+}.$

2011 Spain Mathematical Olympiad, 2

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

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?

Russian TST 2018, P3

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

2017 Bulgaria EGMO TST, 1

Tags: algebra , number theory , function , algorithm , euclidean algorithm , functional equation , induction

Let $\mathbb{Q^+}$ denote the set of positive rational numbers. Determine all functions $f: \mathbb{Q^+} \to \mathbb{Q^+}$ that satisfy the conditions \[ f \left( \frac{x}{x+1}\right) = \frac{f(x)}{x+1} \qquad \text{and} \qquad f \left(\frac{1}{x}\right)=\frac{f(x)}{x^3}\] for all $x \in \mathbb{Q^+}.$

1998 All-Russian Olympiad, 8

Tags: number theory , algorithm , least common multiple , euclidean algorithm

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.

1999 Dutch Mathematical Olympiad, 5

Tags: number theory , algorithm , greatest common divisor , 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$.

1988 AIME Problems, 8

Tags: number theory , least common multiple , algorithm , euclidean algorithm , function

The function $f$, defined on the set of ordered pairs of positive integers, satisfies the following properties: \begin{eqnarray*} f(x,x) &=& x, \\ f(x,y) &=& f(y,x), \quad \text{and} \\ (x + y) f(x,y) &=& yf(x,x + y). \end{eqnarray*} Calculate $f(14,52)$.

2014 AIME Problems, 3

Tags: algorithm , number theory , euler , euclidean algorithm , totient function , relatively prime , function

Find the number of rational numbers $r$, $0<r<1$, such that when $r$ is written as a fraction in lowest terms, the numerator and denominator have a sum of $1000$.

2005 Korea National Olympiad, 1

Tags: greatest common divisor , algorithm , euclidean algorithm , number theory , relatively prime

For two positive integers a and b, which are relatively prime, find all integer that can be the great common divisor of $a+b$ and $\frac{a^{2005}+b^{2005}}{a+b}$.