Olympiad problems

2013 Silk Road, 1

Determine all pairs of positive integers $m, n,$ satisfying the equality $(2^{m}+1;2^n+1)=2^{(m;n)}+1$ , where $(a;b)$ is the greatest common divisor

1981 Brazil National Olympiad, 5

Tags: combinatorics , game strategy , greatest common divisor , number theory

Two thieves stole a container of $8$ liters of wine. How can they divide it into two parts of $4$ liters each if all they have is a $3 $ liter container and a $5$ liter container? Consider the general case of dividing $m+n$ liters into two equal amounts, given a container of $m$ liters and a container of $n$ liters (where $m$ and $n$ are positive integers). Show that it is possible iff $m+n$ is even and $(m+n)/2$ is divisible by $gcd(m,n)$.

2015 NIMO Problems, 8

Tags: number theory , greatest common divisor

For an integer $30 \le k \le 70$, let $M$ be the maximum possible value of \[ \frac{A}{\gcd(A,B)} \quad \text{where } A = \dbinom{100}{k} \text{ and } B = \dbinom{100}{k+3}. \] Find the remainder when $M$ is divided by $1000$. [i]Based on a proposal by Michael Tang[/i]

2008 Romania Team Selection Test, 5

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

Find the greatest common divisor of the numbers \[ 2^{561}\minus{}2, 3^{561}\minus{}3, \ldots, 561^{561}\minus{}561.\]

2012 Junior Balkan MO, 4

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

Find all positive integers $x,y,z$ and $t$ such that $2^x3^y+5^z=7^t$.

2014 Costa Rica - Final Round, 3

Tags: greatest common divisor , gcd , number theory

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

Oliforum Contest IV 2013, 5

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

Let $x,y,z$ be distinct positive integers such that $(y+z)(z+x)=(x+y)^2$ . Show that \[x^2+y^2>8(x+y)+2(xy+1).\] (Paolo Leonetti)

2007 Pre-Preparation Course Examination, 18

Tags: greatest common divisor , number theory

Prove that the equation $x^3+y^3+z^3=t^4$ has infinitely many solutions in positive integers such that $\gcd(x,y,z,t)=1$. [i]Mihai Pitticari & Sorin Rǎdulescu[/i]

2007 Princeton University Math Competition, 5

Tags: greatest common divisor

Let $f_n$ be the Fibonacci numbers, defined by $f_0 = 1$, $f_1 = 1$, and $f_n = f_{n-1}+f_{n-2}$. For each $i$, $1 \le i \le 200$, we calculate the greatest common divisor $g_i$ of $f_i$ and $f_{2007}$. What is the sum of the distinct values of $g_i$?

2009 Harvard-MIT Mathematics Tournament, 2

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

Suppose N is a $6$-digit number having base-$10$ representation $\underline{a}\text{ }\underline{b}\text{ }\underline{c}\text{ }\underline{d}\text{ }\underline{e}\text{ }\underline{f}$. If $N$ is $6/7$ of the number having base-$10$ representation $\underline{d}\text{ }\underline{e}\text{ }\underline{f}\text{ }\underline{a}\text{ }\underline{b}\text{ }\underline{c}$, find $N$.

2019 CMIMC, 4

Tags: greatest common divisor , number theory

Determine the sum of all positive integers $n$ between $1$ and $100$ inclusive such that \[\gcd(n,2^n - 1) = 3.\]

2018 SIMO, Q1

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

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

2001 Saint Petersburg Mathematical Olympiad, 9.4

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

Let $a,b,c\in\mathbb{Z^{+}}$ such that $$(a^2-1, b^2-1, c^2-1)=1$$ Prove that $$(ab+c, bc+a, ca+b)=(a,b,c)$$ (As usual, $(x,y,z)$ means the greatest common divisor of numbers $x,y,z$) [I]Proposed by A. Golovanov[/i]

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.

2020 Mediterranean Mathematics Olympiad, 1

Tags: number theory , greatest common divisor

Determine all integers $m\ge2$ for which there exists an integer $n\ge1$ with $\gcd(m,n)=d$ and $\gcd(m,4n+1)=1$. [i]Proposed by Gerhard Woeginger, Austria[/i]

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.

2010 Putnam, A4

Tags: modular arithmetic , number theory , greatest common divisor , putnam number theory , logarithm

Prove that for each positive integer $n,$ the number $10^{10^{10^n}}+10^{10^n}+10^n-1$ is not prime.

2014 India Regional Mathematical Olympiad, 3

Tags: greatest common divisor , number theory

let $m,n$ be natural number with $m>n$ . find all such pairs of $(m,n) $ such that $gcd(n+1,m+1)=gcd(n+2,m+2) =..........=gcd(m, 2m-n) = 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.

2003 Hungary-Israel Binational, 1

Tags: greatest common divisor , combinatorics

Two players play the following game. They alternately write divisors of $100!$ on the blackboard, not repeating any of the numbers written before. The player after whose move the greatest common divisor of the written numbers equals $1,$ loses the game. Which player has a winning strategy?

2013 Korea Junior Math Olympiad, 6

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

2008 Romania National Olympiad, 2

Tags: geometry , rectangle , ratio , greatest common divisor , relatively prime , number theory

A rectangle can be divided by parallel lines to its sides into 200 congruent squares, and also in 288 congruent squares. Prove that the rectangle can also be divided into 392 congruent squares.

2020-IMOC, N6

Tags: greatest common divisor , number theory

$\textbf{N6.}$ Let $a,b$ be positive integers. If $a,b$ satisfy that \begin{align*} \frac{a+1}{b} + \frac{b+1}{a} \end{align*} is also a positive integer, show that \begin{align*} \frac{a+b}{gcd(a,b)^2} \end{align*} is a Fibonacci number. [i]Proposed by usjl[/i]

2014 Argentina National Olympiad Level 2, 6

Tags: greatest common divisor , number theory

Let $a, b, c$ be distinct positive integers with sum $547$ and let $d$ be the greatest common divisor of the three numbers $ab+1, bc+1, ca+1$. Find the maximal possible value of $d$.

2009 BAMO, 3

Tags: greatest common divisor , set , number theory

A set $S$ of positive integers is called magic if for any two distinct members of $S, i$ and $j$, $\frac{i+ j}{GCD(i, j)}$is also a member of $S$. The $GCD$, or greatest common divisor, of two positive integers is the largest integer that divides evenly into both of them; for example, $GCD(36,80) = 4$. Find and describe all finite magic sets.