Olympiad problems

2003 Turkey MO (2nd round), 1

Suppose that $2^{2n+1}+ 2^{n}+1=x^{k}$, where $k\geq2$ and $n$ are positive integers. Find all possible values of $n$.

2001 Tournament Of Towns, 1

Tags: greatest common divisor , number theory

Do there exist postive integers $a_1<a_2<\cdots<a_{100}$ such that for $2\le k\le100$ the greatest common divisor of $a_{k-1}$ and $a_k$ is greater than the greatest common divisor of $a_k$ and $a_{k+1}$?

1989 APMO, 2

Tags: modular arithmetic , greatest common divisor , number theory

Prove that the equation \[ 6(6a^2 + 3b^2 + c^2) = 5n^2 \] has no solutions in integers except $a = b = c = n = 0$.

1994 Polish MO Finals, 1

Tags: algorithm , greatest common divisor , number theory

$m, n$ are relatively prime. We have three jugs which contain $m$, $n$ and $m+n$ liters. Initially the largest jug is full of water. Show that for any $k$ in $\{1, 2, ... , m+n\}$ we can get exactly $k$ liters into one of the jugs.

2023 AMC 12/AHSME, 24

Tags: number theory , least common multiple , greatest common divisor

Integers $a, b, c, d$ satisfy the following: $abcd=2^6\cdot 3^9\cdot 5^7$ $\text{lcm}(a,b)=2^3\cdot 3^2\cdot 5^3$ $\text{lcm}(a,c)=2^3\cdot 3^3\cdot 5^3$ $\text{lcm}(a,d)=2^3\cdot 3^3\cdot 5^3$ $\text{lcm}(b,c)=2^1\cdot 3^3\cdot 5^2$ $\text{lcm}(b,d)=2^2\cdot 3^3\cdot 5^2$ $\text{lcm}(c,d)=2^2\cdot 3^3\cdot 5^2$ Find $\text{gcd}(a,b,c,d)$ $\textbf{(A)}~30\qquad\textbf{(B)}~45\qquad\textbf{(C)}~3\qquad\textbf{(D)}~15\qquad\textbf{(E)}~6$

2010 AMC 12/AHSME, 20

Tags: number theory , greatest common divisor , modular arithmetic

Arithmetic sequences $ (a_n)$ and $ (b_n)$ have integer terms with $ a_1 \equal{} b_1 \equal{} 1 < a_2 \le b_2$ and $ a_nb_n \equal{} 2010$ for some $ n$. What is the largest possible value of $ n$? $ \textbf{(A)}\ 2 \qquad \textbf{(B)}\ 3 \qquad \textbf{(C)}\ 8 \qquad \textbf{(D)}\ 288 \qquad \textbf{(E)}\ 2009$

1998 USAMTS Problems, 2

Tags: greatest common divisor

Prove that there are inﬁnitely many ordered triples of positive integers $(a,b,c)$ such that the greatest common divisor of $a,b,$ and $c$ is $1$, and the sum $a^2b^2+b^2c^2+c^2a^2$ is the square of an integer.

2021 Bangladeshi National Mathematical Olympiad, 2

Tags: number theory , greatest common divisor , least common multiple

Let $x$ and $y$ be positive integers such that $2(x+y)=gcd(x,y)+lcm(x,y)$. Find $\frac{lcm(x,y)}{gcd(x,y)}$.

2006 Thailand Mathematical Olympiad, 12

Tags: number theory , greatest common divisor , sequence , gcd

Let $a_n = 2^{3n-1} + 3^{6n-2} + 5^{6n-3}$. Compute gcd$(a_1, a_2, ... , a_{25})$

2022 Germany Team Selection Test, 1

Tags: combinatorics , graph theory , greatest common divisor

Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$.

2012 JBMO TST - Turkey, 2

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

Find all positive integers $m,n$ and prime numbers $p$ for which $\frac{5^m+2^np}{5^m-2^np}$ is a perfect square.

2003 Hungary-Israel Binational, 1

Tags: greatest common divisor , combinatorics

Two players play the following game. They alternately write divisors of $100!$ on the blackboard, not repeating any of the numbers written before. The player after whose move the greatest common divisor of the written numbers equals $1,$ loses the game. Which player has a winning strategy?

2004 Postal Coaching, 14

Tags: greatest common divisor , number theory

