Olympiad problems

2000 All-Russian Olympiad, 8

One hundred natural numbers whose greatest common divisor is $1$ are arranged around a circle. An allowed operation is to add to a number the greatest common divisor of its two neighhbors. Prove that we can make all the numbers pairwise copirme in a finite number of moves.

2005 Harvard-MIT Mathematics Tournament, 5

Tags: greatest common divisor , number theory , relatively prime

Ten positive integers are arranged around a circle. Each number is one more than the greatest common divisor of its two neighbors. What is the sum of the ten numbers?

2009 All-Russian Olympiad Regional Round, 11.7

Tags: greatest common divisor , number theory

$a$, $b$ and $c$ are positive integers with $\textrm{gcd}(a,b,c)=1$. Is it true that there exist a positive integer $n$ such that $a^k+b^k+c^k$ is not divisible by $2^n$ for all $k$?

1997 Poland - Second Round, 4

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

There is a set with three elements: (2,3,5). It has got an interesting property: (2*3) mod 5=(2*5) mod 3=(3*5) mod 2. Prove that it is the only one set with such property.

2021 Francophone Mathematical Olympiad, 4

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

Let $\mathbb{N}_{\geqslant 1}$ be the set of positive integers. Find all functions $f \colon \mathbb{N}_{\geqslant 1} \to \mathbb{N}_{\geqslant 1}$ such that, for all positive integers $m$ and $n$: \[\mathrm{GCD}\left(f(m),n\right) + \mathrm{LCM}\left(m,f(n)\right) = \mathrm{GCD}\left(m,f(n)\right) + \mathrm{LCM}\left(f(m),n\right).\] Note: if $a$ and $b$ are positive integers, $\mathrm{GCD}(a,b)$ is the largest positive integer that divides both $a$ and $b$, and $\mathrm{LCM}(a,b)$ is the smallest positive integer that is a multiple of both $a$ and $b$.

2014 Canadian Mathematical Olympiad Qualification, 1

Tags: function , algebra , polynomial , number theory , greatest common divisor

Let $f : \mathbb{Z} \rightarrow \mathbb{Z}^+$ be a function, and define $h : \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}^+$ by $h(x, y) = \gcd (f(x), f(y))$. If $h(x, y)$ is a two-variable polynomial in $x$ and $y$, prove that it must be constant.

Oliforum Contest IV 2013, 1

Tags: modular arithmetic , greatest common divisor , number theory

Given a prime $p$, consider integers $0<a<b<c<d<p$ such that $a^4\equiv b^4\equiv c^4\equiv d^4\pmod{p}$. Show that \[a+b+c+d\mid a^{2013}+b^{2013}+c^{2013}+d^{2013}\]

2007 Tournament Of Towns, 1

Tags: greatest common divisor , least common multiple

[b](a)[/b] Each of Peter and Basil thinks of three positive integers. For each pair of his numbers, Peter writes down the greatest common divisor of the two numbers. For each pair of his numbers, Basil writes down the least common multiple of the two numbers. If both Peter and Basil write down the same three numbers, prove that these three numbers are equal to each other. [b](b)[/b] Can the analogous result be proved if each of Peter and Basil thinks of four positive integers instead?

2002 Junior Balkan Team Selection Tests - Moldova, 1

Tags: number theory , greatest common divisor

For any integer $n$ we define the numbers $a = n^5 + 6n^3 + 8n$ ¸ $b = n^4 + 4n^2 + 3$. Prove that the numbers $a$ and $b$ are relatively prime or have the greatest common factor of $3$.

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})$

PEN A Problems, 68

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

Suppose that $S=\{a_{1}, \cdots, a_{r}\}$ is a set of positive integers, and let $S_{k}$ denote the set of subsets of $S$ with $k$ elements. Show that \[\text{lcm}(a_{1}, \cdots, a_{r})=\prod_{i=1}^{r}\prod_{s\in S_{i}}\gcd(s)^{\left((-1)^{i}\right)}.\]

2009 Putnam, A4

Tags: induction , modular arithmetic , greatest common divisor , quadratic , calculus , integration

Let $ S$ be a set of rational numbers such that (a) $ 0\in S;$ (b) If $ x\in S$ then $ x\plus{}1\in S$ and $ x\minus{}1\in S;$ and (c) If $ x\in S$ and $ x\notin\{0,1\},$ then $ \frac{1}{x(x\minus{}1)}\in S.$ Must $ S$ contain all rational numbers?

