Olympiad problems

2021 Balkan MO Shortlist, C2

Let $K$ and $N > K$ be fixed positive integers. Let $n$ be a positive integer and let $a_1, a_2, ..., a_n$ be distinct integers. Suppose that whenever $m_1, m_2, ..., m_n$ are integers, not all equal to $0$, such that $\mid{m_i}\mid \le K$ for each $i$, then the sum $$\sum_{i = 1}^{n} m_ia_i$$ is not divisible by $N$. What is the largest possible value of $n$? [i]Proposed by Ilija Jovcevski, North Macedonia[/i]

2017 Taiwan TST Round 2, 3

Tags: function , divisibility , number theory

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]

1991 IMO Shortlist, 13

Tags: divisibility , sequence , algebra

Given any integer $ n \geq 2,$ assume that the integers $ a_1, a_2, \ldots, a_n$ are not divisible by $ n$ and, moreover, that $ n$ does not divide $ \sum^n_{i\equal{}1} a_i.$ Prove that there exist at least $ n$ different sequences $ (e_1, e_2, \ldots, e_n)$ consisting of zeros or ones such $ \sum^n_{i\equal{}1} e_i \cdot a_i$ is divisible by $ n.$

2020 China Northern MO, BP3

Tags: number theory , divisibility , existence

Are there infinitely many positive integers $n$ such that $19|1+2^n+3^n+4^n$? Justify your claim.

1997 Romania Team Selection Test, 2

Tags: number theory , divisibility , multiplicative nt , multiplicative order , modular arithmetic

Suppose that $A$ be the set of all positive integer that can write in form $a^2+2b^2$ (where $a,b\in\mathbb {Z}$ and $b$ is not equal to $0$). Show that if $p$ be a prime number and $p^2\in A$ then $p\in A$. [i]Marcel Tena[/i]

1998 IMO Shortlist, 5

Tags: divisibility , number theory , modular arithmetic

Determine all positive integers $n$ for which there exists an integer $m$ such that ${2^{n}-1}$ is a divisor of ${m^{2}+9}$.

1974 IMO Shortlist, 6

Tags: summation , divisibility , binomial coefficient , number theory , modular arithmetic

Prove that for any n natural, the number \[ \sum \limits_{k=0}^{n} \binom{2n+1}{2k+1} 2^{3k} \] cannot be divided by $5$.

1969 IMO Shortlist, 13

Tags: number theory , modular arithmetic , divisibility , additive number theory

$(CZS 2)$ Let $p$ be a prime odd number. Is it possible to find $p-1$ natural numbers $n + 1, n + 2, . . . , n + p -1$ such that the sum of the squares of these numbers is divisible by the sum of these numbers?

1977 IMO Shortlist, 3

Tags: additive number theory , remainder , divisibility , number theory

Let $a,b$ be two natural numbers. When we divide $a^2+b^2$ by $a+b$, we the the remainder $r$ and the quotient $q.$ Determine all pairs $(a, b)$ for which $q^2 + r = 1977.$

2022 Switzerland Team Selection Test, 1

Tags: number theory , divisibility , number base

Let $n$ be a positive integer. Prove that there exists a finite sequence $S$ consisting of only zeros and ones, satisfying the following property: for any positive integer $d \geq 2$, when $S$ is interpreted in base $d$, the resulting number is non-zero and divisible by $n$. [i]Remark: The sequence $S=s_ks_{k-1} \cdots s_1s_0$ interpreted in base $d$ is the number $\sum_{i=0}^{k}s_id^i$[/i]

2007 Bulgarian Autumn Math Competition, Problem 9.4

Tags: divisibility , number theory

Find the smallest natural number, which divides $2^{n}+15$ for some natural number $n$ and can be expressed in the form $3x^2-4xy+3y^2$ for some integers $x$ and $y$.

1998 Iran MO (3rd Round), 1

Tags: divisibility , modular arithmetic , number theory

Determine all positive integers $n$ for which there exists an integer $m$ such that ${2^{n}-1}$ is a divisor of ${m^{2}+9}$.

1988 IMO, 3

Tags: number theory , divisibility , diophantine equation , perfect square , vieta jumping

Let $ a$ and $ b$ be two positive integers such that $ a \cdot b \plus{} 1$ divides $ a^{2} \plus{} b^{2}$. Show that $ \frac {a^{2} \plus{} b^{2}}{a \cdot b \plus{} 1}$ is a perfect square.

2023 Switzerland - Final Round, 6

Tags: number theory , prime , divisibility

Find all positive integers $n>2$ such that $$ n! \mid \prod_{ p<q\le n, p,q \, \text{primes}} (p+q)$$

1990 IMO, 3

Tags: divisibility , orders and lte , number theory , modular arithmetic

Determine all integers $ n > 1$ such that \[ \frac {2^n \plus{} 1}{n^2} \] is an integer.