Find the greatest common divisor of all number in the set $( a^{41} - a | a \in \mathbb{N} and \geq 2 )$ . What is your guess if 41 is replaced by a natural number $n$

1997 Romania Team Selection Test, 4

Tags: polynomial , number theory , greatest common divisor , modular arithmetic , algebra

Let $n\ge 2$ be an integer and let $P(X)=X^n+a_{n-1}X^{n-1}+\ldots +a_1X+1$ be a polynomial with positive integer coefficients. Suppose that $a_k=a_{n-k}$ for all $k\in 1,2,\ldots,n-1$. Prove that there exist infinitely many pairs of positive integers $x,y$ such that $x|P(y)$ and $y|P(x)$. [i]Remus Nicoara[/i]

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

2012 Indonesia TST, 4

Tags: greatest common divisor , modular arithmetic , number theory

Determine all integer $n > 1$ such that \[\gcd \left( n, \dfrac{n-m}{\gcd(n,m)} \right) = 1\] for all integer $1 \le m < n$.

2017 Pan-African Shortlist, N1

Tags: number theory , greatest common divisor , floor function , function , algebra , divisibility theory

Prove that the expression \[\frac{\gcd(m, n)}{n}{n \choose m}\] is an integer for all pairs of positive integers $(m, n)$ with $n \ge m \ge 1$.

2013 Gulf Math Olympiad, 4

Tags: greatest common divisor , number theory

Let $m,n$ be integers. It is known that there are integers $a,b$ such that $am+bn=1$ if, and only if, the greatest common divisor of $m,n$ is 1. [i]You are not required to prove this[/i]. Now suppose that $p,q$ are different odd primes. In each case determine if there are integers $a,b$ such that $ap+bq=1$ so that the given condition is satisfied: [list] a. $p$ divides $b$ and $q$ divides $a$; b. $p$ divides $a$ and $q$ divides $b$; c. $p$ does not divide $a$ and $q$ does not divide $b$. [/list]

2018 VTRMC, 4

Tags: binomial coefficient , number theory , greatest common divisor

Let $m, n$ be integers such that $n \geq m \geq 1$. Prove that $\frac{\text{gcd} (m,n)}{n} \binom{n}{m}$ is an integer. Here $\text{gcd}$ denotes greatest common divisor and $\binom{n}{m} = \frac{n!}{m!(n-m)!}$ denotes the binomial coefficient.

2007 Romania Team Selection Test, 3

Tags: greatest common divisor , number theory

Let $a_{i}$, $i = 1,2, \dots ,n$, $n \geq 3$, be positive integers, having the greatest common divisor 1, such that \[a_{j}\textrm{ divide }\sum_{i = 1}^{n}a_{i}\] for all $j = 1,2, \dots ,n$. Prove that \[\prod_{i = 1}^{n}a_{i}\textrm{ divides }\Big{(}\sum_{i = 1}^{n}a_{i}\Big{)}^{n-2}.\]

2016 SGMO, Q1

Tags: function , greatest common divisor , number theory

Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that for any pair of naturals $m,n$, $$\gcd(f(m),n) = \gcd(m,f(n)).$$

2014 HMNT, 3

Tags: hmmt , greatest common divisor

Compute the greatest common divisor of $4^8 - 1$ and $8^{12} - 1$.

2023 Switzerland - Final Round, 3

Tags: number theory , greatest common divisor

Let $x,y$ and $a_0, a_1, a_2, \cdots $ be integers satisfying $a_0 = a_1 = 0$, and $$a_{n+2} = xa_{n+1}+ya_n+1$$for all integers $n \geq 0$. Let $p$ be any prime number. Show that $\gcd(a_p,a_{p+1})$ is either equal to $1$ or greater than $\sqrt{p}$.

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.

1957 AMC 12/AHSME, 32

Tags: number theory , greatest common divisor , modular arithmetic

The largest of the following integers which divides each of the numbers of the sequence $ 1^5 \minus{} 1,\, 2^5 \minus{} 2,\, 3^5 \minus{} 3,\, \cdots, n^5 \minus{} n, \cdots$ is: $ \textbf{(A)}\ 1 \qquad \textbf{(B)}\ 60 \qquad \textbf{(C)}\ 15 \qquad \textbf{(D)}\ 120\qquad \textbf{(E)}\ 30$