Olympiad problems

2009 Turkey Team Selection Test, 1

Tags: function , algorithm , number theory , euclidean algorithm , continued fraction , algebra , functional equation

Find all $ f: Q^ \plus{} \to\ Z$ functions that satisfy $ f \left(\frac {1}{x} \right) \equal{} f(x)$ and $ (x \plus{} 1)f(x \minus{} 1) \equal{} xf(x)$ for all rational numbers that are bigger than 1.

2013 Finnish National High School Mathematics Competition, 2

Tags: inequalities , algorithm , number theory , euclidean algorithm , greatest common divisor , 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?

2003 AMC 10, 16

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

What is the units digit of $ 13^{2003}$? $ \textbf{(A)}\ 1 \qquad \textbf{(B)}\ 3 \qquad \textbf{(C)}\ 7 \qquad \textbf{(D)}\ 8 \qquad \textbf{(E)}\ 9$

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

2009 Harvard-MIT Mathematics Tournament, 2

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

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

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.

2018 CMIMC Individual Finals, 2

Tags: number theory , euclidean algorithm , algorithm

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}

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

2015 Middle European Mathematical Olympiad, 4

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

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.

2017 Finnish National High School Mathematics Comp, 1

Tags: number theory , remainder , euclidean algorithm , division

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

1988 AIME Problems, 8

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

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

2016 IMO Shortlist, N3

Tags: number theory , polynomial , algebra , euclidean algorithm

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?

2006 AMC 12/AHSME, 25

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

A sequence $ a_1, a_2, \ldots$ of non-negative integers is defined by the rule $ a_{n \plus{} 2} \equal{} |a_{n \plus{} 1} \minus{} a_n|$ for $ n\ge 1$. If $ a_1 \equal{} 999, a_2 < 999,$ and $ a_{2006} \equal{} 1$, how many different values of $ a_2$ are possible? $ \textbf{(A) } 165 \qquad \textbf{(B) } 324 \qquad \textbf{(C) } 495 \qquad \textbf{(D) } 499 \qquad \textbf{(E) } 660$

1982 IMO Longlists, 7

Tags: 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.\]