Olympiad problems

2012 Tuymaada Olympiad, 4

Let $p=1601$. Prove that if \[\dfrac {1} {0^2+1}+\dfrac{1}{1^2+1}+\cdots+\dfrac{1}{(p-1)^2+1}=\dfrac{m} {n},\] where we only sum over terms with denominators not divisible by $p$ (and the fraction $\dfrac {m} {n}$ is in reduced terms) then $p \mid 2m+n$. [i]Proposed by A. Golovanov[/i]

2013 Iran Team Selection Test, 8

Tags: modular arithmetic , greatest common divisor , number theory

Find all Arithmetic progressions $a_{1},a_{2},...$ of natural numbers for which there exists natural number $N>1$ such that for every $k\in \mathbb{N}$: $a_{1}a_{2}...a_{k}\mid a_{N+1}a_{N+2}...a_{N+k}$

2009 China Team Selection Test, 2

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

Find all integers $ n\ge 2$ having the following property: for any $ k$ integers $ a_{1},a_{2},\cdots,a_{k}$ which aren't congruent to each other (modulo $ n$), there exists an integer polynomial $ f(x)$ such that congruence equation $ f(x)\equiv 0 (mod n)$ exactly has $ k$ roots $ x\equiv a_{1},a_{2},\cdots,a_{k} (mod n).$

2006 Moldova National Olympiad, 10.8

Tags: modular arithmetic , induction , number theory

Let $M=\{x^2+x \mid x\in \mathbb N^{\star} \}$. Prove that for every integer $k\geq 2$ there exist elements $a_{1}, a_{2}, \ldots, a_{k},b_{k}$ from $M$, such that $a_{1}+a_{2}+\cdots+a_{k}=b_{k}$.

1981 Bundeswettbewerb Mathematik, 4

Tags: modular arithmetic , number theory

Prove that for any prime number $p$ the equation $2^p+3^p=a^n$ has no solution $(a,n)$ in integers greater than $1$.

2007 AIME Problems, 8

Tags: geometry , rectangle , calculus , integration , derivative , quadratic , modular arithmetic

A rectangular piece of of paper measures 4 units by 5 units. Several lines are drawn parallel to the edges of the paper. A rectangle determined by the intersections of some of these lines is called [i]basic [/i]if (i) all four sides of the rectangle are segments of drawn line segments, and (ii) no segments of drawn lines lie inside the rectangle. Given that the total length of all lines drawn is exactly 2007 units, let $N$ be the maximum possible number of basic rectangles determined. Find the remainder when $N$ is divided by 1000.

2002 National Olympiad First Round, 22

Tags: modular arithmetic

If $2^n$ divides $5^{256} - 1$, what is the largest possible value of $n$? $ \textbf{a)}\ 8 \qquad\textbf{b)}\ 10 \qquad\textbf{c)}\ 11 \qquad\textbf{d)}\ 12 \qquad\textbf{e)}\ \text{None of above} $

2011 AMC 10, 23

Tags: modular arithmetic , euler , function , number theory , least common multiple , search

What is the hundreds digit of $2011^{2011}$? $ \textbf{(A)}\ 1 \qquad \textbf{(B)}\ 4 \qquad \textbf{(C)}\ 5 \qquad \textbf{(D)}\ 6 \qquad \textbf{(E)}\ 9 $

2013 Gulf Math Olympiad, 3

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

There are $n$ people standing on a circular track. We want to perform a number of [i]moves[/i] so that we end up with a situation where the distance between every two neighbours is the same. The [i]move[/i] that is allowed consists in selecting two people and asking one of them to walk a distance $d$ on the circular track clockwise, and asking the other to walk the same distance on the track anticlockwise. The two people selected and the quantity $d$ can vary from move to move. Prove that it is possible to reach the desired situation (where the distance between every two neighbours is the same) after at most $n-1$ moves.

1998 Iran MO (3rd Round), 1

Tags: modular arithmetic , number theory , divisibility

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

2023 USAMO, 5

Tags: arithmetic sequence , modular arithmetic , prime

Let $n\geq3$ be an integer. We say that an arrangement of the numbers $1$, $2$, $\dots$, $n^2$ in a $n \times n$ table is [i]row-valid[/i] if the numbers in each row can be permuted to form an arithmetic progression, and [i]column-valid[/i] if the numbers in each column can be permuted to form an arithmetic progression. For what values of $n$ is it possible to transform any row-valid arrangement into a column-valid arrangement by permuting the numbers in each row?

2011 Iran MO (3rd Round), 5

Tags: modular arithmetic , number theory

Suppose that $k$ is a natural number. Prove that there exists a prime number in $\mathbb Z_{[i]}$ such that every other prime number in $\mathbb Z_{[i]}$ has a distance at least $k$ with it.

2012 China Team Selection Test, 3

