Olympiad problems

2012 France Team Selection Test, 3

Let $p$ be a prime number. Find all positive integers $a,b,c\ge 1$ such that: \[a^p+b^p=p^c.\]

2024 Auckland Mathematical Olympiad, 5

Tags: number theory , modular arithmetic

Prove that the number $2^9 +2^{99}$ is divisible by $100$.

2009 Ukraine National Mathematical Olympiad, 1

Tags: modular arithmetic

Find all positive integer solutions of equation $n^3 - 2 = k! .$

1990 China Team Selection Test, 3

Tags: modular arithmetic , induction , number theory

Prove that for every integer power of 2, there exists a multiple of it with all digits (in decimal expression) not zero.

2016 Middle European Mathematical Olympiad, 8

Tags: equation , modular arithmetic , number theory

For a positive integer $n$, the equation $a^2 + b^2 + c^2 + n = abc$ is given in the positive integers. Prove that: 1. There does not exist a solution $(a, b, c)$ for $n = 2017$. 2. For $n = 2016$, $a$ is divisible by $3$ for all solutions $(a, b, c)$. 3. There are infinitely many solutions $(a, b, c)$ for $n = 2016$.

2005 MOP Homework, 1

Tags: modular arithmetic , combinatorics

Let $X$ be a set with $n$ elements and $0 \le k \le n$. Let $a_{n,k}$ be the maximum number of permutations of the set $X$ such that every two of them have at least $k$ common components (where a common component of $f$ and g is an $x \in X$ such that $f(x) = g(x)$). Let $b_{n,k}$ be the maximum number of permutations of the set $X$ such that every two of them have at most $k$ common components. (a) Show that $a_{n,k} \cdot b_{n,k-1} \le n!$. (b) Let $p$ be prime, and find the exact value of $a_{p,2}$.

1999 Vietnam National Olympiad, 3

Tags: function , modular arithmetic , algebra

Let $ S \equal{} \{0,1,2,\ldots,1999\}$ and $ T \equal{} \{0,1,2,\ldots \}.$ Find all functions $ f: T \mapsto S$ such that [b](i)[/b] $ f(s) \equal{} s \quad \forall s \in S.$ [b](ii)[/b] $ f(m\plus{}n) \equal{} f(f(m)\plus{}f(n)) \quad \forall m,n \in T.$

1998 Romania Team Selection Test, 1

Tags: trapezoid , trigonometry , incenter , modular arithmetic , ratio , parallelogram , geometry

We are given an isosceles triangle $ABC$ such that $BC=a$ and $AB=BC=b$. The variable points $M\in (AC)$ and $N\in (AB)$ satisfy $a^2\cdot AM \cdot AN = b^2 \cdot BN \cdot CM$. The straight lines $BM$ and $CN$ intersect in $P$. Find the locus of the variable point $P$. [i]Dan Branzei[/i]

2009 AIME Problems, 13

Tags: induction , modular arithmetic , inequalities , pigeonhole principle , function

The terms of the sequence $ (a_i)$ defined by $ a_{n \plus{} 2} \equal{} \frac {a_n \plus{} 2009} {1 \plus{} a_{n \plus{} 1}}$ for $ n \ge 1$ are positive integers. Find the minimum possible value of $ a_1 \plus{} a_2$.

2015 AMC 10, 1

Tags: modular arithmetic , function

What is the value of $2-(-2)^{-2}$? $ \textbf{(A) } -2 \qquad\textbf{(B) } \dfrac{1}{16} \qquad\textbf{(C) } \dfrac{7}{4} \qquad\textbf{(D) } \dfrac{9}{4} \qquad\textbf{(E) } 6 $

2001 India IMO Training Camp, 2

Tags: modular arithmetic , number theory

Let $p > 3$ be a prime. For each $k\in \{1,2, \ldots , p-1\}$, define $x_k$ to be the unique integer in $\{1, \ldots, p-1\}$ such that $kx_k\equiv 1 \pmod{p}$ and set $kx_k = 1+ pn_k$. Prove that : \[\sum_{k=1}^{p-1}kn_k \equiv \frac{p-1}{2} \pmod{p}\]

2005 China Team Selection Test, 3

Tags: modular arithmetic , number theory , binomial expansion , fermat number , power of 2

$n$ is a positive integer, $F_n=2^{2^{n}}+1$. Prove that for $n \geq 3$, there exists a prime factor of $F_n$ which is larger than $2^{n+2}(n+1)$.

2010 Contests, 1

Tags: induction , modular arithmetic , combinatorics

For a finite non empty set of primes $P$, let $m(P)$ denote the largest possible number of consecutive positive integers, each of which is divisible by at least one member of $P$. (i) Show that $|P|\le m(P)$, with equality if and only if $\min(P)>|P|$. (ii) Show that $m(P)<(|P|+1)(2^{|P|}-1)$. (The number $|P|$ is the size of set $P$) [i]Dan Schwarz, Romania[/i]

