Olympiad problems

2004 Poland - First Round, 2

2. Find all natural $n>1$ for which value of the sum $2^2+3^2+...+n^2$ equals $p^k$ where p is prime and k is natural

1985 AMC 12/AHSME, 26

Tags: algorithm , number theory , Euclidean algorithm

Find the least positive integer $ n$ for which $ \frac{n\minus{}13}{5n\plus{}6}$ is non-zero reducible fraction. $ \textbf{(A)}\ 45 \qquad \textbf{(B)}\ 68 \qquad \textbf{(C)}\ 155 \qquad \textbf{(D)}\ 226 \qquad \textbf{(E)}\ \text{none of these}$

2015 Middle European Mathematical Olympiad, 4

Tags: number theory , relatively prime , Exponents , factorization , Euclidean algorithm

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.

2005 Korea National Olympiad, 1

Tags: algorithm , number theory , greatest common divisor , relatively prime , Euclidean algorithm , number theory unsolved

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

2010 Iran MO (2nd Round), 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.

2017 Bulgaria EGMO TST, 1

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

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^+}.$

2017 IMO Shortlist, N8

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

2013 Finnish National High School Mathematics Competition, 2

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

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

2011 Bundeswettbewerb Mathematik, 4

Tags: Diophantine equation , diophantine , Euclidean algorithm , number theory

Let $a$ and $b$ be positive integers. As is known, the division of of $a \cdot b$ with $a + b$ determines integers $q$ and $r$ uniquely such that $a \cdot b = q (a + b) + r$ and $0 \le r <a + b$. Find all pairs $(a, b)$ for which $q^2 + r = 2011$.

2009 IberoAmerican, 5

Tags: search , induction , algorithm , continued fraction , number theory , Euclidean algorithm , algebra proposed

Consider the sequence $ \{a_n\}_{n\geq1}$ defined as follows: $ a_1 \equal{} 1$, $ a_{2k} \equal{} 1 \plus{} a_k$ and $ a_{2k \plus{} 1} \equal{} \frac {1}{a_{2k}}$ for every $ k\geq 1$. Prove that every positive rational number appears on the sequence $ \{a_n\}$ exactly once.

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

2016 IMO, 4

Tags: number theory , IMO Shortlist , polynomial , algebra , IMO 2016 , P4 , 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?

2023 Tuymaada Olympiad, 6

Tags: number theory , Euclidean algorithm

An $\textit{Euclidean step}$ transforms a pair $(a, b)$ of positive integers, $a > b$, to the pair $(b, r)$, where $r$ is the remainder when a is divided by $b$. Let us call the $\textit{complexity}$ of a pair $(a, b)$ the number of Euclidean steps needed to transform it to a pair of the form $(s, 0)$. Prove that if $ad - bc = 1$, then the complexities of $(a, b)$ and $(c, d)$ differ at most by $2$.

2011 Turkey Team Selection Test, 1

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

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^+}.$

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$

2009 Princeton University Math Competition, 8

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

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

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.

2011 Tokio University Entry Examination, 2

Tags: algorithm , number theory , Euclidean algorithm

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]

2018 CMIMC Individual Finals, 2

Tags: Tiebreaker , 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}

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

1985 ITAMO, 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.

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$

2014 AIME Problems, 3

Tags: algorithm , Euler , function , number theory , Euclidean algorithm , relatively prime , totient 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$.

2016 IMO Shortlist, N3

Tags: number theory , IMO Shortlist , polynomial , algebra , IMO 2016 , P4 , 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?