Found problems: 583
2009 Albania Team Selection Test, 3
Two people play a game as follows: At the beginning both of them have one point and in every move, one of them can double it's points, or when the other have more point than him, subtract to him his points. Can the two competitors have 2009 and 2002 points respectively? What about 2009 and 2003? Generally which couples of points can they have?
2004 AIME Problems, 10
Let $S$ be the set of integers between $1$ and $2^{40}$ whose binary expansions have exactly two $1$'s. If a number is chosen at random from $S$, the probability that it is divisible by $9$ is $p/q$, where $p$ and $q$ are relatively prime positive integers. Find $p+q$.
2007 Tuymaada Olympiad, 4
Prove that there exists a positive $ c$ such that for every positive integer $ N$ among any $ N$ positive integers not exceeding $ 2N$ there are two numbers whose greatest common divisor is greater than $ cN$.
2012 Iran Team Selection Test, 1
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]
2006 China Team Selection Test, 3
Let $a_{i}$ and $b_{i}$ ($i=1,2, \cdots, n$) be rational numbers such that for any real number $x$ there is:
\[x^{2}+x+4=\sum_{i=1}^{n}(a_{i}x+b)^{2}\]
Find the least possible value of $n$.
1995 Brazil National Olympiad, 3
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).\]
2019 IFYM, Sozopol, 5
Prove that there exist a natural number $a$, for which 999 divides $2^{5n}+a.5^n$ for $\forall$ odd $n\in \mathbb{N}$ and find the smallest such $a$.
2011 India IMO Training Camp, 3
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].
2023 Nordic, P2
Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that $$\gcd(f(x),y)f(xy)=f(x)f(y)$$ for all positive integers $x, y$.
1998 Brazil National Olympiad, 3
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?
2014 NIMO Problems, 4
Let $S$ be the set of integers which are both a multiple of $70$ and a factor of $630{,}000$. A random element $c$ of $S$ is selected. If the probability that there exists an integer $d$ with $\gcd (c,d) = 70$ and $\operatorname{lcm} (c,d) = 630{,}000$ is $\frac mn$ for some relatively prime integers $m$ and $n$, compute $100m+n$.
[i]Proposed by Eugene Chen[/i]
2005 Thailand Mathematical Olympiad, 9
Compute gcd $\left( \frac{135^{90}-45^{90}}{90^2} , 90^2 \right)$
2001 Saint Petersburg Mathematical Olympiad, 9.4
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]
Oliforum Contest IV 2013, 7
For every positive integer $n$, define the number of non-empty subsets $\mathcal N\subseteq \{1,\ldots ,n\}$ such that $\gcd(n\in\mathcal N)=1$. Show that $f(n)$ is a perfect square if and only if $n=1$.
2015 EGMO, 3
Let $n, m$ be integers greater than $1$, and let $a_1, a_2, \dots, a_m$ be positive integers not greater than $n^m$. Prove that there exist positive integers $b_1, b_2, \dots, b_m$ not greater than $n$, such that \[ \gcd(a_1 + b_1, a_2 + b_2, \dots, a_m + b_m) < n, \] where $\gcd(x_1, x_2, \dots, x_m)$ denotes the greatest common divisor of $x_1, x_2, \dots, x_m$.
2003 Italy TST, 1
The incircle of a triangle $ABC$ touches the sides $AB,BC,CA$ at points $D,E,F$ respectively. The line through $A$ parallel to $DF$ meets the line through $C$ parallel to $EF$ at $G$.
$(a)$ Prove that the quadrilateral $AICG$ is cyclic.
$(b)$ Prove that the points $B,I,G$ are collinear.
2006 JBMO ShortLists, 13
Let $ A$ be a subset of the set $ \{1, 2,\ldots,2006\}$, consisting of $ 1004$ elements.
Prove that there exist $ 3$ distinct numbers $ a,b,c\in A$ such that $ gcd(a,b)$:
a) divides $ c$
b) doesn't divide $ c$
2016 Dutch Mathematical Olympiad, 3
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$.)
2001 Brazil National Olympiad, 2
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.
2012 Kosovo Team Selection Test, 5
Prove that the equation
\[\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\]
has infinitly many natural solutions
2014 NIMO Problems, 8
For positive integers $a$, $b$, and $c$, define \[ f(a,b,c)=\frac{abc}{\text{gcd}(a,b,c)\cdot\text{lcm}(a,b,c)}. \] We say that a positive integer $n$ is $f@$ if there exist pairwise distinct positive integers $x,y,z\leq60$ that satisfy $f(x,y,z)=n$. How many $f@$ integers are there?
[i]Proposed by Michael Ren[/i]
2022 Baltic Way, 18
Find all pairs $(a, b)$ of positive integers such that $a \le b$ and
$$ \gcd(x, a) \gcd(x, b) = \gcd(x, 20) \gcd(x, 22) $$
holds for every positive integer $x$.
2015 Grand Duchy of Lithuania, 4
We denote by gcd (...) the greatest common divisor of the numbers in (...). (For example, gcd$(4, 6, 8)=2$ and gcd $(12, 15)=3$.) Suppose that positive integers $a, b, c$ satisfy the following four conditions:
$\bullet$ gcd $(a, b, c)=1$,
$\bullet$ gcd $(a, b + c)>1$,
$\bullet$ gcd $(b, c + a)>1$,
$\bullet$ gcd $(c, a + b)>1$.
a) Is it possible that $a + b + c = 2015$?
b) Determine the minimum possible value that the sum $a+ b+ c$ can take.
1999 Dutch Mathematical Olympiad, 5
Let $c$ be a nonnegative integer, and define $a_n = n^2 + c$ (for $n \geq 1)$. Define $d_n$ as the greatest common divisor of $a_n$ and $a_{n + 1}$.
(a) Suppose that $c = 0$. Show that $d_n = 1,\ \forall n \geq 1$.
(b) Suppose that $c = 1$. Show that $d_n \in \{1,5\},\ \forall n \geq 1$.
(c) Show that $d_n \leq 4c + 1,\ \forall n \geq 1$.
2015 Indonesia MO Shortlist, N4
Suppose that the natural number $a, b, c, d$ satisfy the equation $a^ab^{a + b} = c^cd^{c + d}$.
(a) If gcd $(a, b) = $ gcd $(c, d) = 1$, prove that $a = c$ and $b = d$.
(b) Does the conclusion $a = c$ and $b = d$ apply, without the condition gcd $(a, b) = $ gcd $(c, d) = 1$?