Olympiad problems

2008 China Team Selection Test, 2

The sequence $ \{x_{n}\}$ is defined by $ x_{1} \equal{} 2,x_{2} \equal{} 12$, and $ x_{n \plus{} 2} \equal{} 6x_{n \plus{} 1} \minus{} x_{n}$, $ (n \equal{} 1,2,\ldots)$. Let $ p$ be an odd prime number, let $ q$ be a prime divisor of $ x_{p}$. Prove that if $ q\neq2,3,$ then $ q\geq 2p \minus{} 1$.

2008 Romanian Master of Mathematics, 3

Let $ a>1$ be a positive integer. Prove that every non-zero positive integer $ N$ has a multiple in the sequence $ (a_n)_{n\ge1}$, $ a_n\equal{}\left\lfloor\frac{a^n}n\right\rfloor$.

function modular arithmetic number theory floor function Fermat's little theorem floor and ceiling functions p-adic valuation sequences

2001 Romania Team Selection Test, 1

Find all pairs $\left(m,n\right)$ of positive integers, with $m,n\geq2$, such that $a^n-1$ is divisible by $m$ for each $a\in \left\{1,2,3,\ldots,n\right\}$.

modular arithmetic polynomial congruence number theory Fermat's little theorem

2018 AMC 10, 16

Let $a_1,a_2,\dots,a_{2018}$ be a strictly increasing sequence of positive integers such that $$a_1+a_2+\cdots+a_{2018}=2018^{2018}.$$ What is the remainder when $a_1^3+a_2^3+\cdots+a_{2018}^3$ is divided by $6$? $\textbf{(A)}\ 0\qquad\textbf{(B)}\ 1\qquad\textbf{(C)}\ 2\qquad\textbf{(D)}\ 3\qquad\textbf{(E)}\ 4$

sum of cubes algebra Chinese remainder theorem Fermat's little theorem modular arithmetic number theory parity sequences

2012 Tuymaada Olympiad, 4

Let $p=4k+3$ be a prime. Prove that if \[\dfrac {1} {0^2+1}+\dfrac{1}{1^2+1}+\cdots+\dfrac{1}{(p-1)^2+1}=\dfrac{m} {n}\] (where the fraction $\dfrac {m} {n}$ is in reduced terms), then $p \mid 2m-n$. [i]Proposed by A. Golovanov[/i]

calculus modular arithmetic polynomial quadratic algebra Fermat's little theorem polynomials quadratic equations quadratic residues

2010 Contests, 1

Find all primes $p,q$ such that $p^3-q^7=p-q$.

number theory Fermat's little theorem

2014 Purple Comet Problems, 24

Let $S=2^3+3^4+5^4+7^4+\cdots+17497^4$ be the sum of the fourth powers of the first $2014$ prime numbers. Find the remainder when $S$ is divided by $240$.

modular arithmetic Chinese remainder theorem Fermat's little theorem number theory

2024-IMOC, N3

Find all positive integers $n$ such that $$n(2^n-1)$$ is a perfect square

number theory Fermat's little theorem construction mathematical induction modular arithmetic quadratic residues

2002 China Team Selection Test, 2

Does there exist $ 2002$ distinct positive integers $ k_1, k_2, \cdots k_{2002}$ such that for any positive integer $ n \geq 2001$, one of $ k_12^n \plus{} 1, k_22^n \plus{} 1, \cdots, k_{2002}2^n \plus{} 1$ is prime?

number theory Fermat's little theorem mathematical induction modular arithmetic

2005 Germany Team Selection Test, 1

Let $k$ be a fixed integer greater than 1, and let ${m=4k^2-5}$. Show that there exist positive integers $a$ and $b$ such that the sequence $(x_n)$ defined by \[x_0=a,\quad x_1=b,\quad x_{n+2}=x_{n+1}+x_n\quad\text{for}\quad n=0,1,2,\dots,\] has all of its terms relatively prime to $m$. [i]Proposed by Jaroslaw Wroblewski, Poland[/i]

relatively prime sequence quadratic number theory Chinese remainder theorem Euclidean algorithm Fermat's little theorem factorization mathematical induction modular arithmetic pigeonhole principle prime factorization quadratic equations quadratic residues recurrence relations sequences

2009 Middle European Mathematical Olympiad, 4

Determine all integers $ k\ge 2$ such that for all pairs $ (m$, $ n)$ of different positive integers not greater than $ k$, the number $ n^{n\minus{}1}\minus{}m^{m\minus{}1}$ is not divisible by $ k$.

modular arithmetic quadratic number theory Chinese remainder theorem Fermat's little theorem quadratic equations quadratic residues

1997 IMO Shortlist, 15

An infinite arithmetic progression whose terms are positive integers contains the square of an integer and the cube of an integer. Show that it contains the sixth power of an integer.

arithmetic sequence modular arithmetic perfect cube number theory perfect square Fermat's little theorem factorization mathematical induction perfect powers perfect squares prime factorization quadratic residues sequences

2014 Romania Team Selection Test, 4

Let $k$ be a nonzero natural number and $m$ an odd natural number . Prove that there exist a natural number $n$ such that the number $m^n+n^m$ has at least $k$ distinct prime factors.

induction modular arithmetic prime factorization relatively prime number theory Chinese remainder theorem Fermat's little theorem factorization mathematical induction

2019 Slovenia Team Selection Test, 4

Let $P$ be the set of all prime numbers. Let $A$ be some subset of $P$ that has at least two elements. Let's say that for every positive integer $n$ the following statement holds: If we take $n$ different elements $p_1,p_2...p_n \in A$, every prime number that divides $p_1 p_2 \cdots p_n-1$ is also an element of $A$. Prove, that $A$ contains all prime numbers.

number theory Fermat's little theorem combinatorics modular arithmetic

2012 ELMO Shortlist, 1

Find all positive integers $n$ such that $4^n+6^n+9^n$ is a square. [i]David Yang, Alex Zhu.[/i]

modular arithmetic algorithm quadratic number theory Fermat's little theorem mathematical induction quadratic equations quadratic residues

Russian TST 2018, P4

Let $k$ be a given even positive integer. Sarah first picks a positive integer $N$ greater than $1$ and proceeds to alter it as follows: every minute, she chooses a prime divisor $p$ of the current value of $N$, and multiplies the current $N$ by $p^k -p^{-1}$ to produce the next value of $N$. Prove that there are infinitely many even positive integers $k$ such that, no matter what choices Sarah makes, her number $N$ will at some point be divisible by $2018$.

number theory Fermat's little theorem factorization modular arithmetic prime factorization