Olympiad problems

1993 China Team Selection Test, 1

Find all integer solutions to $2 x^4 + 1 = y^2.$

2008 Indonesia TST, 3

Tags: gcd , greatest common divisor , number theory

Let $n$ be an arbitrary positive integer. (a) For every positive integers $a$ and $b$, show that $gcd(n^a + 1, n^b + 1) \le n^{gcd(a,b)} + 1$. (b) Show that there exist infinitely many composite pairs ($a, b)$, such that each of them is not a multiply of the other number and equality holds in (a).

1988 ITAMO, 7

Tags: greatest common divisor , number theory

Given $n \ge 3$ positive integers not exceeding $100$, let $d$ be their greatest common divisor. Show that there exist three of these numbers whose greatest common divisor is also equal to $d$.

1990 USAMO, 3

Tags: modular arithmetic , greatest common divisor , relatively prime , combinatorics , number theory

Suppose that necklace $\, A \,$ has 14 beads and necklace $\, B \,$ has 19. Prove that for any odd integer $n \geq 1$, there is a way to number each of the 33 beads with an integer from the sequence \[ \{ n, n+1, n+2, \dots, n+32 \} \] so that each integer is used once, and adjacent beads correspond to relatively prime integers. (Here a ``necklace'' is viewed as a circle in which each bead is adjacent to two other beads.)

1997 Romania Team Selection Test, 4

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

Let $n\ge 2$ be an integer and let $P(X)=X^n+a_{n-1}X^{n-1}+\ldots +a_1X+1$ be a polynomial with positive integer coefficients. Suppose that $a_k=a_{n-k}$ for all $k\in 1,2,\ldots,n-1$. Prove that there exist infinitely many pairs of positive integers $x,y$ such that $x|P(y)$ and $y|P(x)$. [i]Remus Nicoara[/i]

2020 Mexico National Olympiad, 1

Tags: combinatorics , greatest common divisor , vector , number theory

A set of five different positive integers is called [i]virtual[/i] if the greatest common divisor of any three of its elements is greater than $1$, but the greatest common divisor of any four of its elements is equal to $1$. Prove that, in any virtual set, the product of its elements has at least $2020$ distinct positive divisors. [i]Proposed by Víctor Almendra[/i]

2009 Middle European Mathematical Olympiad, 10

Tags: incenter , greatest common divisor , cyclic quadrilateral , geometry , number theory

Suppose that $ ABCD$ is a cyclic quadrilateral and $ CD\equal{}DA$. Points $ E$ and $ F$ belong to the segments $ AB$ and $ BC$ respectively, and $ \angle ADC\equal{}2\angle EDF$. Segments $ DK$ and $ DM$ are height and median of triangle $ DEF$, respectively. $ L$ is the point symmetric to $ K$ with respect to $ M$. Prove that the lines $ DM$ and $ BL$ are parallel.

2012 AMC 8, 13

Tags: greatest common divisor , number theory

Jamar bought some pencils costing more than a penny each at the school bookstore and paid $\$1.43$. Sharona bought some of the same pencils and paid $\$1.87$. How many more pencils did Sharona buy than Jamar? $\textbf{(A)}\hspace{.05in}2 \qquad \textbf{(B)}\hspace{.05in}3 \qquad \textbf{(C)}\hspace{.05in}4 \qquad \textbf{(D)}\hspace{.05in}5 \qquad \textbf{(E)}\hspace{.05in}6 $

2011 Canadian Mathematical Olympiad Qualification Repechage, 8

Tags: induction , greatest common divisor , number theory

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

2010 Indonesia TST, 4

Tags: greatest common divisor , inequalities , number theory

Prove that for all integers $ m$ and $ n$, the inequality \[ \dfrac{\phi(\gcd(2^m \plus{} 1,2^n \plus{} 1))}{\gcd(\phi(2^m \plus{} 1),\phi(2^n \plus{} 1))} \ge \dfrac{2\gcd(m,n)}{2^{\gcd(m,n)}}\] holds. [i]Nanang Susyanto, Jogjakarta [/i]

2013 Gulf Math Olympiad, 4

Tags: greatest common divisor , number theory