1995 AIME Problems, 2

Tags: quadratic , modular arithmetic , algebra , polynomial , vieta , search , logarithm

Find the last three digits of the product of the positive roots of \[ \sqrt{1995}x^{\log_{1995}x}=x^2. \]

2010 Germany Team Selection Test, 3

Tags: modular arithmetic , number theory , sequence , divisibility

Find all positive integers $n$ such that there exists a sequence of positive integers $a_1$, $a_2$,$\ldots$, $a_n$ satisfying: \[a_{k+1}=\frac{a_k^2+1}{a_{k-1}+1}-1\] for every $k$ with $2\leq k\leq n-1$. [i]Proposed by North Korea[/i]

2016 Iran MO (3rd Round), 1

Tags: number theory , prime number , modular arithmetic

Let $p,q$ be prime numbers ($q$ is odd). Prove that there exists an integer $x$ such that: $$q |(x+1)^p-x^p$$ If and only if $$q \equiv 1 \pmod p$$

2014 ELMO Shortlist, 11

Tags: algebra , polynomial , modular arithmetic , number theory

Let $p$ be a prime satisfying $p^2\mid 2^{p-1}-1$, and let $n$ be a positive integer. Define \[ f(x) = \frac{(x-1)^{p^n}-(x^{p^n}-1)}{p(x-1)}. \] Find the largest positive integer $N$ such that there exist polynomials $g(x)$, $h(x)$ with integer coefficients and an integer $r$ satisfying $f(x) = (x-r)^N g(x) + p \cdot h(x)$. [i]Proposed by Victor Wang[/i]

1999 IMO Shortlist, 4

Tags: modular arithmetic , combinatorics , counting , additive combinatorics , additive number theory

Let $A$ be a set of $N$ residues $\pmod{N^{2}}$. Prove that there exists a set $B$ of of $N$ residues $\pmod{N^{2}}$ such that $A + B = \{a+b|a \in A, b \in B\}$ contains at least half of all the residues $\pmod{N^{2}}$.

2010 Turkey MO (2nd round), 2

Tags: algebra , polynomial , modular arithmetic , number theory

For integers $a$ and $b$ with $0 \leq a,b < {2010}^{18}$ let $S$ be the set of all polynomials in the form of $P(x)=ax^2+bx.$ For a polynomial $P$ in $S,$ if for all integers n with $0 \leq n <{2010}^{18}$ there exists a polynomial $Q$ in $S$ satisfying $Q(P(n)) \equiv n \pmod {2010^{18}},$ then we call $P$ as a [i]good polynomial.[/i] Find the number of [i]good polynomials.[/i]

2012 USAMO, 4

Tags: function , induction , factorial , modular arithmetic , algebra , number theory

Find all functions $f:\mathbb{Z}^+ \rightarrow \mathbb{Z}^+$ (where $\mathbb{Z}^+$ is the set of positive integers) such that $f(n!) = f(n)!$ for all positive integers $n$ and such that $m-n$ divides $f(m) - f(n)$ for all distinct positive integers $m, n$.

2014 ELMO Shortlist, 2

Tags: modular arithmetic , number theory

Define the Fibanocci sequence recursively by $F_1=1$, $F_2=1$ and $F_{i+2} = F_i + F_{i+1}$ for all $i$. Prove that for all integers $b,c>1$, there exists an integer $n$ such that the sum of the digits of $F_n$ when written in base $b$ is greater than $c$. [i]Proposed by Ryan Alweiss[/i]

2018 China Team Selection Test, 4

Tags: modular arithmetic , arithmetic sequence , number theory , primitive root , sum of powers

Let $p$ be a prime and $k$ be a positive integer. Set $S$ contains all positive integers $a$ satisfying $1\le a \le p-1$, and there exists positive integer $x$ such that $x^k\equiv a \pmod p$. Suppose that $3\le |S| \le p-2$. Prove that the elements of $S$, when arranged in increasing order, does not form an arithmetic progression.

2013 China Team Selection Test, 1

Tags: modular arithmetic , geometric transformation , real analysis , number theory , geometry

Let $p$ be a prime number and $a, k$ be positive integers such that $p^a<k<2p^a$. Prove that there exists a positive integer $n$ such that \[n<p^{2a}, C_n^k\equiv n\equiv k\pmod {p^a}.\]

2014 Kazakhstan National Olympiad, 2

Tags: number theory , modular arithmetic

Do there exist positive integers $a$ and $b$ such that $a^n+n^b$ and $b^n+n^a$ are relatively prime for all natural $n$?

2001 National Olympiad First Round, 19

Tags: modular arithmetic

If the integers $m,n,k$ hold the equation $221m+247n+323k=2001$, what is the smallest possible value of $k$ greater than $100$? $ \textbf{(A)}\ 124 \qquad\textbf{(B)}\ 111 \qquad\textbf{(C)}\ 107 \qquad\textbf{(D)}\ 101 \qquad\textbf{(E)}\ \text{None of the preceding} $