Olympiad problems

1998 Bundeswettbewerb Mathematik, 2

Prove that there exists an infinite sequence of perfect squares with the following properties: (i) The arithmetic mean of any two consecutive terms is a perfect square, (ii) Every two consecutive terms are coprime, (iii) The sequence is strictly increasing.

2011 Regional Olympiad of Mexico Center Zone, 3

Tags: coprime , number theory

We have $n$ positive integers greater than $1$ and less than $10000$ such that neither of them is prime but any two of them are relative prime. Find the maximum value of $n $.

2017 Irish Math Olympiad, 1

Tags: coprime , divisible , number theory

Does there exist an even positive integer $n$ for which $n+1$ is divisible by $5$ and the two numbers $2^n + n$ and $2^n -1$ are co-prime?

2010 Estonia Team Selection Test, 1

Tags: prime , gcd , power of prime , coprime , number theory

For arbitrary positive integers $a, b$, denote $a @ b =\frac{a-b}{gcd(a,b)}$ Let $n$ be a positive integer. Prove that the following conditions are equivalent: (i) $gcd(n, n @ m) = 1$ for every positive integer $m < n$, (ii) $n = p^k$ where $p$ is a prime number and $k$ is a non-negative integer.

2003 All-Russian Olympiad Regional Round, 10.7

Tags: coprime , combinatorics , number theory

Prove that from an arbitrary set of three-digit numbers, including at least four numbers that are mutually prime, you can choose four numbers that are also mutually prime

2016 Saudi Arabia Pre-TST, 1.4

Tags: number theory , coprime , divide , divisible

Let $p$ be a given prime. For each prime $r$, we defind the function as following $F(r) =\frac{(p^{rp} - 1) (p - 1)}{(p^r - 1) (p^p - 1)}$. 1. Show that $F(r)$ is a positive integer for any prime $r \ne p$. 2. Show that $F(r)$ and $F(s)$ are coprime for any primes $r$ and $s$ such that $r \ne p, s \ne p$ and $r \ne s$. 3. Fix a prime $r \ne p$. Show that there is a prime divisor $q$ of $F(r)$ such that $p| q - 1$ but $p^2 \nmid q - 1$.

2004 All-Russian Olympiad Regional Round, 10.5

Tags: polynomial , coprime , integer polynomial , algebra

Equation $$x^n + a_1x^{n-1} + a_2x^{n-2} +...+ a_{n-1}x + a_n = 0$$ with integer non-zero coefficients $a_1$, $a_2$, $...$ , $a_n$ has $n$ different integer roots. Prove that if any two roots are relatively prime, then the numbers $a_{n-1}$ and $a_n$ are coprime.

2009 Bulgaria National Olympiad, 1

Tags: diophantine equation , exponential equation , coprime , number theory

The natural numbers $a$ and $b$ satisfy the inequalities $a > b > 1$ . It is also known that the equation $\frac{a^x - 1}{a - 1}=\frac{b^y - 1}{b - 1}$ has at least two solutions in natural numbers, when $x > 1$ and $y > 1$. Prove that the numbers $a$ and $b$ are coprime (their greatest common divisor is $1$).

2009 Estonia Team Selection Test, 2

Tags: number theory , mean , coprime

Call a finite set of positive integers [i]independent [/i] if its elements are pairwise coprime, and [i]nice [/i] if the arithmetic mean of the elements of every non-empty subset of it is an integer. a) Prove that for any positive integer $n$ there is an $n$-element set of positive integers which is both independent and nice. b) Is there an infinite set of positive integers whose every independent subset is nice and which has an $n$-element independent subset for every positive integer $n$?

2009 Estonia Team Selection Test, 2

Tags: mean , coprime , number theory

Call a finite set of positive integers [i]independent [/i] if its elements are pairwise coprime, and [i]nice [/i] if the arithmetic mean of the elements of every non-empty subset of it is an integer. a) Prove that for any positive integer $n$ there is an $n$-element set of positive integers which is both independent and nice. b) Is there an infinite set of positive integers whose every independent subset is nice and which has an $n$-element independent subset for every positive integer $n$?

1940 Eotvos Mathematical Competition, 2

Tags: coprime , number theory

Let $m$ and $n$ be distinct positive integers. Prove that $2^{2^m} + 1$ and $2^{2^n} + 1$ have no common divisor greater than $1$.

1992 All Soviet Union Mathematical Olympiad, 567

Tags: coprime , prime , number theory

Show that if $15$ numbers lie between $2$ and $1992$ and each pair is coprime, then at least one is prime.

2016 Bosnia and Herzegovina Team Selection Test, 4

Tags: number theory , additive number theory , coprime

