Olympiad problems

1974 IMO Longlists, 24

Let $a_i, b_i$ be coprime positive integers for $i = 1, 2, \ldots , k$, and $m$ the least common multiple of $b_1, \ldots , b_k$. Prove that the greatest common divisor of $a_1 \frac{m}{b_1} , \ldots, a_k \frac{m}{b_k}$ equals the greatest common divisor of $a_1, \ldots , a_k.$

1995 Korea National Olympiad, Day 2

Tags: polynomial , integer polynomial , greatest common divisor , prime , factorization , algebra

Let $a,b$ be integers and $p$ be a prime number such that: (i) $p$ is the greatest common divisor of $a$ and $b$; (ii) $p^2$ divides $a$. Prove that the polynomial $x^{n+2}+ax^{n+1}+bx^{n}+a+b$ cannot be decomposed into the product of two polynomials with integer coefficients and degree greater than $1$.

2016 Taiwan TST Round 3, 4

Tags: greatest common divisor , combinatorics

For a finite set $A$ of positive integers, a partition of $A$ into two disjoint nonempty subsets $A_1$ and $A_2$ is $\textit{good}$ if the least common multiple of the elements in $A_1$ is equal to the greatest common divisor of the elements in $A_2$. Determine the minimum value of $n$ such that there exists a set of $n$ positive integers with exactly $2015$ good partitions.

2024 Ukraine National Mathematical Olympiad, Problem 1

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

Find all pairs $a, b$ of positive integers, for which $$(a, b) + 3[a, b] = a^3 - b^3$$ Here $(a, b)$ denotes the greatest common divisor of $a, b$, and $[a, b]$ denotes the least common multiple of $a, b$. [i]Proposed by Oleksiy Masalitin[/i]

2010 Indonesia TST, 2

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]

2005 AMC 12/AHSME, 12

Tags: analytic geometry , graphing lines , slope , greatest common divisor , geometry , rectangle , number theory

A line passes through $ A(1,1)$ and $ B(100,1000)$. How many other points with integer coordinates are on the line and strictly between $ A$ and $ B$? $ \textbf{(A)}\ 0\qquad \textbf{(B)}\ 2\qquad \textbf{(C)}\ 3\qquad \textbf{(D)}\ 8\qquad \textbf{(E)}\ 9$

2019 IFYM, Sozopol, 5

Tags: number theory , divisibility , greatest common divisor , modulo

Prove that there exist a natural number $a$, for which 999 divides $2^{5n}+a.5^n$ for $\forall$ odd $n\in \mathbb{N}$ and find the smallest such $a$.

KoMaL A Problems 2023/2024, A. 882

Tags: number theory , gcd , greatest common divisor

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]

2014 NIMO Problems, 8

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

For positive integers $a$, $b$, and $c$, define \[ f(a,b,c)=\frac{abc}{\text{gcd}(a,b,c)\cdot\text{lcm}(a,b,c)}. \] We say that a positive integer $n$ is $f@$ if there exist pairwise distinct positive integers $x,y,z\leq60$ that satisfy $f(x,y,z)=n$. How many $f@$ integers are there? [i]Proposed by Michael Ren[/i]

2007 USA Team Selection Test, 3

Tags: trigonometry , induction , algebra , polynomial , algorithm , number theory , greatest common divisor

Let $ \theta$ be an angle in the interval $ (0,\pi/2)$. Given that $ \cos \theta$ is irrational, and that $ \cos k \theta$ and $ \cos[(k \plus{} 1)\theta ]$ are both rational for some positive integer $ k$, show that $ \theta \equal{} \pi/6$.

2013 India Regional Mathematical Olympiad, 6

Tags: number theory , polynomial , root , factorial , greatest common divisor

Let $P(x)=x^3+ax^2+b$ and $Q(x)=x^3+bx+a$, where $a$ and $b$ are nonzero real numbers. Suppose that the roots of the equation $P(x)=0$ are the reciprocals of the roots of the equation $Q(x)=0$. Prove that $a$ and $b$ are integers. Find the greatest common divisor of $P(2013!+1)$ and $Q(2013!+1)$.

2018 India Regional Mathematical Olympiad, 1

