Olympiad problems

2004 India Regional Mathematical Olympiad, 3

Let $\alpha$ and $\beta$ be the roots of the equation $x^2 + mx -1 = 0$ where $m$ is an odd integer. Let $\lambda _n = \alpha ^n + \beta ^n , n \geq 0$ Prove that (A) $\lambda _n$ is an integer (B) gcd ( $\lambda _n , \lambda_{n+1}$) = 1 .

2006 Rioplatense Mathematical Olympiad, Level 3, 3

Tags: greatest common divisor , number theory

An infinite sequence $x_1,x_2,\ldots$ of positive integers satisfies \[ x_{n+2}=\gcd(x_{n+1},x_n)+2006 \] for each positive integer $n$. Does there exist such a sequence which contains exactly $10^{2006}$ distinct numbers?

1986 AIME Problems, 5

Tags: modular arithmetic , algorithm , algebra , polynomial , greatest common divisor , number theory , euclidean algorithm

What is that largest positive integer $n$ for which $n^3+100$ is divisible by $n+10$?

2017 CMIMC Number Theory, 5

Tags: number theory , greatest common divisor

One can define the greatest common divisor of two positive rational numbers as follows: for $a$, $b$, $c$, and $d$ positive integers with $\gcd(a,b)=\gcd(c,d)=1$, write \[\gcd\left(\dfrac ab,\dfrac cd\right) = \dfrac{\gcd(ad,bc)}{bd}.\] For all positive integers $K$, let $f(K)$ denote the number of ordered pairs of positive rational numbers $(m,n)$ with $m<1$ and $n<1$ such that \[\gcd(m,n)=\dfrac{1}{K}.\] What is $f(2017)-f(2016)$?

2014 Costa Rica - Final Round, 3

Tags: number theory , greatest common divisor , gcd

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

2015 China Girls Math Olympiad, 4

Tags: number theory , greatest common divisor

Let $g(n)$ be the greatest common divisor of $n$ and $2015$. Find the number of triples $(a,b,c)$ which satisfies the following two conditions: $1)$ $a,b,c \in$ {$1,2,...,2015$}; $2)$ $g(a),g(b),g(c),g(a+b),g(b+c),g(c+a),g(a+b+c)$ are pairwise distinct.

2021 Iran MO (3rd Round), 1

Tags: combinatorics , graph theory , greatest common divisor

Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a,b,c,d \in S$ with $\gcd(a,b) \neq \gcd(c,d)$. Prove that there exist three pairwise distinct $x,y,z \in S$ such that $\gcd(x,y)=\gcd(y,z) \neq \gcd(z,x)$.

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?

2010 USA Team Selection Test, 6

Tags: number theory , greatest common divisor , combinatorics

Let $T$ be a finite set of positive integers greater than 1. A subset $S$ of $T$ is called [i]good[/i] if for every $t \in T$ there exists some $s \in S$ with $\gcd(s, t) > 1$. Prove that the number of good subsets of $T$ is odd.

2017 CMIMC Number Theory, 2

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

Determine all possible values of $m+n$, where $m$ and $n$ are positive integers satisfying \[\operatorname{lcm}(m,n) - \gcd(m,n) = 103.\]

1966 Dutch Mathematical Olympiad, 2

Tags: number theory , greatest common divisor , gcd , recurrence relation

For all $n$, $t_{n+1} = 2(t_n)^2 - 1$. Prove that gcd $(t_n,t_m) = 1$ if $n \ne m$.

2014 Online Math Open Problems, 14

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

What is the greatest common factor of $12345678987654321$ and $12345654321$? [i]Proposed by Evan Chen[/i]

2002 Baltic Way, 16

Tags: greatest common divisor , quadratic , number theory

Find all nonnegative integers $m$ such that \[a_m=(2^{2m+1})^2+1 \] is divisible by at most two different primes.

2016 Greece Team Selection Test, 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.

2015 China Team Selection Test, 3

Tags: number theory , greatest common divisor , modular arithmetic

Let $a,b$ be two integers such that their gcd has at least two prime factors. Let $S = \{ x \mid x \in \mathbb{N}, x \equiv a \pmod b \} $ and call $ y \in S$ irreducible if it cannot be expressed as product of two or more elements of $S$ (not necessarily distinct). Show there exists $t$ such that any element of $S$ can be expressed as product of at most $t$ irreducible elements.

