Olympiad problems

2019 Irish Math Olympiad, 1

Tags: number theory

Define the [i]quasi-primes[/i] as follows. $\bullet$ The first quasi-prime is $q_1 = 2$ $\bullet$ For $n \ge 2$, the $n^{th}$ quasi-prime $q_n$ is the smallest integer greater than $q_{n_1}$ and not of the form $q_iq_j$ for some $1 \le i \le j \le n - 1$. Determine, with proof, whether or not $1000$ is a quasi-prime.

2012 Belarus Team Selection Test, 1

Tags: algebra , pigeonhole principle , polynomial , combinatorics , number theory

Consider a polynomial $P(x) = \prod^9_{j=1}(x+d_j),$ where $d_1, d_2, \ldots d_9$ are nine distinct integers. Prove that there exists an integer $N,$ such that for all integers $x \geq N$ the number $P(x)$ is divisible by a prime number greater than 20. [i]Proposed by Luxembourg[/i]

2024 All-Russian Olympiad, 8

Tags: number theory

Prove that there exists $c>0$ such that for any odd prime $p=2k+1$, the numbers $1^0, 2^1,3^2,\dots,k^{k-1}$ give at least $c\sqrt{p}$ distinct residues modulo $p$. [i]Proposed by M. Turevsky, I. Bogdanov[/i]

2020 SMO, 6

Tags: number theory , algebra

We say that a number is [i]angelic[/i] if it is greater than $10^{100}$ and all of its digits are elements of $\{1,3,5,7,8\}$. Suppose $P$ is a polynomial with nonnegative integer coefficients such that over all positive integers $n$, if $n$ is angelic, then the decimal representation of $P(s(n))$ contains the decimal representation of $s(P(n))$ as a contiguous substring, where $s(n)$ denotes the sum of digits of $n$. Prove that $P$ is linear and its leading coefficient is $1$ or a power of $10$. [i]Proposed by Grant Yu[/i]

2005 Bulgaria National Olympiad, 1

Tags: number theory

Determine all triples $\left( x,y,z\right)$ of positive integers for which the number \[ \sqrt{\frac{2005}{x+y}}+\sqrt{\frac{2005}{y+z}}+\sqrt{\frac{2005}{z+x}} \] is an integer .

2014 Contests, 2

Tags: induction , algebra , modular arithmetic , number theory

Let $n \ge 2$ be an integer. Show that there exist $n+1$ numbers $x_1, x_2, \ldots, x_{n+1} \in \mathbb{Q} \setminus \mathbb{Z}$, so that $\{ x_1^3 \} + \{ x_2^3 \} + \cdots + \{ x_n^3 \}=\{ x_{n+1}^3 \}$, where $\{ x \}$ is the fractionary part of $x$.

2014 Postal Coaching, 2

Tags: function , number theory

Let $d(n)$ be the number of positive divisors of a natural number $n$.Find all $k\in \mathbb{N}$ such that there exists $n\in \mathbb{N}$ with $d(n^2)/d(n)=k$.

2021 Korea National Olympiad, P3

Tags: number theory

Show that for any positive integers $k$ and $1 \leq a \leq 9$, there exists $n$ such that satisfies the below statement. When $2^n=a_0+10a_1+10^2a_2+ \cdots +10^ia_i+ \cdots $ $(0 \leq a_i \leq 9$ and $a_i$ is integer), $a_k$ is equal to $a$.

2014 Contests, 4

Tags: prime number , modular arithmetic , number theory

The sum of two prime numbers is $85$. What is the product of these two prime numbers? $\textbf{(A) }85\qquad\textbf{(B) }91\qquad\textbf{(C) }115\qquad\textbf{(D) }133\qquad \textbf{(E) }166$

2004 India Regional Mathematical Olympiad, 3

Tags: relatively prime , quadratic , number theory with sequences , induction , greatest common divisor , number theory

Let $\alpha$ and $\beta$ be the roots of the equation $x^2 + mx -1 = 0$ where $m$ is an odd integer. Let $\lambda _n = \alpha ^n + \beta ^n , n \geq 0$ Prove that (A) $\lambda _n$ is an integer (B) gcd ( $\lambda _n , \lambda_{n+1}$) = 1 .

1978 Miklós Schweitzer, 3

Tags: logarithm , number theory , combinatorics

Let $ 1<a_1<a_2< \ldots <a_n<x$ be positive integers such that $ \sum_{i\equal{}1}^n 1/a_i \leq 1$. Let $ y$ denote the number of positive integers smaller that $ x$ not divisible by any of the $ a_i$. Prove that \[ y > \frac{cx}{\log x}\] with a suitable positive constant $ c$ (independent of $ x$ and the numbers $ a_i$). [i]I. Z. Ruzsa[/i]

