Found problems: 97
2008 Indonesia TST, 3
Let $n$ be an arbitrary positive integer.
(a) For every positive integers $a$ and $b$, show that $gcd(n^a + 1, n^b + 1) \le n^{gcd(a,b)} + 1$.
(b) Show that there exist infinitely many composite pairs ($a, b)$, such that each of them is not a multiply of the other number and equality holds in (a).
2005 Thailand Mathematical Olympiad, 9
Compute gcd $\left( \frac{135^{90}-45^{90}}{90^2} , 90^2 \right)$
2004 Estonia National Olympiad, 1
Find all triples of positive integers $(x, y, z)$ satisfying $x < y < z$, $gcd(x, y) = 6, gcd(y, z) = 10, gcd(z, x) = 8$ and $lcm(x, y,z) = 2400$.
2012 EGMO, 5
The numbers $p$ and $q$ are prime and satisfy
\[\frac{p}{{p + 1}} + \frac{{q + 1}}{q} = \frac{{2n}}{{n + 2}}\]
for some positive integer $n$. Find all possible values of $q-p$.
[i]Luxembourg (Pierre Haas)[/i]
2004 Cuba MO, 4
Determine all pairs of natural numbers $ (x, y)$ for which it holds that $$x^2 = 4y + 3gcd (x, y).$$
2019 Dutch BxMO TST, 4
Do there exist a positive integer $k$ and a non-constant sequence $a_1, a_2, a_3, ...$ of positive integers such that $a_n = gcd(a_{n+k}, a_{n+k+1})$ for all positive integers $n$?
2012 Bogdan Stan, 2
For any $ a\in\mathbb{Z}_{\ge 0} $ make the notation $ a\mathbb{Z}_{\ge 0} =\{ an| n\in\mathbb{Z}_{\ge 0} \} . $ Prove that the following relations are equivalent:
$ \text{(1)} a\mathbb{Z}_{\ge 0} \setminus b\mathbb{Z}_{\ge 0}\subset c\mathbb{Z}_{\ge 0} \setminus d\mathbb{Z}_{\ge 0} $
$ \text{(2)} b|a\text{ or } (c|a\text{ and } \text{lcm} (a,b) |\text{lcm} (a,d)) $
[i]Marin Tolosi[/i] and [i]Cosmin Nitu[/i]
2018 Saudi Arabia GMO TST, 1
Let $n$ be an odd positive integer with $n > 1$ and let $a_1, a_2,... , a_n$ be positive integers such that gcd $(a_1, a_2,... , a_n) = 1$. Let $d$ = gcd $(a_1^n + a_1\cdot a_2 \cdot \cdot \cdot a_n, a_2^n + a_1\cdot a_2 \cdot \cdot \cdot a_n, ... , a_n^n + a_1\cdot a_2 \cdot \cdot \cdot a_n)$. Show that the possible values of $d$ are $d = 1, d = 2$
2016 Latvia Baltic Way TST, 16
What is the largest possible value of the expression $$gcd \,\,\, (n^2 + 3, (n + 1)^2 + 3 )$$ for naturals $n$?
[hide]original wording]Kāda ir izteiksmes LKD (n2 + 3, (n + 1)2 + 3) lielākā iespējamā vērtība naturāliem n? [/hide]
2013 Switzerland - Final Round, 1
Find all triples $(a, b, c)$ of natural numbers such that the sets
$$\{ gcd (a, b), gcd(b, c), gcd(c, a), lcm (a, b), lcm (b, c), lcm (c, a)\}$$ and
$$\{2, 3, 5, 30, 60\}$$
are the same.
Remark: For example, the sets $\{1, 2013\}$ and $\{1, 1, 2013\}$ are equal.
2012 Thailand Mathematical Olympiad, 7
Let $a, b, m$ be integers such that gcd $(a, b) = 1$ and $5 | ma^2 + b^2$ . Show that there exists an integer $n$ such that $5 | m - n^2$.
2010 Estonia Team Selection Test, 1
For arbitrary positive integers $a, b$, denote $a @ b =\frac{a-b}{gcd(a,b)}$
Let $n$ be a positive integer. Prove that the following conditions are equivalent:
(i) $gcd(n, n @ m) = 1$ for every positive integer $m < n$,
(ii) $n = p^k$ where $p$ is a prime number and $k$ is a non-negative integer.
2004 Thailand Mathematical Olympiad, 14
Compute gcd$(5^{2547} - 1, 5^{2004} - 1)$.
2014 Costa Rica - Final Round, 3
Find all possible pairs of integers $ a$ and $ b$ such that $ab = 160 + 90 (a,b)$, where $(a, b)$ is the greatest common divisor of $ a$ and $ b$.
2001 Saint Petersburg Mathematical Olympiad, 9.4
Let $a,b,c\in\mathbb{Z^{+}}$ such that
$$(a^2-1, b^2-1, c^2-1)=1$$
Prove that
$$(ab+c, bc+a, ca+b)=(a,b,c)$$
(As usual, $(x,y,z)$ means the greatest common divisor of numbers $x,y,z$)
[I]Proposed by A. Golovanov[/i]
1995 All-Russian Olympiad Regional Round, 10.2
Natural numbers $m$ and $n$ satisfy $$gcd(m,n)+lcm(m,n) = m+n. $$Prove that one of numbers $m,n$ divides the other.
2022 Caucasus Mathematical Olympiad, 3
Pete wrote down $21$ pairwise distinct positive integers, each not greater than $1,000,000$. For every pair $(a, b)$ of numbers written down by Pete, Nick wrote the number
$$F(a;b)=a+b -\gcd(a;b)$$
on his piece of paper. Prove that one of Nick’s numbers differs from all of Pete’s numbers.
2024 USEMO, 1
There are $1001$ stacks of coins $S_1, S_2, \dots, S_{1001}$. Initially, stack $S_k$ has $k$ coins for each $k = 1,2,\dots,1001$. In an operation, one selects an ordered pair $(i,j)$ of indices $i$ and $j$ satisfying $1 \le i < j \le 1001$ subject to two conditions:
[list]
[*]The stacks $S_i$ and $S_j$ must each have at least $1$ coin.
[*]The ordered pair $(i,j)$ must [i]not[/i] have been selected before.
[/list]
Then, if $S_i$ and $S_j$ have $a$ coins and $b$ coins respectively, one removes $\gcd(a,b)$ coins from each stack.
What is the maximum number of times this operation could be performed?
[i]Galin Totev[/i]
2007 Stars of Mathematics, 4
Show that any subset of $ A=\{ 1,2,...,2007\} $ having $ 27 $ elements contains three distinct numbers such that the greatest common divisor of two of them divides the other one.
[i]Dan Schwarz[/i]
2018 Peru Cono Sur TST, 5
Find all positive integers $d$ that can be written in the form
$$ d = \gcd(|x^2 - y| , |y^2 - z| , |z^2 - x|), $$
where $x, y, z$ are pairwise coprime positive integers such that $x^2 \neq y$, $y^2 \neq z$, and $z^2 \neq x$.
2000 Korea Junior Math Olympiad, 1
For arbitrary natural number $a$, show that $\gcd(a^3+1, a^7+1)=a+1$.
1998 Slovenia Team Selection Test, 4
Find all positive integers $x$ and $y$ such that $x+y^2+z^3 = xyz$, where $z$ is the greatest common divisor of $x$ and $y$
2008 Indonesia TST, 3
Let $n$ be an arbitrary positive integer.
(a) For every positive integers $a$ and $b$, show that $gcd(n^a + 1, n^b + 1) \le n^{gcd(a,b)} + 1$.
(b) Show that there exist infinitely many composite pairs ($a, b)$, such that each of them is not a multiply of the other number and equality holds in (a).
2022 Kyiv City MO Round 2, Problem 4
Fedir and Mykhailo have three piles of stones: the first contains $100$ stones, the second $101$, the third $102$. They are playing a game, going in turns, Fedir makes the first move. In one move player can select any two piles of stones, let's say they have $a$ and $b$ stones left correspondently, and remove $gcd(a, b)$ stones from each of them. The player after whose move some pile becomes empty for the first time wins. Who has a winning strategy?
As a reminder, $gcd(a, b)$ denotes the greatest common divisor of $a, b$.
[i](Proposed by Oleksii Masalitin)[/i]
2023 European Mathematical Cup, 1
Suppose $a,b,c$ are positive integers such that \[\gcd(a,b)+\gcd(a,c)+\gcd(b,c)=b+c+2023\] Prove that $\gcd(b,c)=2023$.
[i]Remark.[/i] For positive integers $x$ and $y$, $\gcd(x,y)$ denotes their greatest common divisor.
[i]Ivan Novak[/i]