Olympiad problems

Russian TST 2020, P2

Given a natural number $n{}$ find the smallest $\lambda$ such that\[\gcd(x(x + 1)\cdots(x + n - 1), y(y + 1)\cdots(y + n - 1)) \leqslant (x-y)^\lambda,\] for any positive integers $y{}$ and $x \geqslant y + n$.

2012 India IMO Training Camp, 2

Tags: greatest common divisor , number theory

Show that there exist infinitely many pairs $(a, b)$ of positive integers with the property that $a+b$ divides $ab+1$, $a-b$ divides $ab-1$, $b>1$ and $a>b\sqrt{3}-1$

2013 Romania Team Selection Test, 1

Tags: floor function , ratio , limit , number theory , greatest common divisor , inequalities , algebra

Suppose that $a$ and $b$ are two distinct positive real numbers such that $\lfloor na\rfloor$ divides $\lfloor nb\rfloor$ for any positive integer $n$. Prove that $a$ and $b$ are positive integers.

2015 IMO Shortlist, N7

Tags: function , number theory , greatest common divisor

Let $\mathbb{Z}_{>0}$ denote the set of positive integers. For any positive integer $k$, a function $f: \mathbb{Z}_{>0} \to \mathbb{Z}_{>0}$ is called [i]$k$-good[/i] if $\gcd(f(m) + n, f(n) + m) \le k$ for all $m \neq n$. Find all $k$ such that there exists a $k$-good function. [i]Proposed by James Rickards, Canada[/i]

2019 Saint Petersburg Mathematical Olympiad, 2

Tags: combinatorics , number theory , greatest common divisor

On the blackboard there are written $100$ different positive integers . To each of these numbers is added the $\gcd$ of the $99$ other numbers . In the new $100$ numbers , is it possible for $3$ of them to be equal. [i] (С. Берлов)[/i]

2018 SIMO, Q1

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

Find all functions $f:\mathbb{N}\setminus\{1\} \rightarrow\mathbb{N}$ such that for all distinct $x,y\in \mathbb{N}$ with $y\ge 2018$, $$\gcd(f(x),y)\cdot \mathrm{lcm}(x,f(y))=f(x)f(y).$$

2007 Singapore Team Selection Test, 3

Tags: analytic geometry , number theory , greatest common divisor , modular arithmetic

Let $A,B,C$ be $3$ points on the plane with integral coordinates. Prove that there exists a point $P$ with integral coordinates distinct from $A,B$ and $C$ such that the interiors of the segments $PA,PB$ and $PC$ do not contain points with integral coordinates.

2008 ISI B.Math Entrance Exam, 10

Tags: number theory , greatest common divisor

If $p$ is a prime number and $a>1$ is a natural number , then show that the greatest common divisor of the two numbers $a-1$ and $\frac{a^p-1}{a-1}$ is either $1$ or $p$ .

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]

2018 Switzerland - Final Round, 2

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

Let $a, b$ and $c$ be natural numbers. Determine the smallest value that the following expression can take: $$\frac{a}{gcd\,\,(a + b, a - c)} + \frac{b}{gcd\,\,(b + c, b - a)} + \frac{c}{gcd\,\,(c + a, c - b)}.$$ . Remark: $gcd \,\, (6, 0) = 6$ and $gcd\,\,(3, -6) = 3$.

2018 Romania Team Selection Tests, 4

Tags: greatest common divisor , bezout s identity , number theory

Let $D$ be a non-empty subset of positive integers and let $d$ be the greatest common divisor of $D$, and let $d\mathbb{Z}=[dn: n \in \mathbb{Z} ]$. Prove that there exists a bijection $f: \mathbb{Z} \rightarrow d\mathbb{Z} $ such that $| f(n+1)-f(n)|$ is member of $D$ for every integer $n$.

2010 China Team Selection Test, 2

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

Given integer $a_1\geq 2$. For integer $n\geq 2$, define $a_n$ to be the smallest positive integer which is not coprime to $a_{n-1}$ and not equal to $a_1,a_2,\cdots, a_{n-1}$. Prove that every positive integer except 1 appears in this sequence $\{a_n\}$.

1996 Flanders Math Olympiad, 2

Tags: greatest common divisor , number theory

Determine the gcd of all numbers of the form $p^8-1$, with p a prime above 5.

1998 Flanders Math Olympiad, 1

Tags: number theory , greatest common divisor , inequalities

Prove there exist positive integers a,b,c for which $a+b+c=1998$, the gcd is maximized, and $0<a<b\leq c<2a$. Find those numbers. Are they unique?