Determine the largest positive integer $n$ which cannot be written as the sum of three numbers bigger than $1$ which are pairwise coprime.

2017 Singapore Junior Math Olympiad, 5

Tags: combinatorics , coprime , number theory

Let $a, b, c$ be nonzero integers, with $1$ as their only positive common divisor, such that $\frac{1}{a}+\frac{1}{b}+\frac{1}{c}= 0$. Find the number of such triples $(a, b, c)$ with $50 \ge |a| \ge |b| \ge |c| 1$.

VMEO III 2006, 11.4

Tags: coprime , lcm , number theory

Given an integer $a>1$. Let $p_1 < p_2 <...< p_k$ be all prime divisors of $a$. For each positive integer $n$ we define: $C_0(n) = a^{2n}, C_1(n) =\frac{a^{2n}}{p^2_1}, .... , C_k(n) =\frac{a^{2_n}}{p^2_k}$ $A = a^2 + 1$ $T(n) = A^{C_0(n)} - 1$ $M(n) = LCM(a^{2n+2}, A^{C_1(n)} - 1, ..., A^{C_k(n)} - 1)$ $A_n =\frac{T(n)}{M(n)}$ Prove that the sequence $A_1, A_2, ... $ satisfies the properties: (i) Every number in the sequence is an integer greater than $1$ and has only prime divisors of the form $am + 1$. (ii) Any two different numbers in the sequence are coprime.

2011 Korea Junior Math Olympiad, 6

Tags: relatively prime , number theory , euler s totient function , coprime , divisor

For a positive integer $n$, define the set $S_n$ as $S_n =\{(a, b)|a, b \in N, lcm[a, b] = n\}$ . Let $f(n)$ be the sum of $\phi (a)\phi (b)$ for all $(a, b) \in S_n$. If a prime $p$ relatively prime to $n$ is a divisor of $f(n)$, prove that there exists a prime $q|n$ such that $p|q^2 - 1$.

1963 Polish MO Finals, 1

Tags: coprime , digtis , number theory

Prove that two natural numbers whose digits are all ones are relatively prime if and only if the numbers of their digits are relatively prime.

2018 Dutch BxMO TST, 2

Tags: integer , sides of a triangle , coprime , geometry

Let $\vartriangle ABC$ be a triangle of which the side lengths are positive integers which are pairwise coprime. The tangent in $A$ to the circumcircle intersects line $BC$ in $D$. Prove that $BD$ is not an integer.

2008 Korea Junior Math Olympiad, 3

Tags: relatively prime , diophantine equation , coprime , number theory

For all positive integers $n$, prove that there are integers $x, y$ relatively prime to $5$ such that $x^2 + y^2 = 5^n$.

2016 Balkan MO Shortlist, N1

Tags: coprime , phi function , number theory

Find all natural numbers $n$ for which $1^{\phi (n)} + 2^{\phi (n)} +... + n^{\phi (n)}$ is coprime with $n$.

2015 Costa Rica - Final Round, N4

Tags: coprime , integer , number theory

Show that there are no triples $(a, b, c)$ of positive integers such that a) $a + c, b + c, a + b$ do not have common multiples in pairs. b)$\frac{c^2}{a + b},\frac{b^2}{a + c},\frac{a^2}{c + b}$ are integer numbers.

2012 Singapore Junior Math Olympiad, 5

Tags: number theory , prime number , coprime , prime

Suppose $S = \{a_1, a_2,..., a_{15}\}$ is a set of $1 5$ distinct positive integers chosen from $2 , 3, ... , 2012$ such that every two of them are coprime. Prove that $S$ contains a prime number. (Note: Two positive integers $m, n$ are coprime if their only common factor is 1)

2006 Korea Junior Math Olympiad, 5

Tags: number theory , coprime , integer , positive integer

Find all positive integers that can be written in the following way $\frac{m^2 + 20mn + n^2}{m^3 + n^3}$ Also, $m,n$ are relatively prime positive integers.

2012 Danube Mathematical Competition, 2

Tags: decimal representation , decimal , coprime , number theory

Consider the natural number prime $p, p> 5$. From the decimal number $\frac1p$, randomly remove $2012$ numbers, after the comma. Show that the remaining number can be represented as $\frac{a}{b}$ , where $a$ and $b$ are coprime numbers , and $b$ is multiple of $p$.

2017 Tuymaada Olympiad, 6

Tags: sum of divisors , coprime , number theory

Let $\sigma(n)$ denote the sum of positive divisors of a number $n$. A positive integer $N=2^r b$ is given, where $r$ and $b$ are positive integers and $b$ is odd. It is known that $\sigma(N)=2N-1$. Prove that $b$ and $\sigma(b)$ are coprime. (J. Antalan, J. Dris)