Olympiad problems

2024 Philippine Math Olympiad, P4

Let $n$ be a positive integer. Suppose for any $\mathcal{S} \subseteq \{1, 2, \cdots, n\}$, $f(\mathcal{S})$ is the set containing all positive integers at most $n$ that have an odd number of factors in $\mathcal{S}$. How many subsets of $\{1, 2, \cdots, n\}$ can be turned into $\{1\}$ after finitely many (possibly zero) applications of $f$?

2006 Austria Beginners' Competition, 1

Tags: number theory , divisible

Do integers $a, b$ exist such that $a^{2006} + b^{2006} + 1$ is divisible by $2006^2$?

2010 Contests, 1

Tags: algorithm , euclidean algorithm , number theory

Let $a,b$ be two positive integers and $a>b$.We know that $\gcd(a-b,ab+1)=1$ and $\gcd(a+b,ab-1)=1$. Prove that $(a-b)^2+(ab+1)^2$ is not a perfect square.

1999 Croatia National Olympiad, Problem 4

Tags: number theory

A triple of numbers $(a_1,a_2,a_3)=(3,4,12)$ is given. The following operation is performed a finite number of times: choose two numbers $a,b$ from the triple and replace them by $0.6x-0.8y$ and $0.8x+0.6y$. Is it possible to obtain the (unordered) triple $(2,8,10)$?

2018 Saudi Arabia JBMO TST, 4

Tags: number theory

Let $n=>2$ be a natural number. A set $S$ of natural numbers is called $complete$ if, for any integer $0<=x<n$, there is a subset of $S$ with the property that the remainder of the division by $n$ of the sum of the elements in the subset is $x$. The sum of the elements of the empty set is considered to be $0$. Show that if a set $S$ is $complete$, then there is a subset of $S$ which has at most $n-1$ elements and which is still $complete$.

2018 Costa Rica - Final Round, N4

Tags: prime , number theory

Let $p$ be a prime number such that $p = 10^{d -1} + 10^{d-2} + ...+ 10 + 1$. Show that $d$ is a prime.

2019 South East Mathematical Olympiad, 3

Tags: function , number theory

Let $f:\mathbb{N}\rightarrow \mathbb{N}$ be a function such that $f(ab)$ divides $\max \{f(a),b\}$ for any positive integers $a,b$. Must there exist infinitely many positive integers $k$ such that $f(k)=1$?

2019 Iran MO (3rd Round), 2

Tags: number theory

Call a polynomial $P(x)=a_nx^n+a_{n-1}x^{n-1}+\dots a_1x+a_0$ with integer coefficients primitive if and only if $\gcd(a_n,a_{n-1},\dots a_1,a_0) =1$. a)Let $P(x)$ be a primitive polynomial with degree less than $1398$ and $S$ be a set of primes greater than $1398$.Prove that there is a positive integer $n$ so that $P(n)$ is not divisible by any prime in $S$. b)Prove that there exist a primitive polynomial $P(x)$ with degree less than $1398$ so that for any set $S$ of primes less than $1398$ the polynomial $P(x)$ is always divisible by product of elements of $S$.

2002 Germany Team Selection Test, 3

Tags: number theory

Determine all $(x,y) \in \mathbb{N}^2$ which satisfy $x^{2y} + (x+1)^{2y} = (x+2)^{2y}.$

2013 Saudi Arabia IMO TST, 3

Tags: digit , divisor , number theory

For a positive integer $n$, we consider all its divisors (including $1$ and itself). Suppose that $p\%$ of these divisors have their unit digit equal to $3$. (For example $n = 117$, has six divisors, namely $1,3,9,13,39,117$. Two of these divisors namely $3$ and $13$, have unit digits equal to $3$. Hence for $n = 117$, $p =33.33...$). Find, when $n$ is any positive integer, the maximum possible value of $p$.

2017 Taiwan TST Round 2, 3

Tags: number theory , function , divisibility

Denote by $\mathbb{N}$ the set of all positive integers. Find all functions $f:\mathbb{N}\rightarrow \mathbb{N}$ such that for all positive integers $m$ and $n$, the integer $f(m)+f(n)-mn$ is nonzero and divides $mf(m)+nf(n)$. [i]Proposed by Dorlir Ahmeti, Albania[/i]

2019 HMNT, 6

Tags: number theory