Tags: function , modular arithmetic , algebra , functional equation , number theory

Given an integer $n\ge 2$, a function $f:\mathbb{Z}\rightarrow \{1,2,\ldots,n\}$ is called [i]good[/i], if for any integer $k,1\le k\le n-1$ there exists an integer $j(k)$ such that for every integer $m$ we have \[f(m+j(k))\equiv f(m+k)-f(m) \pmod{n+1}. \] Find the number of [i]good[/i] functions.

2001 IMO Shortlist, 6

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

Is it possible to find $100$ positive integers not exceeding $25,000$, such that all pairwise sums of them are different?

2009 Moldova Team Selection Test, 4

Tags: modular arithmetic , combinatorics

[color=darkblue]Let $ X$ be a group of people, where any two people are friends or enemies. Each pair of friends from $ X$ doesn't have any common friends, and any two enemies have exactly two common friends. Prove that each person from $ X$ has the same number of friends as others.[/color]

2019 China Team Selection Test, 4

Tags: modular arithmetic , number theory

Does there exist a finite set $A$ of positive integers of at least two elements and an infinite set $B$ of positive integers, such that any two distinct elements in $A+B$ are coprime, and for any coprime positive integers $m,n$, there exists an element $x$ in $A+B$ satisfying $x\equiv n \pmod m$ ? Here $A+B=\{a+b|a\in A, b\in B\}$.

2015 India National Olympiad, 6

Tags: quadratic , modular arithmetic , pigeonhole principle , number theory

Show that from a set of $11$ square integers one can select six numbers $a^2,b^2,c^2,d^2,e^2,f^2$ such that $a^2+b^2+c^2 \equiv d^2+e^2+f^2\pmod{12}$.

1997 IMO Shortlist, 12

Tags: algebra , polynomial , modular arithmetic , congruence

Let $ p$ be a prime number and $ f$ an integer polynomial of degree $ d$ such that $ f(0) = 0,f(1) = 1$ and $ f(n)$ is congruent to $ 0$ or $ 1$ modulo $ p$ for every integer $ n$. Prove that $ d\geq p - 1$.

1973 AMC 12/AHSME, 18

Tags: probability , modular arithmetic , number theory , prime number

If $ p \geq 5$ is a prime number, then $ 24$ divides $ p^2 \minus{} 1$ without remainder $ \textbf{(A)}\ \text{never} \qquad \textbf{(B)}\ \text{sometimes only} \qquad \textbf{(C)}\ \text{always} \qquad$ $ \textbf{(D)}\ \text{only if } p \equal{}5 \qquad \textbf{(E)}\ \text{none of these}$

1988 IMO Longlists, 1

Tags: linear recurrence , modular arithmetic , linear algebra , algebra , sequence , divisibility

An integer sequence is defined by \[{ a_n = 2 a_{n-1} + a_{n-2}}, \quad (n > 1), \quad a_0 = 0, a_1 = 1.\] Prove that $2^k$ divides $a_n$ if and only if $2^k$ divides $n$.

2020 March Advanced Contest, 1

Tags: function , number theory , modular arithmetic

In terms of $a$, $b$, and a prime $p$, find an expression which gives the number of $x \in \{0, 1, \ldots, p-1\}$ such that the remainder of $ax$ upon division by $p$ is less than the remainder of $bx$ upon division by $p$.

PEN H Problems, 53

Tags: diophantine equation , modular arithmetic

Suppose that $a, b$, and $p$ are integers such that $b \equiv 1 \; \pmod{4}$, $p \equiv 3 \; \pmod{4}$, $p$ is prime, and if $q$ is any prime divisor of $a$ such that $q \equiv 3 \; \pmod{4}$, then $q^{p}\vert a^{2}$ and $p$ does not divide $q-1$ (if $q=p$, then also $q \vert b$). Show that the equation \[x^{2}+4a^{2}= y^{p}-b^{p}\] has no solutions in integers.

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)$.

1993 IberoAmerican, 3

Tags: modular arithmetic , number theory

Two nonnegative integers $a$ and $b$ are [i]tuanis[/i] if the decimal expression of $a+b$ contains only $0$ and $1$ as digits. Let $A$ and $B$ be two infinite sets of non negative integers such that $B$ is the set of all the [i]tuanis[/i] numbers to elements of the set $A$ and $A$ the set of all the [i]tuanis[/i] numbers to elements of the set $B$. Show that in at least one of the sets $A$ and $B$ there is an infinite number of pairs $(x,y)$ such that $x-y=1$.

2007 Alexandru Myller, 1

Tags: algebra , modular arithmetic , number theory

[b]a)[/b] Show that $ n^2+2n+2007 $ is squarefree for any natural number $ n. $ [b]b)[/b] Prove that for any natural number $ k\ge 2 $ there is a nonnegative integer $ m $ such that $ m^2+2m+2k $ is a perfect square.