1998 Federal Competition For Advanced Students, Part 2, 2

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

Let $P(x) = x^3 - px^2 + qx - r$ be a cubic polynomial with integer roots $a, b, c$. [b](a)[/b] Show that the greatest common divisor of $p, q, r$ is equal to $1$ if the greatest common divisor of $a, b, c$ is equal to $1$. [b](b)[/b] What are the roots of polynomial $Q(x) = x^3-98x^2+98sx-98t$ with $s, t$ positive integers.

1994 India Regional Mathematical Olympiad, 5

Tags: number theory , greatest common divisor

Let $A$ be a set of $16$ positive integers with the property that the product of any two distinct members of $A$ will not exceed 1994. Show that there are numbers $a$ and $b$ in the set $A$ such that the gcd of $a$ and $b$ is greater than 1.

2013 Finnish National High School Mathematics Competition, 2

Tags: inequalities , algorithm , number theory , euclidean algorithm , greatest common divisor , combinatorics

In a particular European city, there are only $7$ day tickets and $30$ day tickets to the public transport. The former costs $7.03$ euro and the latter costs $30$ euro. Aina the Algebraist decides to buy at once those tickets that she can travel by the public transport the whole three year (2014-2016, 1096 days) visiting in the city. What is the cheapest solution?

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]

2001 Macedonia National Olympiad, 1

Tags: modular arithmetic , greatest common divisor , number theory

Prove that if $m$ and $s$ are integers with $ms=2000^{2001}$, then the equation $mx^2-sy^2=3$ has no integer solutions.

2008 Bosnia And Herzegovina - Regional Olympiad, 3

Tags: inequalities , abstract algebra , number theory , greatest common divisor , prime number

Prove that equation $ p^{4}\plus{}q^{4}\equal{}r^{4}$ does not have solution in set of prime numbers.

2016 All-Russian Olympiad, 3

Tags: number theory , greatest common divisor , divisor

Alexander has chosen a natural number $N>1$ and has written down in a line,and in increasing order,all his positive divisors $d_1<d_2<\ldots <d_s$ (where $d_1=1$ and $d_s=N$).For each pair of neighbouring numbers,he has found their greater common divisor.The sum of all these $s-1$ numbers (the greatest common divisors) is equal to $N-2$.Find all possible values of $N$.

2009 USA Team Selection Test, 3

Tags: algebra , polynomial , geometry , geometric transformation , number theory , least common multiple , greatest common divisor

For each positive integer $ n$, let $ c(n)$ be the largest real number such that \[ c(n) \le \left| \frac {f(a) \minus{} f(b)}{a \minus{} b}\right|\] for all triples $ (f, a, b)$ such that --$ f$ is a polynomial of degree $ n$ taking integers to integers, and --$ a, b$ are integers with $ f(a) \neq f(b)$. Find $ c(n)$. [i]Shaunak Kishore.[/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$.

2016 Greece JBMO TST, 3

Tags: number theory , greatest common divisor , divisor

Positive integer $n$ is such that number $n^2-9$ has exactly $6$ positive divisors. Prove that GCD $(n-3, n+3)=1$

2016 Israel Team Selection Test, 4

Tags: greatest common divisor , number theory

Find the greatest common divisor of all numbers of the form $(2^{a^2}\cdot 19^{b^2} \cdot 53^{c^2} + 8)^{16} - 1$ where $a,b,c$ are integers.

2015 Indonesia MO, 2

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

For every natural number $a$ and $b$, define the notation $[a,b]$ as the least common multiple of $a $ and $b$ and the notation $(a,b)$ as the greatest common divisor of $a$ and $b$. Find all $n \in \mathbb{N}$ that satisfies \[ 4 \sum_{k=1}^{n} [n,k] = 1 + \sum_{k=1}^{n} (n,k) + 2n^2 \sum_{k=1}^{n} \frac{1}{(n,k)} \]

1996 Bosnia and Herzegovina Team Selection Test, 2

Tags: euler , number theory , eulers function , greatest common divisor , function

$a)$ Let $m$ and $n$ be positive integers. If $m>1$ prove that $ n \mid \phi(m^n-1)$ where $\phi$ is Euler function $b)$ Prove that number of elements in sequence $1,2,...,n$ $(n \in \mathbb{N})$, which greatest common divisor with $n$ is $d$, is $\phi\left(\frac{n}{d}\right)$