Olympiad problems

2014 AMC 8, 8

Tags: modular arithmetic

Eleven members of the Middle School Math Club each paid the same amount for a guest speaker to talk about problem solving at their math club meeting. They paid their guest speaker $ \$ \underline{1}$ $ \underline{A}$ $ \underline{2}$. What is the missing digit $A$ of this $3$-digit number? $\textbf{(A) }0\qquad\textbf{(B) }1\qquad\textbf{(C) }2\qquad\textbf{(D) }3\qquad \textbf{(E) }4$

1989 IMO Longlists, 93

Tags: modular arithmetic , prime number , sequence , power of number , number theory

Prove that for each positive integer $ n$ there exist $ n$ consecutive positive integers none of which is an integral power of a prime number.

2009 All-Russian Olympiad, 4

Tags: modular arithmetic , geometric transformation , rotation , combinatorics , geometry

On a circle there are 2009 nonnegative integers not greater than 100. If two numbers sit next to each other, we can increase both of them by 1. We can do this at most $ k$ times. What is the minimum $ k$ so that we can make all the numbers on the circle equal?

2025 Bangladesh Mathematical Olympiad, P8

Tags: divisibility , gcd , modular arithmetic , number theory

Let $a, b, m, n$ be positive integers such that $gcd(a, b) = 1$ and $a > 1$. Prove that if $$a^m+b^m \mid a^n+b^n$$then $m \mid n$.

2013 Brazil Team Selection Test, 3

Tags: number theory , divisibility , modular arithmetic

Let $x$ and $y$ be positive integers. If ${x^{2^n}}-1$ is divisible by $2^ny+1$ for every positive integer $n$, prove that $x=1$.

2008 Germany Team Selection Test, 3

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

Let $ X$ be a set of 10,000 integers, none of them is divisible by 47. Prove that there exists a 2007-element subset $ Y$ of $ X$ such that $ a \minus{} b \plus{} c \minus{} d \plus{} e$ is not divisible by 47 for any $ a,b,c,d,e \in Y.$ [i]Author: Gerhard Wöginger, Netherlands[/i]

2004 Manhattan Mathematical Olympiad, 2

Tags: quadratic , algebra , modular arithmetic

Assume $a,b,c$ are odd integers. Show that the quadratic equation \[ ax^2 + bx + c = 0 \] has no rational solutions. (A number is said to be [i]rational[/i], if it can be written as a fraction: $\frac{\text{integer}}{\text{integer}}$.)

PEN H Problems, 28

Tags: diophantine equation , number theory , relatively prime , modular arithmetic

Let $a, b, c$ be positive integers such that $a$ and $b$ are relatively prime and $c$ is relatively prime either to $a$ or $b$. Prove that there exist infinitely many triples $(x, y, z)$ of distinct positive integers such that \[x^{a}+y^{b}= z^{c}.\]

1996 Romania Team Selection Test, 11

Tags: modular arithmetic , number theory , function

Find all primes $ p,q $ such that $ \alpha^{3pq} -\alpha \equiv 0 \pmod {3pq} $ for all integers $ \alpha $.

2009 Mexico National Olympiad, 2

Tags: number theory , induction , modular arithmetic

In boxes labeled $0$, $1$, $2$, $\dots$, we place integers according to the following rules: $\bullet$ If $p$ is a prime number, we place it in box $1$. $\bullet$ If $a$ is placed in box $m_a$ and $b$ is placed in box $m_b$, then $ab$ is placed in the box labeled $am_b+bm_a$. Find all positive integers $n$ that are placed in the box labeled $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]

2003 Polish MO Finals, 4

Tags: modular arithmetic , number theory

A prime number $p$ and integers $x, y, z$ with $0 < x < y < z < p$ are given. Show that if the numbers $x^3, y^3, z^3$ give the same remainder when divided by $p$, then $x^2 + y^2 + z^2$ is divisible by $x + y + z.$

1998 National Olympiad First Round, 18

Tags: modular arithmetic , prime number , number theory

Let $ p_{1} <p_{2} <\ldots <p_{24}$ be the prime numbers on the interval $ \left[3,100\right]$. Find the smallest value of $ a\ge 0$ such that $ \sum _{i\equal{}1}^{24}p_{i}^{99!} \equiv a\, \, \left(mod\, 100\right)$. $\textbf{(A)}\ 24 \qquad\textbf{(B)}\ 25 \qquad\textbf{(C)}\ 48 \qquad\textbf{(D)}\ 50 \qquad\textbf{(E)}\ 99$

2018 CHKMO, 3

Tags: number theory , modular arithmetic , relatively prime

