Found problems: 97
2015 Saudi Arabia IMO TST, 1
Let $a, b,c,d$ be positive integers such that $ac+bd$ is divisible by $a^2 +b^2$. Prove that $gcd(c^2 + d^2, a^2 + b^2) > 1$.
Trần Nam Dũng
2009 Tournament Of Towns, 7
Initially a number $6$ is written on a blackboard. At $n$-th step an integer $k$ on the blackboard is replaced by $k+gcd(k,n)$. Prove that at each step the number on the blackboard increases either by $1$ or by a prime number.
2005 Switzerland - Final Round, 4
Determine all sets $M$ of natural numbers such that for every two (not necessarily different) elements $a, b$ from $M$ , $$\frac{a + b}{gcd(a, b)}$$ lies in $M$.
KoMaL A Problems 2023/2024, A. 882
Let $H_1, H_2,\ldots, H_m$ be non-empty subsets of the positive integers, and let $S$ denote their union. Prove that
\[\sum_{i=1}^m \sum_{(a,b)\in H_i^2}\gcd(a,b)\ge\frac1m \sum_{(a,b)\in S^2}\gcd(a,b).\]
[i]Proposed by Dávid Matolcsi, Berkeley[/i]
2012 Dutch IMO TST, 1
For all positive integers $a$ and $b$, we de ne $a @ b = \frac{a - b}{gcd(a, b)}$ .
Show that for every integer $n > 1$, the following holds:
$n$ is a prime power if and only if for all positive integers $m$ such that $m < n$, it holds that $gcd(n, n @m) = 1$.
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]
2021 Cyprus JBMO TST, 2
Find all pairs of natural numbers $(\alpha,\beta)$ for which, if $\delta$ is the greatest common divisor of $\alpha,\beta$, and $\varDelta$ is the least common multiple of $\alpha,\beta$, then
\[ \delta + \Delta = 4(\alpha + \beta) + 2021\]
2013 Peru MO (ONEM), 2
The positive integers $a, b, c$ are such that
$$gcd \,\,\, (a, b, c) = 1,$$
$$gcd \,\,\,(a, b + c) > 1,$$
$$gcd \,\,\,(b, c + a) > 1,$$
$$gcd \,\,\,(c, a + b) > 1.$$
Determine the smallest possible value of $a + b + c$.
Clarification: gcd stands for greatest common divisor.
2021 Turkey Team Selection Test, 9
For which positive integer couples $(k,n)$, the equality
$\Bigg|\Bigg\{{a \in \mathbb{Z}^+: 1\leq a\leq(nk)!, gcd \left(\binom{a}{k},n\right)=1}\Bigg\}\Bigg|=\frac{(nk)!}{6}$
holds?
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]
2025 All-Russian Olympiad, 10.5
Let \( n \) be a natural number. The numbers \( 1, 2, \ldots, n \) are written in a row in some order. For each pair of adjacent numbers, their greatest common divisor (GCD) is calculated and written on a sheet. What is the maximum possible number of distinct values among the \( n - 1 \) GCDs obtained? \\
2019 Saudi Arabia BMO TST, 1
Let $19$ integer numbers are given. Let Hamza writes on the paper the greatest common divisor for each pair of numbers. It occurs that the difference between the biggest and smallest numbers written on the paper is less than $180$. Prove that not all numbers on the paper are different.
2023 Indonesia TST, N
Given an integer $a>1$. Prove that there exists a sequence of positive integers
\[ n_1, n_2, n_3, \ldots \]
Such that
\[ \gcd(a^{n_i+1} + a^{n_i} - 1, \ a^{n_j + 1} + a^{n_j} - 1) =1 \] For every $i \neq j$.
2020 MMATHS, I5
For some positive integers $m>n$, the quantities $a=\text{lcm}(m,n)$ and $b=\gcd(m,n)$ satisfy $a=30b$. If $m-n$ divides $a$, then what is the value of $\frac{m+n}{b}$?
[i]Proposed by Andrew Wu[/i]
2011 Saudi Arabia IMO TST, 2
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$.
2010 NZMOC Camp Selection Problems, 4
Find all positive integer solutions $(a, b)$ to the equation $$\frac{1}{a}+\frac{1}{b}+ \frac{n}{lcm(a,b)}=\frac{1}{gcd(a, b)}$$ for
(i) $n = 2007$;
(ii) $n = 2010$.
2023 Bundeswettbewerb Mathematik, 1
Determine the greatest common divisor of the numbers $p^6-7p^2+6$ where $p$ runs through the prime numbers $p \ge 11$.
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]
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.
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]
2014 Brazil Team Selection Test, 1
For $m$ and $n$ positive integers that are prime to each other, determine the possible values of
$$\gcd (5^m + 7^m, 5^n + 7^n)$$
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$.