Olympiad problems

2009 Bulgaria National Olympiad, 1

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

2014 IFYM, Sozopol, 5

Tags: polynomial , number theory , coprime

Let $f(x)$ be a polynomial with integer coefficients, for which there exist $a,b\in \mathbb{Z}$ ($a\neq b$), such that $f(a)$ and $f(b)$ are coprime. Prove that there exist infinitely many values for $x$, such that each $f(x)$ is coprime with any other.

2016 Silk Road, 3

Tags: floor function , coprime , divisibility , number theory

Given natural numbers $a,b$ and function $f: \mathbb{N} \to \mathbb{N} $ such that for any natural number $n, f\left( n+a \right)$ is divided by $f\left( {\left[ {\sqrt n } \right] + b} \right)$. Prove that for any natural $n$ exist $n$ pairwise distinct and pairwise relatively prime natural numbers ${{a}_{1}}$, ${{a}_{2}}$, $\ldots$, ${{a}_{n}}$ such that the number $f\left( {{a}_{i+1}} \right)$ is divided by $f\left( {{a}_{i}} \right)$ for each $i=1,2, \dots ,n-1$ . (Here $[x]$ is the integer part of number $x$, that is, the largest integer not exceeding $x$.)

1992 All Soviet Union Mathematical Olympiad, 567

Tags: number theory , coprime , prime

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

1963 Polish MO Finals, 1

Tags: number theory , coprime , digtis

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.

2003 All-Russian Olympiad Regional Round, 9.7

Tags: number theory , coprime , relatively prime

Prove that of any six four-digit numbers, mutual prime in total, you can always choose five numbers that are also relatively prime in total. [hide=original wording]Докажите, что из любых шести четырехзначных чисел, взаимно простых в совокупности, всегда можно выбратьпя ть чисел, также взаимно простых в совокупности.[/hide]

2016 Bosnia And Herzegovina - Regional Olympiad, 2

Tags: combinatorics , combinatorial number theory , coprime , set

Find all elements $n \in A = \{2,3,...,2016\} \subset \mathbb{N}$ such that: every number $m \in A$ smaller than $n$, and coprime with $n$, must be a prime number

2017 Tuymaada Olympiad, 6

Tags: number theory , sum of divisors , coprime

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)

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?

2004 All-Russian Olympiad Regional Round, 10.5

Tags: algebra , polynomial , coprime , integer polynomial

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.

2010 Estonia Team Selection Test, 1

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

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.

2007 Bulgarian Autumn Math Competition, Problem 10.3

Tags: number theory , coprime , sum function

For a natural number $m>1$ we'll denote with $f(m)$ the sum of all natural numbers less than $m$, which are also coprime to $m$. Find all natural numbers $n$, such that there exist natural numbers $k$ and $\ell$ which satisfy $f(n^{k})=n^{\ell}$.

1969 IMO Shortlist, 18

Tags: number theory , coprime , frobenius , additive number theory

$(FRA 1)$ Let $a$ and $b$ be two nonnegative integers. Denote by $H(a, b)$ the set of numbers $n$ of the form $n = pa + qb,$ where $p$ and $q$ are positive integers. Determine $H(a) = H(a, a)$. Prove that if $a \neq b,$ it is enough to know all the sets $H(a, b)$ for coprime numbers $a, b$ in order to know all the sets $H(a, b)$. Prove that in the case of coprime numbers $a$ and $b, H(a, b)$ contains all numbers greater than or equal to $\omega = (a - 1)(b -1)$ and also $\frac{\omega}{2}$ numbers smaller than $\omega$

2017 Singapore Junior Math Olympiad, 5

Tags: number theory , combinatorics , coprime

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

2022 Bulgaria JBMO TST, 3

Tags: number theory , coprime , divisibility , relatively prime

The integers $a$, $b$, $c$ and $d$ are such that $a$ and $b$ are relatively prime, $d\leq 2022$ and $a+b+c+d = ac + bd = 0$. Determine the largest possible value of $d$,

2015 Costa Rica - Final Round, N4

Tags: integer , number theory , coprime

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.

1988 Mexico National Olympiad, 5

Tags: number theory , coprime , greatest common divisor

If $a$ and $b$ are coprime positive integers and $n$ an integer, prove that the greatest common divisor of $a^2+b^2-nab$ and $a+b$ divides $n+2$.

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

2024 Abelkonkurransen Finale, 1a

Tags: number theory , modular arithmetic , coprime , coprime numbers

Determine all integers $n \ge 2$ such that $n \mid s_n-t_n$ where $s_n$ is the sum of all the integers in the interval $[1,n]$ that are mutually prime to $n$, and $t_n$ is the sum of the remaining integers in the same interval.

2003 All-Russian Olympiad Regional Round, 10.7

Tags: combinatorics , number theory , coprime

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

2023 Indonesia TST, N

Tags: number theory , gcd , integer sequence , infinite sequence , coprime

Given an integer $a>1$. Prove that there exists a sequence of positive integers \[ n_1, n_2, n_3, \ldots \] Such that \[ \gcd(a^{n_i+1} + a^{n_i} - 1, \ a^{n_j + 1} + a^{n_j} - 1) =1 \] For every $i \neq j$.

2006 Korea Junior Math Olympiad, 5

Tags: integer , positive integer , number theory , coprime

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.

2010 Estonia Team Selection Test, 1

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

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.

2004 All-Russian Olympiad Regional Round, 9.4

Tags: number theory , coprime

Three natural numbers are such that the product of any two of them is divided by the sum of these two numbers. Prove that these three numbers have a common divisor greater than one.

2014 Danube Mathematical Competition, 3

Tags: coprime , arithmetic progression , number theory , arithmetic sequence

Given any integer $n \ge 2$, show that there exists a set of $n$ pairwise coprime composite integers in arithmetic progression.