This website contains problems from math contests. Problems and corresponding tags were obtained from the Art of Problem Solving website.

Tags were heavily modified to better represent problems.

AND:
OR:
NO:

Found problems: 583

2007 India Regional Mathematical Olympiad, 2
Tags: number theory , search , greatest common divisor
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]

1973 Poland - Second Round, 6
Tags: number theory , greatest common divisor
Prove that for every non-negative integer $m$ there exists a polynomial w with integer coefficients such that $2^m$ is the greatest common divisor of the numbers $$ a_n = 3^n + w(n), n = 0, 1, 2, ....$$

2022 Assara - South Russian Girl's MO, 4
Tags: number theory , greatest common divisor
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?

2016 Belarus Team Selection Test, 3
Tags: combinatorics , greatest common divisor
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 AMC 12/AHSME, 23
Tags: geometric transformation , rotation , geometry , number theory , greatest common divisor
$ ABCD$ is a square of side length $ \sqrt{3} + 1 $. Point $ P $ is on $ \overline{AC} $ such that $ AP = \sqrt{2} $. The square region bounded by $ ABCD $ is rotated $ 90^{\circ} $ counterclockwise with center $ P $, sweeping out a region whose area is $ \frac{1}{c} (a \pi + b) $, where $a $, $b$, and $ c $ are positive integers and $ \text{gcd}(a,b,c) = 1 $. What is $ a + b + c $? $\textbf{(A)} \ 15 \qquad \textbf{(B)} \ 17 \qquad \textbf{(C)} \ 19 \qquad \textbf{(D)} \ 21 \qquad \textbf{(E)} \ 23 $

2009 China Second Round Olympiad, 3
Tags: greatest common divisor , number theory
Let $k,l$ be two given integers. Prove that there exist infinite many integers $m\ge k$ such that $\gcd\left(\binom{m}{k},l\right)=1$.

2019 Dutch IMO TST, 3
Tags: greatest common divisor , number theory , maximum , gcd
Let $n$ be a positive integer. Determine the maximum value of $gcd(a, b) + gcd(b, c) + gcd(c, a)$ for positive integers $a, b, c$ such that $a + b + c = 5n$.

2007 Princeton University Math Competition, 10
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$?

2013 Balkan MO Shortlist, N7
Tags: difference , set , number theory , greatest common divisor
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.

1971 IMO Longlists, 23
Tags: greatest common divisor , number theory
Find all integer solutions of the equation \[x^2+y^2=(x-y)^3.\]

1998 Hong kong National Olympiad, 3
Tags: relatively prime , number theory , greatest common divisor
Given $s,t$ are non-zero integers, $(x,y) $ is an integer pair , A transformation is to change pair $(x,y)$ into pair $(x+t,y-s)$ . If the two integers in a certain pair becoems relatively prime after several tranfomations , then we call the original integer pair "a good pair" . (1) Is $(s,t)$ a good pair ? (2) Prove :for any $s$ and $t$ , there exists pair $(x,y)$ which is " a good pair".

1990 AIME Problems, 10
Tags: greatest common divisor , least common multiple , number theory , complex number , relatively prime , modular arithmetic , trigonometry
The sets $A = \{z : z^{18} = 1\}$ and $B = \{w : w^{48} = 1\}$ are both sets of complex roots of unity. The set $C = \{zw : z \in A \ \text{and} \ w \in B\}$ is also a set of complex roots of unity. How many distinct elements are in $C$?

2008 Romania Team Selection Test, 5
Tags: greatest common divisor , algebra , modular arithmetic , number theory , polynomial
Find the greatest common divisor of the numbers \[ 2^{561}\minus{}2, 3^{561}\minus{}3, \ldots, 561^{561}\minus{}561.\]

PEN N Problems, 16
Tags: more sequences , greatest common divisor
Does there exist positive integers $a_{1}<a_{2}<\cdots<a_{100}$ such that for $2 \le k \le 100$, the greatest common divisor of $a_{k-1}$ and $a_{k}$ is greater than the greatest common divisor of $a_{k}$ and $a_{k+1}$?