2016 Dutch Mathematical Olympiad, 3

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

Find all possible triples $(a, b, c)$ of positive integers with the following properties: • $gcd(a, b) = gcd(a, c) = gcd(b, c) = 1$, • $a$ is a divisor of $a + b + c$, • $b$ is a divisor of $a + b + c$, • $c$ is a divisor of $a + b + c$. (Here $gcd(x,y)$ is the greatest common divisor of $x$ and $y$.)

2007 JBMO Shortlist, 1

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

Find all the pairs positive integers $(x, y)$ such that $\frac{1}{x}+\frac{1}{y}+\frac{1}{[x, y]}+\frac{1}{(x, y)}=\frac{1}{2}$ , where $(x, y)$ is the greatest common divisor of $x, y$ and $[x, y]$ is the least common multiple of $x, y$.

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.

1998 Estonia National Olympiad, 1

Tags: number theory , greatest common divisor , divisor

Let $d_1$ and $d_2$ be divisors of a positive integer $n$. Suppose that the greatest common divisor of $d_1$ and $n/d_2$ and the greatest common divisor of $d_2$ and $n/d_1$ are equal. Show that $d_1 = d_2$.

2020 Hong Kong TST, 3

Tags: greatest common divisor , number theory

Given a list of integers $2^1+1, 2^2+1, \ldots, 2^{2019}+1$, Adam chooses two different integers from the list and computes their greatest common divisor. Find the sum of all possible values of this greatest common divisor.

2009 Princeton University Math Competition, 8

Tags: number theory , greatest common divisor , algorithm , relatively prime , euclidean algorithm , algebra , difference of squares

Find the largest positive integer $k$ such that $\phi ( \sigma ( 2^k)) = 2^k$. ($\phi(n)$ denotes the number of positive integers that are smaller than $n$ and relatively prime to $n$, and $\sigma(n)$ denotes the sum of divisors of $n$). As a hint, you are given that $641|2^{32}+1$.

2014 Tuymaada Olympiad, 1

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

Four consecutive three-digit numbers are divided respectively by four consecutive two-digit numbers. What minimum number of different remainders can be obtained? [i](A. Golovanov)[/i]

2011 India IMO Training Camp, 3

Tags: number theory , greatest common divisor , search , combinatorics

Let $T$ be a non-empty finite subset of positive integers $\ge 1$. A subset $S$ of $T$ is called [b]good [/b] if for every integer $t\in T$ there exists an $s$ in $S$ such that $gcd(t,s) >1$. Let \[A={(X,Y)\mid X\subseteq T,Y\subseteq T,gcd(x,y)=1 \text{for all} x\in X, y\in Y}\] Prove that : $a)$ If $X_0$ is not [b]good[/b] then the number of pairs $(X_0,Y)$ in $A$ is [b]even[/b]. $b)$ the number of good subsets of $T$ is [b]odd[/b].

2007 India Regional Mathematical Olympiad, 2

Tags: greatest common divisor , search , number theory

Let $ a, b, c$ be three natural numbers such that $ a < b < c$ and $ gcd (c \minus{} a, c \minus{} b) \equal{} 1$. Suppose there exists an integer $ d$ such that $ a \plus{} d, b \plus{} d, c \plus{} d$ form the sides of a right-angled triangle. Prove that there exist integers, $ l,m$ such that $ c \plus{} d \equal{} l^{2} \plus{} m^{2} .$ [b][Weightage 17/100][/b]

2006 MOP Homework, 3

Tags: greatest common divisor , inequalities , number theory

Prove that the following inequality holds with the exception of finitely many positive integers $n$: $\sum^{n}_{i=1}\sum^{n}_{j=1}gcd(i,j)>4n^2$.

1998 Brazil National Olympiad, 3

Tags: combinatorial game , game , number theory , greatest common divisor , least common multiple , combinatorics

Two players play a game as follows: there $n > 1$ rounds and $d \geq 1$ is fixed. In the first round A picks a positive integer $m_1$, then B picks a positive integer $n_1 \not = m_1$. In round $k$ (for $k = 2, \ldots , n$), A picks an integer $m_k$ such that $m_{k-1} < m_k \leq m_{k-1} + d$. Then B picks an integer $n_k$ such that $n_{k-1} < n_k \leq n_{k-1} + d$. A gets $\gcd(m_k,n_{k-1})$ points and B gets $\gcd(m_k,n_k)$ points. After $n$ rounds, A wins if he has at least as many points as B, otherwise he loses. For each $(n, d)$ which player has a winning strategy?