Found problems: 583
2006 AMC 12/AHSME, 14
Two farmers agree that pigs are worth $ \$300$ and that goats are worth $ \$210$. When one farmer owes the other money, he pays the debt in pigs or goats, with ``change'' received in the form of goats or pigs as necessary. (For example, a $ \$390$ debt could be paid with two pigs, with one goat received in change.) What is the amount of the smallest positive debt that can be resolved in this way?
$ \textbf{(A) } \$5\qquad \textbf{(B) } \$10\qquad \textbf{(C) } \$30\qquad \textbf{(D) } \$90\qquad \textbf{(E) } \$210$
1995 USAMO, 4
Suppose $\, q_{0}, \, q_{1}, \, q_{2}, \ldots \; \,$ is an infinite sequence of integers satisfying the following two conditions:
(i) $\, m-n \,$ divides $\, q_{m}-q_{n}\,$ for $\, m > n \geq 0,$
(ii) there is a polynomial $\, P \,$ such that $\, |q_{n}| < P(n) \,$ for all $\, n$
Prove that there is a polynomial $\, Q \,$ such that $\, q_{n}= Q(n) \,$ for all $\, n$.
2023 AMC 12/AHSME, 15
Suppose $a$, $b$, and $c$ are positive integers such that \[\frac{a}{14}+\frac{b}{15}=\frac{c}{210}.\] Which of the following statements are necessarily true?
I. If $\gcd(a,14)=1$ or $\gcd(b,15)=1$ or both, then $\gcd(c,210)=1$.
II. If $\gcd(c,210)=1$, then $\gcd(a,14)=1$ or $\gcd(b,15)=1$ or both.
III. $\gcd(c,210)=1$ if and only if $\gcd(a,14)=\gcd(b,15)=1$.
$\textbf{(A)}~\text{I, II, and III}\qquad\textbf{(B)}~\text{I only}\qquad\textbf{(C)}~\text{I and II only}\qquad\textbf{(D)}~\text{III only}\qquad\textbf{(E)}~\text{II and III only}$
2013 India Regional Mathematical Olympiad, 5
Let $a_1,b_1,c_1$ be natural numbers. We define \[a_2=\gcd(b_1,c_1),\,\,\,\,\,\,\,\,b_2=\gcd(c_1,a_1),\,\,\,\,\,\,\,\,c_2=\gcd(a_1,b_1),\] and \[a_3=\operatorname{lcm}(b_2,c_2),\,\,\,\,\,\,\,\,b_3=\operatorname{lcm}(c_2,a_2),\,\,\,\,\,\,\,\,c_3=\operatorname{lcm}(a_2,b_2).\] Show that $\gcd(b_3,c_3)=a_2$.
2022 MMATHS, 8
Let $S = \{1, 2, 3, 5, 6, 10, 15, 30\}$. For each of the $64$ ordered pairs $(a, b)$ of elements of $S$, AJ computes $gcd(a, b)$. They then sum all of the numbers they computed. What is AJ’s sum?
1997 Poland - Second Round, 4
There is a set with three elements: (2,3,5). It has got an interesting property: (2*3) mod 5=(2*5) mod 3=(3*5) mod 2. Prove that it is the only one set with such property.
2008 CHKMO, 4
Determine if there exist positive integer pairs $(m,n)$, such that
(i) the greatest common divisor of m and $n$ is $1$, and $m \le 2007$,
(ii) for any $k=1,2,..., 2007$, $\big[\frac{nk}{m}\big]=\big[\sqrt2 k\big]$ .
(Here $[x]$ stands for the greatest integer less than or equal to $x$.)
2008 ISI B.Stat Entrance Exam, 8
In how many ways can you divide the set of eight numbers $\{2,3,\cdots,9\}$ into $4$ pairs such that no pair of numbers has $\text{gcd}$ equal to $2$?
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 \).
2011-2012 SDML (High School), 15
Let $\left(1+\sqrt{2}\right)^{2012}=a+b\sqrt{2}$, where $a$ and $b$ are integers. The greatest common divisor of $b$ and $81$ is
$\text{(A) }1\qquad\text{(B) }3\qquad\text{(C) }9\qquad\text{(D) }27\qquad\text{(E) }81$
2022 Indonesia TST, N
For each natural number $n$, let $f(n)$ denote the number of ordered integer pairs $(x,y)$ satisfying the following equation:
\[ x^2 - xy + y^2 = n. \]
a) Determine $f(2022)$.
b) Determine the largest natural number $m$ such that $m$ divides $f(n)$ for every natural number $n$.
1996 Bosnia and Herzegovina Team Selection Test, 2
$a)$ Let $m$ and $n$ be positive integers. If $m>1$ prove that $ n \mid \phi(m^n-1)$ where $\phi$ is Euler function
$b)$ Prove that number of elements in sequence $1,2,...,n$ $(n \in \mathbb{N})$, which greatest common divisor with $n$ is $d$, is $\phi\left(\frac{n}{d}\right)$
2011 Singapore Senior Math Olympiad, 2
Determine if there is a set $S$ of 2011 positive integers so that for every pair $m,n$ of distinct elements of $S$, $|m-n|=(m,n)$. Here $(m,n)$ denotes the greatest common divisor of $m$ and $n$.
PEN A Problems, 37
If $n$ is a natural number, prove that the number $(n+1)(n+2)\cdots(n+10)$ is not a perfect square.
2007 Singapore Junior Math Olympiad, 3
Let $n$ be a positive integer and $d$ be the greatest common divisor of $n^2+1$ and $(n + 1)^2 + 1$. Find all the possible values of $d$. Justify your answer.
2014 Online Math Open Problems, 23
For a prime $q$, let $\Phi_q(x)=x^{q-1}+x^{q-2}+\cdots+x+1$.
Find the sum of all primes $p$ such that $3 \le p \le 100$ and there exists an odd prime $q$ and a positive integer $N$ satisfying
\[\dbinom{N}{\Phi_q(p)}\equiv \dbinom{2\Phi_q(p)}{N} \not \equiv 0 \pmod p. \][i]Proposed by Sammy Luo[/i]
1957 AMC 12/AHSME, 32
The largest of the following integers which divides each of the numbers of the sequence $ 1^5 \minus{} 1,\, 2^5 \minus{} 2,\, 3^5 \minus{} 3,\, \cdots, n^5 \minus{} n, \cdots$ is:
$ \textbf{(A)}\ 1 \qquad \textbf{(B)}\ 60 \qquad \textbf{(C)}\ 15 \qquad \textbf{(D)}\ 120\qquad \textbf{(E)}\ 30$
2016 Iran Team Selection Test, 2
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.
2014 Contests, 1
Numbers $1$ through $2014$ are written on a board. A valid operation is to erase two numbers $a$ and $b$ on the board and replace them with the greatest common divisor and the least common multiple of $a$ and $b$.
Prove that, no matter how many operations are made, the sum of all the numbers that remain on the board is always larger than $2014$ $\times$ $\sqrt[2014]{2014!}$
2020 Polish Junior MO Second Round, 5.
Let $a$, $b$ be such integers that $gcd(a + n,b + n) > 1$ for every integer $n \geq 1$. Prove that $a = b$.
1974 IMO Shortlist, 7
Let $a_i, b_i$ be coprime positive integers for $i = 1, 2, \ldots , k$, and $m$ the least common multiple of $b_1, \ldots , b_k$. Prove that the greatest common divisor of $a_1 \frac{m}{b_1} , \ldots, a_k \frac{m}{b_k}$ equals the greatest common divisor of $a_1, \ldots , a_k.$
PEN L Problems, 2
The Fibonacci sequence $\{F_{n}\}$ is defined by \[F_{1}=1, \; F_{2}=1, \; F_{n+2}=F_{n+1}+F_{n}.\] Show that $\gcd (F_{m}, F_{n})=F_{\gcd (m, n)}$ for all $m, n \in \mathbb{N}$.
2008 Saint Petersburg Mathematical Olympiad, 6
$a+b+c \leq 3000000$ and $a\neq b \neq c \neq a$ and $a,b,c$ are naturals.
Find maximum $GCD(ab+1,ac+1,bc+1)$
2023 AMC 12/AHSME, 24
Integers $a, b, c, d$ satisfy the following:
$abcd=2^6\cdot 3^9\cdot 5^7$
$\text{lcm}(a,b)=2^3\cdot 3^2\cdot 5^3$
$\text{lcm}(a,c)=2^3\cdot 3^3\cdot 5^3$
$\text{lcm}(a,d)=2^3\cdot 3^3\cdot 5^3$
$\text{lcm}(b,c)=2^1\cdot 3^3\cdot 5^2$
$\text{lcm}(b,d)=2^2\cdot 3^3\cdot 5^2$
$\text{lcm}(c,d)=2^2\cdot 3^3\cdot 5^2$
Find $\text{gcd}(a,b,c,d)$
$\textbf{(A)}~30\qquad\textbf{(B)}~45\qquad\textbf{(C)}~3\qquad\textbf{(D)}~15\qquad\textbf{(E)}~6$
2014 ELMO Shortlist, 8
Let $\mathbb N$ denote the set of positive integers. Find all functions $f: \mathbb{N} \to \mathbb{N}$ such that:
(i) The greatest common divisor of the sequence $f(1), f(2), \dots$ is $1$.
(ii) For all sufficiently large integers $n$, we have $f(n) \neq 1$ and \[ f(a)^n \mid f(a+b)^{a^{n-1}} - f(b)^{a^{n-1}} \] for all positive integers $a$ and $b$.
[i]Proposed by Yang Liu[/i]