2022 Assara - South Russian Girl's MO, 4

Tags: greatest common divisor , number theory

Nadya has $2022$ cards, each with a number one or seven written on it. It is known that there are both cards.Nadya looked at all possible $2022$-digit numbers that can be composed from all these cards. What is the largest value that can take the greatest common divisor of all these numbers?

1959 AMC 12/AHSME, 42

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

Given three positive integers $a,b,$ and $c$. Their greatest common divisor is $D$; their least common multiple is $m$. Then, which two of the following statements are true? $ \text{(1)}\ \text{the product MD cannot be less than abc} \qquad$ $\text{(2)}\ \text{the product MD cannot be greater than abc}\qquad$ $\text{(3)}\ \text{MD equals abc if and only if a,b,c are each prime}\qquad$ $\text{(4)}\ \text{MD equals abc if and only if a,b,c are each relatively prime in pairs}$ $\text{ (This means: no two have a common factor greater than 1.)}$ $ \textbf{(A)}\ 1,2 \qquad\textbf{(B)}\ 1,3\qquad\textbf{(C)}\ 1,4\qquad\textbf{(D)}\ 2,3\qquad\textbf{(E)}\ 2,4 $

1995 Brazil National Olympiad, 3

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

For any positive integer $ n>1$, let $ P\left(n\right)$ denote the largest prime divisor of $ n$. Prove that there exist infinitely many positive integers $ n$ for which \[ P\left(n\right)<P\left(n\plus{}1\right)<P\left(n\plus{}2\right).\]

2016 Bosnia and Herzegovina Junior BMO TST, 2

Tags: coloring , greatest common divisor , combinatorics

We color numbers $1,2,3,...,20$ in two colors, blue and yellow, such that both colors are used (not all numbers are colored in one color). Determine number of ways we can color those numbers, such that product of all blue numbers and product of all yellow numbers have greatest common divisor $1$.

2007 Baltic Way, 17

Tags: inequalities , greatest common divisor , number theory

Let $x,y,z$ be positive integers such that $\frac{x+1}{y}+\frac{y+1}{z}+\frac{z+1}{x}$ is an integer. Let $d$ be the greatest common divisor of $x,y$ and $z$. Prove that $d\le \sqrt[3]{xy+yz+zx}$.

2016 India IMO Training Camp, 3

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.

2013 Korea National Olympiad, 5

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

Find all functions $f : \mathbb{N} \rightarrow \mathbb{N} $ satisfying \[ f(mn) = \operatorname{lcm} (m,n) \cdot \gcd( f(m), f(n) ) \] for all positive integer $m,n$.

2009 Romanian Master of Mathematics, 1

Tags: floor function , inequalities , number theory , greatest common divisor , least common multiple , triangle inequality , algebra

For $ a_i \in \mathbb{Z}^ \plus{}$, $ i \equal{} 1, \ldots, k$, and $ n \equal{} \sum^k_{i \equal{} 1} a_i$, let $ d \equal{} \gcd(a_1, \ldots, a_k)$ denote the greatest common divisor of $ a_1, \ldots, a_k$. Prove that $ \frac {d} {n} \cdot \frac {n!}{\prod\limits^k_{i \equal{} 1} (a_i!)}$ is an integer. [i]Dan Schwarz, Romania[/i]

2009 All-Russian Olympiad, 1

Tags: number theory , greatest common divisor , algebra

The denominators of two irreducible fractions are 600 and 700. Find the minimum value of the denominator of their sum (written as an irreducible fraction).

2012 Iran Team Selection Test, 1

Tags: induction , graph theory , greatest common divisor , combinatorics

Is it possible to put $\binom{n}{2}$ consecutive natural numbers on the edges of a complete graph with $n$ vertices in a way that for every path (or cycle) of length $3$ where the numbers $a,b$ and $c$ are written on its edges (edge $b$ is between edges $c$ and $a$), $b$ is divisible by the greatest common divisor of the numbers $a$ and $c$? [i]Proposed by Morteza Saghafian[/i]