Let $k$ be a positive integer. Prove that there exists a positive integer $\ell$ with the following property: if $m$ and $n$ are positive integers relatively prime to $\ell$ such that $m^m\equiv n^n \pmod{\ell}$, then $m\equiv n \pmod k$.

2014 Contests, 2

Tags: number theory , modular arithmetic

Find all integers $n$, $n>1$, with the following property: for all $k$, $0\le k < n$, there exists a multiple of $n$ whose digits sum leaves a remainder of $k$ when divided by $n$.

1995 IMO Shortlist, 6

Tags: counting , prime , number theory , modular arithmetic

Let $ p$ be an odd prime number. How many $ p$-element subsets $ A$ of $ \{1,2,\dots,2p\}$ are there, the sum of whose elements is divisible by $ p$?

PEN B Problems, 3

Tags: primitive root , modular arithmetic

Show that for each odd prime $p$, there is an integer $g$ such that $1<g<p$ and $g$ is a primitive root modulo $p^n$ for every positive integer $n$.

2014 AMC 12/AHSME, 23

Tags: divisibility tests , induction , modular arithmetic , function , number theory

The fraction \[\dfrac1{99^2}=0.\overline{b_{n-1}b_{n-2}\ldots b_2b_1b_0},\] where $n$ is the length of the period of the repeating decimal expansion. What is the sum $b_0+b_1+\cdots+b_{n-1}$? $\textbf{(A) }874\qquad \textbf{(B) }883\qquad \textbf{(C) }887\qquad \textbf{(D) }891\qquad \textbf{(E) }892\qquad$

2014 AMC 10, 17

Tags: modular arithmetic

What is the greatest power of 2 that is a factor of $10^{1002}-4^{501}$? $ \textbf{(A) }2^{1002}\qquad\textbf{(B) }2^{1003}\qquad\textbf{(C) }2^{1004}\qquad\textbf{(D) }2^{1005} \qquad\textbf{(E) }2^{1006} \qquad $

2005 Danube Mathematical Olympiad, 4

Tags: modular arithmetic , rectangle , combinatorics , geometry

Let $k$ and $n$ be positive integers. Consider an array of $2\left(2^n-1\right)$ rows by $k$ columns. A $2$-coloring of the elements of the array is said to be [i]acceptable[/i] if any two columns agree on less than $2^n-1$ entries on the same row. Given $n$, determine the maximum value of $k$ for an acceptable $2$-coloring to exist.

2013 NIMO Problems, 7

Tags: modular arithmetic

Let $p$ be the largest prime less than $2013$ for which \[ N = 20 + p^{p^{p+1}-13} \] is also prime. Find the remainder when $N$ is divided by $10^4$. [i]Proposed by Evan Chen and Lewis Chen[/i]

2011 Baltic Way, 3

Tags: least common multiple , modular arithmetic , algebra

A sequence $a_1,a_2,a_3,\ldots $ of non-negative integers is such that $a_{n+1}$ is the last digit of $a_n^n+a_{n-1}$ for all $n>2$. Is it always true that for some $n_0$ the sequence $a_{n_0},a_{n_0+1},a_{n_0+2},\ldots$ is periodic?

1991 Federal Competition For Advanced Students, 3

Tags: number theory , quadratic , induction , modular arithmetic

Find the number of squares in the sequence given by $ a_0\equal{}91$ and $ a_{n\plus{}1}\equal{}10a_n\plus{}(\minus{}1)^n$ for $ n \ge 0.$

2013 USAMTS Problems, 4

Tags: inequalities , prime factorization , arithmetic sequence , modular arithmetic , relatively prime , number theory

Bunbury the bunny is hopping on the positive integers. First, he is told a positive integer $n$. Then Bunbury chooses positive integers $a,d$ and hops on all of the spaces $a,a+d,a+2d,\dots,a+2013d$. However, Bunbury must make these choices so that the number of every space that he hops on is less than $n$ and relatively prime to $n$. A positive integer $n$ is called [i]bunny-unfriendly[/i] if, when given that $n$, Bunbury is unable to find positive integers $a,d$ that allow him to perform the hops he wants. Find the maximum bunny-unfriendly integer, or prove that no such maximum exists.

2024 Israel TST, P3

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

Let $n$ be a positive integer and $p$ be a prime number of the form $8k+5$. A polynomial $Q$ of degree at most $2023$ and nonnegative integer coefficients less than or equal to $n$ will be called "cool" if \[p\mid Q(2)\cdot Q(3) \cdot \ldots \cdot Q(p-2)-1.\] Prove that the number of cool polynomials is even.