Found problems: 583
2009 China Team Selection Test, 3
Let $ (a_{n})_{n\ge 1}$ be a sequence of positive integers satisfying $ (a_{m},a_{n}) = a_{(m,n)}$ (for all $ m,n\in N^ +$). Prove that for any $ n\in N^ + ,\prod_{d|n}{a_{d}^{\mu (\frac {n}{d})}}$ is an integer. where $ d|n$ denotes $ d$ take all positive divisors of $ n.$ Function $ \mu (n)$ is defined as follows: if $ n$ can be divided by square of certain prime number, then $ \mu (1) = 1;\mu (n) = 0$; if $ n$ can be expressed as product of $ k$ different prime numbers, then $ \mu (n) = ( - 1)^k.$
2005 AMC 12/AHSME, 17
How many distinct four-tuples $ (a,b,c,d)$ of rational numbers are there with
$ a \log_{10} 2 \plus{} b \log_{10} 3 \plus{} c \log_{10} 5 \plus{} d \log_{10} 7 \equal{} 2005$?
$ \textbf{(A)}\ 0\qquad
\textbf{(B)}\ 1\qquad
\textbf{(C)}\ 17\qquad
\textbf{(D)}\ 2004\qquad
\textbf{(E)}\ \text{infinitely many}$
2021 Francophone Mathematical Olympiad, 4
Let $\mathbb{N}_{\geqslant 1}$ be the set of positive integers.
Find all functions $f \colon \mathbb{N}_{\geqslant 1} \to \mathbb{N}_{\geqslant 1}$ such that, for all positive integers $m$ and $n$:
\[\mathrm{GCD}\left(f(m),n\right) + \mathrm{LCM}\left(m,f(n)\right) =
\mathrm{GCD}\left(m,f(n)\right) + \mathrm{LCM}\left(f(m),n\right).\]
Note: if $a$ and $b$ are positive integers, $\mathrm{GCD}(a,b)$ is the largest positive integer that divides both $a$ and $b$, and $\mathrm{LCM}(a,b)$ is the smallest positive integer that is a multiple of both $a$ and $b$.
2006 Estonia Math Open Senior Contests, 4
Martin invented the following algorithm. Let two irreducible fractions $ \frac{s_1}{t_1}$ and $ \frac{s_2}{t_2}$ be given as inputs, with the numerators and denominators being positive integers. Divide $ s_1$ and $ s_2$ by their greatest common divisor $ c$ and obtain $ a_1$ and $ a_2$, respectively. Similarily, divide $ t_1$ and $ t_2$ by their greatest common divisor $ d$ and obtain $ b_1$ and $ b_2$, respectively. After that, form a new fraction $ \frac{a_1b_2 \plus{} a_2b_1}{t_1b_2}$, reduce it, and multiply the numerator of the result by $ c$. Martin claims that this algorithm always finds the sum of the original fractions as an irreducible fraction. Is his claim correct?
PEN O Problems, 59
Let $a_{1} < a_{2} < a_{3} < \cdots $ be an infinite increasing sequence of positive integers in which the number of prime factors of each term, counting repeated factors, is never more than $1987$. Prove that it is always possible to extract from $A$ an infinite subsequence $b_{1} < b_{2} < b_{3} < \cdots $ such that the greatest common divisor $(b_i, b_j)$ is the same number for every pair of its terms.
2007 Princeton University Math Competition, 5
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 Switzerland - Final Round, 1
Find all triples $(a, b, c)$ of natural numbers such that the sets
$$\{ gcd (a, b), gcd(b, c), gcd(c, a), lcm (a, b), lcm (b, c), lcm (c, a)\}$$ and
$$\{2, 3, 5, 30, 60\}$$
are the same.
Remark: For example, the sets $\{1, 2013\}$ and $\{1, 1, 2013\}$ are equal.
2002 India IMO Training Camp, 9
On each day of their tour of the West Indies, Sourav and Srinath have either an apple or an orange for breakfast. Sourav has oranges for the first $m$ days, apples for the next $m$ days, followed by oranges for the next $m$ days, and so on. Srinath has oranges for the first $n$ days, apples for the next $n$ days, followed by oranges for the next $n$ days, and so on.
If $\gcd(m,n)=1$, and if the tour lasted for $mn$ days, on how many days did they eat the same kind of fruit?
2011 Romanian Master of Mathematics, 2
Determine all positive integers $n$ for which there exists a polynomial $f(x)$ with real coefficients, with the following properties:
(1) for each integer $k$, the number $f(k)$ is an integer if and only if $k$ is not divisible by $n$;
(2) the degree of $f$ is less than $n$.
[i](Hungary) Géza Kós[/i]
2012 Dutch IMO TST, 1
For all positive integers $a$ and $b$, we de ne $a @ b = \frac{a - b}{gcd(a, b)}$ .
Show that for every integer $n > 1$, the following holds:
$n$ is a prime power if and only if for all positive integers $m$ such that $m < n$, it holds that $gcd(n, n @m) = 1$.
1998 Federal Competition For Advanced Students, Part 2, 2
Let $P(x) = x^3 - px^2 + qx - r$ be a cubic polynomial with integer roots $a, b, c$.
[b](a)[/b] Show that the greatest common divisor of $p, q, r$ is equal to $1$ if the greatest common divisor of $a, b, c$ is equal to $1$.
[b](b)[/b] What are the roots of polynomial $Q(x) = x^3-98x^2+98sx-98t$ with $s, t$ positive integers.
2007 All-Russian Olympiad Regional Round, 10.7
Given an integer $ n>6$. Consider those integers $ k\in (n(n\minus{}1),n^{2})$ which are coprime with $ n$. Prove that the greatest common divisor of the considered numbers is $ 1$.
2016 Latvia Baltic Way TST, 16
What is the largest possible value of the expression $$gcd \,\,\, (n^2 + 3, (n + 1)^2 + 3 )$$ for naturals $n$?
[hide]original wording]Kāda ir izteiksmes LKD (n2 + 3, (n + 1)2 + 3) lielākā iespējamā vērtība naturāliem n? [/hide]
1996 Spain Mathematical Olympiad, 1
The natural numbers $a$ and $b$ are such that $ \frac{a+1}{b}+ \frac{b+1}{a}$ is an integer. Show that the greatest common divisor of a and b is not greater than $\sqrt{a+b}$.
2011 Canadian Mathematical Olympiad Qualification Repechage, 8
Determine all pairs $(n,m)$ of positive integers for which there exists an infinite sequence $\{x_k\}$ of $0$'s and $1$'s with the properties that if $x_i=0$ then $x_{i+m}=1$ and if $x_i = 1$ then $x_{i+n} = 0.$
2019 USA TSTST, 7
Let $f: \mathbb Z\to \{1, 2, \dots, 10^{100}\}$ be a function satisfying
$$\gcd(f(x), f(y)) = \gcd(f(x), x-y)$$
for all integers $x$ and $y$. Show that there exist positive integers $m$ and $n$ such that $f(x) = \gcd(m+x, n)$ for all integers $x$.
[i]Ankan Bhattacharya[/i]
1990 Vietnam Team Selection Test, 1
Let $ T$ be a finite set of positive integers, satisfying the following conditions:
1. For any two elements of $ T$, their greatest common divisor and their least common multiple are also elements of $ T$.
2. For any element $ x$ of $ T$, there exists an element $ x'$ of $ T$ such that $ x$ and $ x'$ are relatively prime, and their least common multiple is the largest number in $ T$.
For each such set $ T$, denote by $ s(T)$ its number of elements. It is known that $ s(T) < 1990$; find the largest value $ s(T)$ may take.
2024 Mexican University Math Olympiad, 3
Consider a multiplicative function \( f \) from the positive integers to the unit disk centered at the origin, that is, \( f : \mathbb{Z}^+ \to D^2 \subseteq \mathbb{C} \) such that \( f(mn) = f(m)f(n) \). Prove that for every \( \epsilon > 0 \) and every integer \( k > 0 \), there exist \( k \) distinct positive integers \( a_1, a_2, \dots, a_k \) such that \( \text{gcd}(a_1, a_2, \dots, a_k) = k \) and \( d(f(a_i), f(a_j)) < \epsilon \) for all \( i, j = 1, \dots, k \).
2018 AMC 10, 23
How many ordered pairs $(a, b)$ of positive integers satisfy the equation
$$a\cdot b + 63 = 20\cdot \text{lcm}(a, b) + 12\cdot\text{gcd}(a,b),$$
where $\text{gcd}(a,b)$ denotes the greatest common divisor of $a$ and $b$, and $\text{lcm}(a,b)$ denotes their least common multiple?
$\textbf{(A)}\ 0\qquad\textbf{(B)}\ 2\qquad\textbf{(C)}\ 4\qquad\textbf{(D)}\ 6\qquad\textbf{(E)}\ 8$
2014 Online Math Open Problems, 28
Let $S$ be the set of all pairs $(a,b)$ of real numbers satisfying $1+a+a^2+a^3 = b^2(1+3a)$ and $1+2a+3a^2 = b^2 - \frac{5}{b}$. Find $A+B+C$, where \[
A = \prod_{(a,b) \in S} a
, \quad
B = \prod_{(a,b) \in S} b
, \quad \text{and} \quad
C = \sum_{(a,b) \in S} ab.
\][i]Proposed by Evan Chen[/i]
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$.
2017 Costa Rica - Final Round, 2
Determine the greatest common divisor of the numbers:
$$5^5-5, 7^7-7, 9^9-9 ,..., 2017^{2017}-2017,$$
2005 Baltic Way, 16
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$.
1994 India Regional Mathematical Olympiad, 5
Let $A$ be a set of $16$ positive integers with the property that the product of any two distinct members of $A$ will not exceed 1994. Show that there are numbers $a$ and $b$ in the set $A$ such that the gcd of $a$ and $b$ is greater than 1.
2008 Bosnia And Herzegovina - Regional Olympiad, 3
Prove that equation $ p^{4}\plus{}q^{4}\equal{}r^{4}$ does not have solution in set of prime numbers.