2024 New Zealand MO, 4
Tags: number theory , greatest common divisor
Determine all positive integers $n$ less than $2024$ such that for all positive integers $x$, the greatest common divisor of $9x + 1$ and $nx+1$ is $1$.

2023 Bulgaria National Olympiad, 1
Tags: graph theory , number theory , greatest common divisor , combinatorics
Let $G$ be a graph on $n\geq 6$ vertices and every vertex is of degree at least 3. If $C_{1}, C_{2}, \dots, C_{k}$ are all the cycles in $G$, determine all possible values of $\gcd(|C_{1}|, |C_{2}|, \dots, |C_{k}|)$ where $|C|$ denotes the number of vertices in the cycle $C$.

2014 Canadian Mathematical Olympiad Qualification, 1
Tags: greatest common divisor , number theory , polynomial , function , algebra
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.

2023 South Africa National Olympiad, 3
Tags: greatest common divisor , least common multiple , number theory
Consider $2$ positive integers $a,b$ such that $a+2b=2020$. (a) Determine the largest possible value of the greatest common divisor of $a$ and $b$. (b) Determine the smallest possible value of the least common multiple of $a$ and $b$.

2011 Middle European Mathematical Olympiad, 8
Tags: modular arithmetic , arithmetic sequence , system of equations , number theory , greatest common divisor , relatively prime , algebra
We call a positive integer $n$ [i]amazing[/i] if there exist positive integers $a, b, c$ such that the equality \[n = (b, c)(a, bc) + (c, a)(b, ca) + (a, b)(c, ab)\] holds. Prove that there exist $2011$ consecutive positive integers which are [i]amazing[/i]. [b]Note.[/b] By $(m, n)$ we denote the greatest common divisor of positive integers $m$ and $n$.

2023 Switzerland - Final Round, 3
Tags: greatest common divisor , number theory
Let $x,y$ and $a_0, a_1, a_2, \cdots $ be integers satisfying $a_0 = a_1 = 0$, and $$a_{n+2} = xa_{n+1}+ya_n+1$$for all integers $n \geq 0$. Let $p$ be any prime number. Show that $\gcd(a_p,a_{p+1})$ is either equal to $1$ or greater than $\sqrt{p}$.

1985 IMO Longlists, 54
Tags: algorithm , number theory , greatest common divisor , binomial theorem , modular arithmetic , induction , algebra
Set $S_n = \sum_{p=1}^n (p^5+p^7)$. Determine the greatest common divisor of $S_n$ and $S_{3n}.$

2013 Rioplatense Mathematical Olympiad, Level 3, 5
Tags: greatest common divisor , algorithm , modular arithmetic , number theory
Find all positive integers $n$ for which there exist two distinct numbers of $n$ digits, $\overline{a_1a_2\ldots a_n}$ and $\overline{b_1b_2\ldots b_n}$, such that the number of $2n$ digits $\overline{a_1a_2\ldots a_nb_1b_2\ldots b_n}$ is divisible by $\overline{b_1b_2\ldots b_na_1a_2\ldots a_n}$.

2012 JBMO TST - Turkey, 2
Tags: gcd , modular arithmetic , greatest common divisor , number theory
Find all positive integers $m,n$ and prime numbers $p$ for which $\frac{5^m+2^np}{5^m-2^np}$ is a perfect square.

1981 All Soviet Union Mathematical Olympiad, 322
Tags: consecutive , greatest common divisor , number theory
Find $n$ such that each of the numbers $n,(n+1),...,(n+20)$ has the common divider greater than one with the number $30030 = 2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13$.

2012 Albania Team Selection Test, 4
Tags: least common multiple , number theory , greatest common divisor , relatively prime
Find all couples of natural numbers $(a,b)$ not relatively prime ($\gcd(a,b)\neq\ 1$) such that \[\gcd(a,b)+9\operatorname{lcm}[a,b]+9(a+b)=7ab.\]