Tags: greatest common divisor , circumcircle , geometry

Let $ABC$ be a triangle with integer sides in which $AB<AC$. Let the tangent to the circumcircle of triangle $ABC$ at $A$ intersect the line $BC$ at $D$. Suppose $AD$ is also an integer. Prove that $\gcd(AB,AC)>1$.

1985 ITAMO, 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.

2012 District Olympiad, 3

Tags: superior algebra , function , greatest common divisor

Let $G$ a $n$ elements group. Find all the functions $f:G\rightarrow \mathbb{N}^*$ such that: (a) $f(x)=1$ if and only if $x$ is $G$'s identity; (b) $f(x^k)=\frac{f(x)}{(f(x),k)}$ for any divisor $k$ of $n$, where $(r,s)$ stands for the greatest common divisor of the positive integers $r$ and $s$.

PEN A Problems, 40

Tags: number theory , greatest common divisor , divisibility theory

Determine the greatest common divisor of the elements of the set \[\{n^{13}-n \; \vert \; n \in \mathbb{Z}\}.\]

2023 Bundeswettbewerb Mathematik, 1

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

Determine the greatest common divisor of the numbers $p^6-7p^2+6$ where $p$ runs through the prime numbers $p \ge 11$.

2019-2020 Fall SDPC, 1

Tags: number theory , greatest common divisor

Show that there exists some [b]positive[/b] integer $k$ with $$\gcd(2012,2020)=\gcd(2012+k,2020)$$$$=\gcd(2012,2020+k)=\gcd(2012+k,2020+k).$$

2014 Korea Junior Math Olympiad, 4

Tags: number theory , greatest common divisor , positive integer

Positive integers $p, q, r$ satisfy $gcd(a,b,c) = 1$. Prove that there exists an integer $a$ such that $gcd(p,q+ar) = 1$.

2005 Switzerland - Final Round, 4

Tags: number theory , greatest common divisor , gcd

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

2006 Romania National Olympiad, 4

Tags: calculus , integration , number theory , greatest common divisor , least common multiple , relatively prime

Let $A$ be a set of positive integers with at least 2 elements. It is given that for any numbers $a>b$, $a,b \in A$ we have $\frac{ [a,b] }{ a- b } \in A$, where by $[a,b]$ we have denoted the least common multiple of $a$ and $b$. Prove that the set $A$ has [i]exactly[/i] two elements. [i]Marius Gherghu, Slatina[/i]

1999 Swedish Mathematical Competition, 6

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

$S$ is any sequence of at least $3$ positive integers. A move is to take any $a, b$ in the sequence such that neither divides the other and replace them by gcd $(a,b)$ and lcm $(a,b)$. Show that only finitely many moves are possible and that the final result is independent of the moves made, except possibly for order.

2012 Dutch IMO TST, 1

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

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

2004 IMO Shortlist, 2

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

The function $f$ from the set $\mathbb{N}$ of positive integers into itself is defined by the equality \[f(n)=\sum_{k=1}^{n} \gcd(k,n),\qquad n\in \mathbb{N}.\] a) Prove that $f(mn)=f(m)f(n)$ for every two relatively prime ${m,n\in\mathbb{N}}$. b) Prove that for each $a\in\mathbb{N}$ the equation $f(x)=ax$ has a solution. c) Find all ${a\in\mathbb{N}}$ such that the equation $f(x)=ax$ has a unique solution.

2013 Balkan MO Shortlist, N7

Tags: number theory , greatest common divisor , difference , set

Two distinct positive integers are called [i]close [/i] if their greatest common divisor equals their difference. Show that for any $n$, there exists a set $S$ of $n$ elements such that any two elements of $S$ are close.

2011 Romanian Masters In Mathematics, 2

Tags: algebra , polynomial , modular arithmetic , function , number theory , greatest common divisor , system of equations

Determine all positive integers $n$ for which there exists a polynomial $f(x)$ with real coefficients, with the following properties: (1) for each integer $k$, the number $f(k)$ is an integer if and only if $k$ is not divisible by $n$; (2) the degree of $f$ is less than $n$. [i](Hungary) Géza Kós[/i]