Olympiad problems

2002 Tournament Of Towns, 2

All the species of plants existing in Russia are catalogued (numbered by integers from $2$ to $2000$ ; one after another, without omissions or repetitions). For any pair of species the gcd of their catalogue numbers was calculated and recorded but the catalogue numbers themselves were lost. Is it possible to restore the catalogue numbers from the data in hand?

2022 MMATHS, 8

Tags: number theory , greatest common divisor

Let $S = \{1, 2, 3, 5, 6, 10, 15, 30\}$. For each of the $64$ ordered pairs $(a, b)$ of elements of $S$, AJ computes $gcd(a, b)$. They then sum all of the numbers they computed. What is AJ’s sum?

2007 Indonesia TST, 4

Tags: greatest common divisor , number theory

Determine all pairs $ (n,p)$ of positive integers, where $ p$ is prime, such that $ 3^p\minus{}np\equal{}n\plus{}p$.

2003 India IMO Training Camp, 2

Tags: greatest common divisor , number theory

Find all triples $(a,b,c)$ of positive integers such that (i) $a \leq b \leq c$; (ii) $\text{gcd}(a,b,c)=1$; and (iii) $a^3+b^3+c^3$ is divisible by each of the numbers $a^2b, b^2c, c^2a$.

1991 Romania Team Selection Test, 8

Tags: number theory , greatest common divisor , diophantine equation , algebra , function

Let $n, a, b$ be integers with $n \geq 2$ and $a \notin \{0, 1\}$ and let $u(x) = ax + b$ be the function defined on integers. Show that there are infinitely many functions $f : \mathbb{Z} \rightarrow \mathbb{Z}$ such that $f_n(x) = \underbrace{f(f(\cdots f}_{n}(x) \cdots )) = u(x)$ for all $x$. If $a = 1$, show that there is a $b$ for which there is no $f$ with $f_n(x) \equiv u(x)$.

2011 Saudi Arabia IMO TST, 2

Tags: number theory , greatest common divisor , gcd

Consider the set $S= \{(a + b)^7 - a^7 - b^7 : a,b \in Z\}$. Find the greatest common divisor of all members in $S$.

1995 AMC 12/AHSME, 27

Tags: modular arithmetic , number theory , greatest common divisor , arithmetic series

Consider the triangular array of numbers with $0,1,2,3,...$ along the sides and interior numbers obtained by adding the two adjacent numbers in the previous row. Rows $1$ through $6$ are shown. \begin{tabular}{ccccccccccc} & & & & & 0 & & & & & \\ & & & & 1 & & 1 & & & & \\ & & & 2 & & 2 & & 2 & & & \\ & & 3 & & 4 & & 4 & & 3 & & \\ & 4 & & 7 & & 8 & & 7 & & 4 & \\ 5 & & 11 & & 15 & & 15 & & 11 & & 5 \end{tabular} Let $f(n)$ denote the sum of the numbers in row $n$. What is the remainder when $f(100)$ is divided by $100$? $\textbf{(A)}\ 12\qquad \textbf{(B)}\ 30 \qquad \textbf{(C)}\ 50 \qquad \textbf{(D)}\ 62 \qquad \textbf{(E)}\ 74$

2009 Brazil Team Selection Test, 4

Tags: greatest common divisor , number theory , sequence

Let $ a_0$, $ a_1$, $ a_2$, $ \ldots$ be a sequence of positive integers such that the greatest common divisor of any two consecutive terms is greater than the preceding term; in symbols, $ \gcd (a_i, a_{i \plus{} 1}) > a_{i \minus{} 1}$. Prove that $ a_n\ge 2^n$ for all $ n\ge 0$. [i]Proposed by Morteza Saghafian, Iran[/i]