Let $m,n$ be integers. It is known that there are integers $a,b$ such that $am+bn=1$ if, and only if, the greatest common divisor of $m,n$ is 1. [i]You are not required to prove this[/i]. Now suppose that $p,q$ are different odd primes. In each case determine if there are integers $a,b$ such that $ap+bq=1$ so that the given condition is satisfied: [list] a. $p$ divides $b$ and $q$ divides $a$; b. $p$ divides $a$ and $q$ divides $b$; c. $p$ does not divide $a$ and $q$ does not divide $b$. [/list]

2014 PUMaC Number Theory B, 8

Tags: floor function , number theory , greatest common divisor , calculus , integration , modular arithmetic

Find the number of positive integers $n \le 2014$ such that there exists integer $x$ that satisfies the condition that $\frac{x+n}{x-n}$ is an odd perfect square.

2012 Kosovo Team Selection Test, 5

Tags: greatest common divisor , number theory

Prove that the equation \[\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\] has infinitly many natural solutions

2013 Princeton University Math Competition, 6

Tags: modular arithmetic , greatest common divisor

Let $d$ be the greatest common divisor of $2^{30^{10}}-2$ and $2^{30^{45}}-2$. Find the remainder when $d$ is divided by $2013$.

2013 Korea National Olympiad, 5

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

2014 Baltic Way, 19

Tags: greatest common divisor , number theory

Let $m$ and $n$ be relatively prime positive integers. Determine all possible values of \[\gcd(2^m - 2^n, 2^{m^2+mn+n^2}- 1).\]

2010 China Team Selection Test, 2

Tags: induction , greatest common divisor , algebra , number theory

Given integer $a_1\geq 2$. For integer $n\geq 2$, define $a_n$ to be the smallest positive integer which is not coprime to $a_{n-1}$ and not equal to $a_1,a_2,\cdots, a_{n-1}$. Prove that every positive integer except 1 appears in this sequence $\{a_n\}$.

1979 IMO Longlists, 55

Tags: greatest common divisor , search , relatively prime , number theory

Let $a,b$ be coprime integers. Show that the equation $ax^2 + by^2 =z^3$ has an infinite set of solutions $(x,y,z)$ with $\{x,y,z\}\in\mathbb{Z}$ and each pair of $x,y$ mutually coprime.

2011 Saint Petersburg Mathematical Olympiad, 2

Tags: greatest common divisor , least common multiple , number theory

$a,b$ are naturals and $$a \times GCD(a,b)+b \times LCM(a,b)<2.5 ab$$. Prove that $b|a$

2006 Brazil National Olympiad, 4

Tags: greatest common divisor , number theory

A positive integer is [i]bold[/i] iff it has $8$ positive divisors that sum up to $3240$. For example, $2006$ is bold because its $8$ positive divisors, $1$, $2$, $17$, $34$, $59$, $118$, $1003$ and $2006$, sum up to $3240$. Find the smallest positive bold number.

2012 Today's Calculation Of Integral, 826

Tags: abstract algebra , greatest common divisor , group theory , relatively prime , superior algebra , number theory

Let $G$ be a hyper elementary abelian $p-$group and let $f : G \rightarrow G$ be a homomorphism. Then prove that $\ker f$ is isomorphic to $\mathrm{coker} f$.

2013 Turkey Team Selection Test, 1

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

Find all pairs of integers $(m,n)$ such that $m^6 = n^{n+1} + n -1$.

1999 Tuymaada Olympiad, 4

Tags: calculus , integration , analytic geometry , geometry , parallelogram , number theory , greatest common divisor

A right parallelepiped (i.e. a parallelepiped one of whose edges is perpendicular to a face) is given. Its vertices have integral coordinates, and no other points with integral coordinates lie on its faces or edges. Prove that the volume of this parallelepiped is a sum of three perfect squares. [i]Proposed by A. Golovanov[/i]

2007 Tuymaada Olympiad, 4

Tags: probability , limit , ratio , greatest common divisor , number theory , prime number , logarithm

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

2013 AMC 12/AHSME, 23

Tags: geometry , geometric transformation , rotation , 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 $