2010 Indonesia TST, 4

Tags: greatest common divisor , number theory , inequalities

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]

2007 Pre-Preparation Course Examination, 16

Tags: induction , number theory

Prove that $2^{2^{n}}+2^{2^{{n-1}}}+1$ has at least $n$ distinct prime divisors.

2020 China Second Round Olympiad, 3

Tags: recurrence relation , linear recurrence , number theory

Let $a_1=1,$ $a_2=2,$ $a_n=2a_{n-1}+a_{n-2},$ $n=3,4,\cdots.$ Prove that for any integer $n\geq5,$ $a_n$ has at least one prime factor $p,$ such that $p\equiv 1\pmod{4}.$

2000 Romania Team Selection Test, 1

Tags: modular arithmetic , number theory

Let $a>1$ be an odd positive integer. Find the least positive integer $n$ such that $2^{2000}$ is a divisor of $a^n-1$. [i]Mircea Becheanu [/i]

2003 Bulgaria National Olympiad, 2

Tags: inequalities , number theory

Let $a,b,c$ be rational numbers such that $a+b+c$ and $a^2+b^2+c^2$ are [b]equal[/b] integers. Prove that the number $abc$ can be written as the ratio of a perfect cube and a perfect square which are relatively prime.

2022 Thailand Online MO, 7

Tags: number theory

Let $p$ be a prime number, and let $a_1, a_2, \dots , a_p$ and $b_1, b_2, \dots , b_p$ be $2p$ (not necessarily distinct) integers chosen from the set $\{1, 2, \dots , p - 1\}$. Prove that there exist integers $i$ and $j$ such that $1 \le i < j \le p$ and $p$ divides $a_ib_j-a_jb_i$.

1989 IMO Longlists, 88

Tags: number theory

Prove that the sequence $ (a_n)_{n \geq 0,}, a_n \equal{} [n \cdot \sqrt{2}],$ contains an infinite number of perfect squares.

2018 Harvard-MIT Mathematics Tournament, 7

Tags: number theory

Anders is solving a math problem, and he encounters the expression $\sqrt{15!}$. He attempts to simplify this radical as $a\sqrt{b}$ where $a$ and $b$ are positive integers. The sum of all possible values of $ab$ can be expressed in the form $q\cdot 15!$ for some rational number $q$. Find $q$.

Russian TST 2018, P3

Tags: number theory

Find all pairs $(p,q)$ of prime numbers which $p>q$ and $$\frac{(p+q)^{p+q}(p-q)^{p-q}-1}{(p+q)^{p-q}(p-q)^{p+q}-1}$$ is an integer.

2021 Auckland Mathematical Olympiad, 5

Tags: combinatorics , number theory

There are $13$ stones each of which weighs an integer number of grams. It is known that any $12$ of them can be put on two pans of a balance scale, six on each pan, so that they are in equilibrium (i.e., each pan will carry an equal total weight). Prove that either all stones weigh an even number of grams or all stones weigh an odd number of grams.

1990 IMO Longlists, 57

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

The sequence $\{u_n\}$ is defined by $u_1 = 1, u_2 = 1, u_n = u_{n-1} + 2u_{n-2} for n \geq 3$. Prove that for any positive integers $n, p \ (p > 1), u_{n+p} = u_{n+1}u_{p} + 2u_nu_{p-1}$. Also find the greatest common divisor of $u_n$ and $u_{n+3}.$

2021 Israel TST, 1

Tags: sum of digits , number theory

A pair of positive integers $(a,b)$ is called an [b]average couple[/b] if there exist positive integers $k$ and $c_1, \dots, c_k$ for which \[\frac{c_1+c_2+\cdots+c_k}{k}=a\qquad \text{and} \qquad \frac{s(c_1)+s(c_2)+\cdots+s(c_k)}{k}=b\] where $s(n)$ denotes the sum of digits of $n$ in decimal representation. Find the number of average couples $(a,b)$ for which $a,b<10^{10}$.

1989 China Team Selection Test, 2

Tags: number theory

Let $v_0 = 0, v_1 = 1$ and $v_{n+1} = 8 \cdot v_n - v_{n-1},$ $n = 1,2, ...$. Prove that in the sequence $\{v_n\}$ there aren't terms of the form $3^{\alpha} \cdot 5^{\beta}$ with $\alpha, \beta \in \mathbb{N}.$

2022 BMT, 3

Tags: number theory

Katie and Allie are playing a game. Katie rolls two fair six-sided dice and Allie flips two fair two-sided coins. Katie’s score is equal to the sum of the numbers on the top of the dice. Allie’s score is the product of the values of two coins, where heads is worth $4$ and tails is worth $2.$ What is the probability Katie’s score is strictly greater than Allie’s?