Olympiad problems

2018 Turkey Team Selection Test, 7

For integers $a, b$, call the lattice point with coordinates $(a,b)$ [b]basic[/b] if $gcd(a,b)=1$. A graph takes the basic points as vertices and the edges are drawn in such way: There is an edge between $(a_1,b_1)$ and $(a_2,b_2)$ if and only if $2a_1=2a_2\in \{b_1-b_2, b_2-b_1\}$ or $2b_1=2b_2\in\{a_1-a_2, a_2-a_1\}$. Some of the edges will be erased, such that the remaining graph is a forest. At least how many edges must be erased to obtain this forest? At least how many trees exist in such a forest?

2017 Romania EGMO TST, P2

Tags: gcd , sequence , number theory

Determine all pairs $(a,b)$ of positive integers with the following property: all of the terms of the sequence $(a^n+b^n+1)_{n\geqslant 1}$ have a greatest common divisor $d>1.$

2010 Estonia Team Selection Test, 1

Tags: prime , gcd , power of prime , coprime , number theory

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.

2007 Stars of Mathematics, 4

Tags: number theory , gcd , greatest common divisor

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]

2013 Tournament of Towns, 3

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

Denote by $(a, b)$ the greatest common divisor of $a$ and $b$. Let $n$ be a positive integer such that $(n, n + 1) < (n, n + 2) <... < (n,n + 35)$. Prove that $(n, n + 35) < (n,n + 36)$.

2000 Singapore MO Open, 2

Tags: divisible , prime , divide , gcd , number theory

Show that $240$ divides all numbers of the form $p^4 - q^4$, where p and q are prime numbers strictly greater than $5$. Show also that $240$ is the greatest common divisor of all numbers of the form $p^4 - q^4$, with $p$ and $q$ prime numbers strictly greater than $5$.

2002 Estonia National Olympiad, 1

Tags: divisible , gcd , lcm , divide , number theory

The greatest common divisor $d$ and the least common multiple $u$ of positive integers $m$ and $n$ satisfy the equality $3m + n = 3u + d$. Prove that $m$ is divisible by $n$.

2001 Saint Petersburg Mathematical Olympiad, 11.4

Tags: inequalities , least common multiple , greatest common divisor , gcd , algebra , number theory

For any two positive integers $n>m$ prove the following inequality: $$[m,n]+[m+1,n+1]\geq \dfrac{2nm}{\sqrt{m-n}}$$ As always, $[x,y]$ means the least common multiply of $x,y$. [I]Proposed by A. Golovanov[/i]

2019 Dutch BxMO TST, 4

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

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

2018 Peru Cono Sur TST, 5

Tags: gcd , number theory

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

2022 South East Mathematical Olympiad, 5

Tags: number sequence , gcd , inequalities

Positive sequences $\{a_n\},\{b_n\}$ satisfy:$a_1=b_1=1,b_n=a_nb_{n-1}-\frac{1}{4}(n\geq 2)$. Find the minimum value of $4\sqrt{b_1b_2\cdots b_m}+\sum_{k=1}^m\frac{1}{a_1a_2\cdots a_k}$,where $m$ is a given positive integer.

2023 Indonesia TST, N

Tags: gcd , integer sequence , infinite sequence , coprime , number theory

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

2012 Thailand Mathematical Olympiad, 7

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

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

2012 Dutch IMO TST, 1

Tags: greatest common divisor , gcd , perfect power , prime , number theory

For all positive integers $a$ and $b$, we dene $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$.

2014 Saudi Arabia GMO TST, 2

Tags: gcd , greatest common divisor , number theory

Let $p \ge 2$ be a prime number and $\frac{a_p}{b_p}= 1 +\frac12+ .. +\frac{1}{p^2 -1}$, where $a_p$ and $b_p$ are two relatively prime positive integers. Compute gcd $(p, b_p)$.

2019 Saudi Arabia JBMO TST, 4

Tags: number theory , gcd , combinatorics

Let $14$ 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 $91$. Prove that not all numbers on the paper are different.

2020 Macedonian Nationаl Olympiad, 1

Tags: number theory , fermat's little theorem , gcd , divisibility , prime number

Let $a, b$ be positive integers and $p, q$ be prime numbers for which $p \nmid q - 1$ and $q \mid a^p - b^p$. Prove that $q \mid a - b$.

2021 Czech-Polish-Slovak Junior Match, 3

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

Find the number of pairs $(a, b)$ of positive integers with the property that the greatest common divisor of $a$ and $ b$ is equal to $1\cdot 2 \cdot 3\cdot ... \cdot50$, and the least common multiple of $a$ and $ b$ is $1^2 \cdot 2^2 \cdot 3^2\cdot ... \cdot 50^2$.

1978 Romania Team Selection Test, 2

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

Suppose that $ k,l $ are natural numbers such that $ \gcd (11m-1,k)=\gcd (11m-1, l) , $ for any natural number $ m. $ Prove that there exists an integer $ n $ such that $ k=11^nl. $

2013 Saudi Arabia BMO TST, 2

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

For positive integers $a$ and $b$, $gcd (a, b)$ denote their greatest common divisor and $lcm (a, b)$ their least common multiple. Determine the number of ordered pairs (a,b) of positive integers satisfying the equation $ab + 63 = 20\, lcm (a, b) + 12\, gcd (a,b)$

2001 Saint Petersburg Mathematical Olympiad, 10.6

Tags: least common multiple , greatest common divisor , algebra , gcd , number theory , inequalities

For any positive integers $n>m$ prove the following inequality: $$[m,n]+[m+1,n+1]\geq 2m\sqrt{n}$$ As usual, [x,y] denotes the least common multiply of $x,y$ [I]Proposed by A. Golovanov[/i]

2021 Lotfi Zadeh Olympiad, 3

Tags: number theory , lcm , gcd

Find the least possible value for the fraction $$\frac{lcm(a,b)+lcm(b,c)+lcm(c,a)}{gcd(a,b)+gcd(b,c)+gcd(c,a)}$$ over all distinct positive integers $a, b, c$. By $lcm(x, y)$ we mean the least common multiple of $x, y$ and by $gcd(x, y)$ we mean the greatest common divisor of $x, y$.

2019 Saudi Arabia Pre-TST + Training Tests, 3.3

Tags: number theory , greatest common divisor , gcd

Let $d$ be a positive divisor of a positive integer $m$ and $(a_l), (b_l)$ two arithmetic sequences of positive integers. It is given that $gcd(a_i, b_j) = 1$ and $gcd(a_k, b_n) = m$ for some positive integers $i,j,k,$ and $n$. Prove that there exist positive integers $t$ and $s$ such that $gcd(a_t, b_s) = d$.

2005 Cuba MO, 7

Tags: lcm , gcd , gcd and lcm , number theory

Determine all triples of positive integers $(x, y, z)$ that satisfy $$x < y < z, \ \ gcd(x, y) = 6, \ \ gcd(y, z) = 10, \ \ gcd(z, x) = 8 \ \ and \ \ lcm(x, y, z) = 2400.$$

2005 Thailand Mathematical Olympiad, 9

Tags: number theory , greatest common divisor , gcd

Compute gcd $\left( \frac{135^{90}-45^{90}}{90^2} , 90^2 \right)$