2015 German National Olympiad, 4

Tags: divisibility , number theory

Let $k$ be a positive integer. Define $n_k$ to be the number with decimal representation $70...01$ where there are exactly $k$ zeroes. Prove the following assertions: a) None of the numbers $n_k$ is divisible by $13$. b) Infinitely many of the numbers $n_k$ are divisible by $17$.

1993 IMO Shortlist, 4

Tags: subset , additive number theory , divisibility , induction , number theory

Show that for any finite set $S$ of distinct positive integers, we can find a set $T \supseteq S$ such that every member of $T$ divides the sum of all the members of $T$. [b]Original Statement:[/b] A finite set of (distinct) positive integers is called a [b]DS-set[/b] if each of the integers divides the sum of them all. Prove that every finite set of positive integers is a subset of some [b]DS-set[/b].

2011 N.N. Mihăileanu Individual, 1

Tags: divisibility , number theory

[b]a)[/b] Prove that $ 4040100 $ divides $ 2009\cdot 2011^{2011}+1. $ [i]Gabriel Iorgulescu[/i] [b]b)[/b] Let be three natural numbers $ x,y,z $ with the property that $ (1+\sqrt 2)^x=y^2+2z^2+2yz\sqrt 2. $ Show that $ x $ is even. [i]Marius Cavachi[/i]

2001 Mongolian Mathematical Olympiad, Problem 3

Tags: divisibility , number theory

Let $a,b$ be coprime positive integers with $a$ even and $a>b$. Show that there exist infinitely many pairs $(m,n)$ of coprime positive integers such that $m\mid a^{n-1}-b^{n-1}$ and $n\mid a^{m-1}-b^{m-1}$.

1994 Bundeswettbewerb Mathematik, 2

Tags: sequence , divisibility , number theory

Let $k$ be an integer and define a sequence $a_0 , a_1 ,a_2 ,\ldots$ by $$ a_0 =0 , \;\; a_1 =k \;\;\text{and} \;\; a_{n+2} =k^{2}a_{n+1}-a_n \; \text{for} \; n\geq 0.$$ Prove that $a_{n+1} a_n +1$ divides $a_{n+1}^{2} +a_{n}^{2}$ for all $n$.

2005 India IMO Training Camp, 2

Tags: divisibility , functional equation , function , number theory , algebra

Find all functions $ f: \mathbb{N^{*}}\to \mathbb{N^{*}}$ satisfying \[ \left(f^{2}\left(m\right)+f\left(n\right)\right) \mid \left(m^{2}+n\right)^{2}\] for any two positive integers $ m$ and $ n$. [i]Remark.[/i] The abbreviation $ \mathbb{N^{*}}$ stands for the set of all positive integers: $ \mathbb{N^{*}}=\left\{1,2,3,...\right\}$. By $ f^{2}\left(m\right)$, we mean $ \left(f\left(m\right)\right)^{2}$ (and not $ f\left(f\left(m\right)\right)$). [i]Proposed by Mohsen Jamali, Iran[/i]

1984 IMO Shortlist, 12

Tags: polynomial , algebra , divisibility , number theory , modular arithmetic

Find one pair of positive integers $a,b$ such that $ab(a+b)$ is not divisible by $7$, but $(a+b)^7-a^7-b^7$ is divisible by $7^7$.

1997 Slovenia National Olympiad, Problem 2

Tags: divisibility , number theory

Let $a$ be an integer and $p$ a prime number that divides both $5a-1$ and $a-10$. Show that $p$ also divides $a-3$.

1969 IMO Shortlist, 19

Tags: number theory , periodic sequence , divisibility , relatively prime

$(FRA 2)$ Let $n$ be an integer that is not divisible by any square greater than $1.$ Denote by $x_m$ the last digit of the number $x^m$ in the number system with base $n.$ For which integers $x$ is it possible for $x_m$ to be $0$? Prove that the sequence $x_m$ is periodic with period $t$ independent of $x.$ For which $x$ do we have $x_t = 1$. Prove that if $m$ and $x$ are relatively prime, then $0_m, 1_m, . . . , (n-1)_m$ are different numbers. Find the minimal period $t$ in terms of $n$. If n does not meet the given condition, prove that it is possible to have $x_m = 0 \neq x_1$ and that the sequence is periodic starting only from some number $k > 1.$

2019 China Team Selection Test, 4

Tags: divisibility , number theory

Call a sequence of positive integers $\{a_n\}$ good if for any distinct positive integers $m,n$, one has $$\gcd(m,n) \mid a_m^2 + a_n^2 \text{ and } \gcd(a_m,a_n) \mid m^2 + n^2.$$ Call a positive integer $a$ to be $k$-good if there exists a good sequence such that $a_k = a$. Does there exists a $k$ such that there are exactly $2019$ $k$-good positive integers?