Olympiad problems

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

2013 Kazakhstan National Olympiad, 2

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

Prove that for all natural $n$ there exists $a,b,c$ such that $n=\gcd (a,b)(c^2-ab)+\gcd (b,c)(a^2-bc)+\gcd (c,a)(b^2-ca)$.

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]

2011 NIMO Problems, 11

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

How many ordered pairs of positive integers $(m, n)$ satisfy the system \begin{align*} \gcd (m^3, n^2) & = 2^2 \cdot 3^2, \\ \text{LCM} [m^2, n^3] & = 2^4 \cdot 3^4 \cdot 5^6, \end{align*} where $\gcd(a, b)$ and $\text{LCM}[a, b]$ denote the greatest common divisor and least common multiple of $a$ and $b$, respectively?

2016 Switzerland Team Selection Test, Problem 1

Tags: number theory , greatest common divisor , set

Let $n$ be a natural number. Two numbers are called "unsociable" if their greatest common divisor is $1$. The numbers $\{1,2,...,2n\}$ are partitioned into $n$ pairs. What is the minimum number of "unsociable" pairs that are formed?

2005 Postal Coaching, 4

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

Let $m,n$ be natural numbers and let $d = gcd(m,n)$. Let $x = 2^{m} -1$ and $y= 2^n +1$ (a) If $\frac{m}{d}$ is odd, prove that $gcd(x,y) = 1$ (b) If $\frac{m}{d}$ is even, Find $gcd(x,y)$

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]

2011 NIMO Summer Contest, 11

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

How many ordered pairs of positive integers $(m, n)$ satisfy the system \begin{align*} \gcd (m^3, n^2) & = 2^2 \cdot 3^2, \\ \text{LCM} [m^2, n^3] & = 2^4 \cdot 3^4 \cdot 5^6, \end{align*} where $\gcd(a, b)$ and $\text{LCM}[a, b]$ denote the greatest common divisor and least common multiple of $a$ and $b$, respectively?

2001 Saint Petersburg Mathematical Olympiad, 10.6

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

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]

2005 Baltic Way, 16

Tags: greatest common divisor , number theory

Let $n$ be a positive integer, let $p$ be prime and let $q$ be a divisor of $(n + 1)^p - n^p$. Show that $p$ divides $q - 1$.

Mathematical Minds 2023, P8

Tags: number theory , greatest common divisor

Prove that if $N{}$ is a large enough positive integer, then for any permutation $\pi_1,\ldots,\pi_N$ of $1,\ldots, N$ at least $11\%$ of the pairs $(i,j)$ of indices from $1{}$ to $N{}$ satisfy $\gcd(i,j)=1=\gcd(\pi_i,\pi_j).$ [i]Proposed by Vlad Spătaru[/i]

2016 Argentina National Olympiad Level 2, 5

Tags: number theory , greatest common divisor

For each pair $a, \,b$ of coprime natural numbers, let $d_{a,\,b}$ be the greatest common divisor of $51a + b$ and $a + 51b$. Find the maximum possible value of $d_{a,\,b}$.

2017 China Team Selection Test, 5

Tags: greatest common divisor , number theory

Show that there exists a positive real $C$ such that for any naturals $H,N$ satisfying $H \geq 3, N \geq e^{CH}$, for any subset of $\{1,2,\ldots,N\}$ with size $\lceil \frac{CHN}{\ln N} \rceil$, one can find $H$ naturals in it such that the greatest common divisor of any two elements is the greatest common divisor of all $H$ elements.

2019 Saudi Arabia BMO TST, 1

Tags: number theory , gcd , greatest common divisor

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.

2018 China National Olympiad, 1

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

Let $n$ be a positive integer. Let $A_n$ denote the set of primes $p$ such that there exists positive integers $a,b$ satisfying $$\frac{a+b}{p} \text{ and } \frac{a^n + b^n}{p^2}$$ are both integers that are relatively prime to $p$. If $A_n$ is finite, let $f(n)$ denote $|A_n|$. a) Prove that $A_n$ is finite if and only if $n \not = 2$. b) Let $m,k$ be odd positive integers and let $d$ be their gcd. Show that $$f(d) \leq f(k) + f(m) - f(km) \leq 2 f(d).$$

2014 ITAMO, 3

Tags: greatest common divisor , modular arithmetic , number theory

For any positive integer $n$, let $D_n$ denote the greatest common divisor of all numbers of the form $a^n + (a + 1)^n + (a + 2)^n$ where $a$ varies among all positive integers. (a) Prove that for each $n$, $D_n$ is of the form $3^k$ for some integer $k \ge 0$. (b) Prove that, for all $k\ge 0$, there exists an integer $n$ such that $D_n = 3^k$.

2012 European Mathematical Cup, 2

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

Let $S$ be the set of positive integers. For any $a$ and $b$ in the set we have $GCD(a, b)>1$. For any $a$, $b$ and $c$ in the set we have $GCD(a, b, c)=1$. Is it possible that $S$ has $2012$ elements? [i]Proposed by Ognjen Stipetić.[/i]

1995 IMO Shortlist, 4

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

Find all $ x,y$ and $ z$ in positive integer: $ z \plus{} y^{2} \plus{} x^{3} \equal{} xyz$ and $ x \equal{} \gcd(y,z)$.

PEN A Problems, 37

Tags: number theory , greatest common divisor , modular arithmetic , relatively prime , divisibility theory

If $n$ is a natural number, prove that the number $(n+1)(n+2)\cdots(n+10)$ is not a perfect square.

2001 Brazil National Olympiad, 2

Tags: ceiling function , greatest common divisor , relatively prime , number theory , logarithm

Given $a_0 > 1$, the sequence $a_0, a_1, a_2, ...$ is such that for all $k > 0$, $a_k$ is the smallest integer greater than $a_{k-1}$ which is relatively prime to all the earlier terms in the sequence. Find all $a_0$ for which all terms of the sequence are primes or prime powers.

2002 Tournament Of Towns, 1

Tags: number theory , greatest common divisor , combinatorics

All the species of plants existing in Russia are catalogued (numbered by integers from $2$ to $2000$ ; one after another, without omissions or repetitions). For any pair of species the gcd of their catalogue numbers was calculated and recorded but the catalogue numbers themselves were lost. Is it possible to restore the catalogue numbers from the data in hand?

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 $