Find all ordered pairs $(a,b)$ of positive integers such that $2a + 1$ divides $3b - 1$ and $2b + 1$ divides $3a -1$.

2018 Purple Comet Problems, 23

Tags: number theory

Let $a, b$, and $c$ be integers simultaneously satisfying the equations $4abc + a + b + c = 2018$ and $ab + bc + ca = -507$. Find $|a| + |b|+ |c|$.

1998 IMO Shortlist, 2

Tags: floor function , number theory , algebraic identities , algebra

Determine all pairs $(a,b)$ of real numbers such that $a \lfloor bn \rfloor =b \lfloor an \rfloor $ for all positive integers $n$. (Note that $\lfloor x\rfloor $ denotes the greatest integer less than or equal to $x$.)

2017 Romania Team Selection Test, P1

Tags: number theory

Let m be a positive interger, let $p$ be a prime, let $a_1=8p^m$, and let $a_n=(n+1)^{\frac{a_{n-1}}{n}}$, $n=2,3...$. Determine the primes $p$ for which the products $a_n(1-\frac{1}{a_1})(1-\frac{1}{a_2})...(1-\frac{1}{a_n})$, $n=1,2,3...$ are all integral.

2001 IMO Shortlist, 5

Tags: composite number , number theory

Let $a > b > c > d$ be positive integers and suppose that \[ ac + bd = (b+d+a-c)(b+d-a+c). \] Prove that $ab + cd$ is not prime.

2010 Dutch IMO TST, 3

Tags: number theory , perfect square

Let $n\ge 2$ be a positive integer and $p $ a prime such that $n|p-1$ and $p | n^3-1$. Show $ 4p-3$ is a square.

2022 Tuymaada Olympiad, 3

Tags: number theory , combinatorics

Is there a colouring of all positive integers in three colours so that for each positive integer the numbers of its divisors of any two colours differ at most by $2?$

1991 French Mathematical Olympiad, Problem 1

Tags: number theory

(a) Suppose that $x_n~(n\ge0)$ is a sequence of real numbers with the property that $x_0^3+x_1^3+\ldots+x_n^3=(x_0+x_1+\ldots+x_n)^2$ for each $n\in\mathbb N$. Prove that for each $n\in\mathbb N_0$ there exists $m\in\mathbb N_0$ such that $x_0+x_1+\ldots+x_n=\frac{m(m+1)}2$. (b) For natural numbers $n$ and $p$, we define $S_{n,p}=1^p+2^p+\ldots+n^p$. Find all natural numbers $p$ such that $S_{n,p}$ is a perfect square for each $n\in\mathbb N$.

2015 Saint Petersburg Mathematical Olympiad, 3

Tags: combinatorics , number theory

There are weights with mass $1,3,5,....,2i+1,...$ Let $A(n)$ -is number of different sets with total mass equal $n$( For example $A(9)=2$, because we have two sets $9=9=1+3+5$). Prove that $A(n) \leq A(n+1)$ for $n>1$

2003 IMO Shortlist, 8

Tags: modular arithmetic , number theory , prime number , perfect power

Let $p$ be a prime number and let $A$ be a set of positive integers that satisfies the following conditions: (i) the set of prime divisors of the elements in $A$ consists of $p-1$ elements; (ii) for any nonempty subset of $A$, the product of its elements is not a perfect $p$-th power. What is the largest possible number of elements in $A$ ?

2024 Stars of Mathematics, P2

Tags: number theory

A positive integer is called [i]cool[/i] if it is divisible by the square of each of its prime divisors. Prove that $n$ and $n+1$ are simultaneously cool for infinitely many $n$.

KoMaL A Problems 2022/2023, A. 841

Tags: number theory , diophantine equation

Find all non-negative integer solutions of the equation $2^a+p^b=n^{p-1}$, where $p$ is a prime number. Proposed by [i]Máté Weisz[/i], Cambridge

1985 AIME Problems, 13

Tags: number theory , greatest common divisor , algorithm , algebra , polynomial , euclidean algorithm

The numbers in the sequence 101, 104, 109, 116, $\dots$ are of the form $a_n = 100 + n^2$, where $n = 1$, 2, 3, $\dots$. For each $n$, let $d_n$ be the greatest common divisor of $a_n$ and $a_{n + 1}$. Find the maximum value of $d_n$ as $n$ ranges through the positive integers.

1957 AMC 12/AHSME, 32

Tags: number theory , greatest common divisor , modular arithmetic

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$