This website contains problems from math contests. Problems and corresponding tags were obtained from the Art of Problem Solving website.

Tags were heavily modified to better represent problems.

AND:
OR:
NO:

Found problems: 23

PEN D Problems, 1
Tags: floor function , modular arithmetic , blogs , Congruences
If $p$ is an odd prime, prove that \[{k \choose p}\equiv \left\lfloor \frac{k}{p}\right\rfloor \pmod{p}.\]

PEN D Problems, 16
Tags: modular arithmetic , number theory , relatively prime , Congruences
Determine all positive integers $n \ge 2$ that satisfy the following condition; For all integers $a, b$ relatively prime to $n$, \[a \equiv b \; \pmod{n}\Longleftrightarrow ab \equiv 1 \; \pmod{n}.\]

PEN D Problems, 19
Tags: modular arithmetic , Congruences
Let $a_{1}$, $\cdots$, $a_{k}$ and $m_{1}$, $\cdots$, $m_{k}$ be integers with $2 \le m_{1}$ and $2m_{i}\le m_{i+1}$ for $1 \le i \le k-1$. Show that there are infinitely many integers $x$ which do not satisfy any of congruences \[x \equiv a_{1}\; \pmod{m_{1}}, x \equiv a_{2}\; \pmod{m_{2}}, \cdots, x \equiv a_{k}\; \pmod{m_{k}}.\]

PEN D Problems, 21
Tags: Euler , modular arithmetic , Congruences
Determine the last three digits of \[2003^{2002^{2001}}.\]

PEN D Problems, 4
Tags: modular arithmetic , blogs , Congruences
Let $n$ be a positive integer. Prove that $n$ is prime if and only if \[{{n-1}\choose k}\equiv (-1)^{k}\pmod{n}\] for all $k \in \{ 0, 1, \cdots, n-1 \}$.

PEN D Problems, 10
Tags: modular arithmetic , quadratics , Congruences
Let $p$ be a prime number of the form $4k+1$. Suppose that $2p+1$ is prime. Show that there is no $k \in \mathbb{N}$ with $k<2p$ and $2^k \equiv 1 \; \pmod{2p+1}$.

PEN D Problems, 14
Tags: modular arithmetic , Congruences
Determine the number of integers $n \ge 2$ for which the congruence \[x^{25}\equiv x \; \pmod{n}\] is true for all integers $x$.

PEN D Problems, 11
Tags: quadratics , induction , modular arithmetic , symmetry , Congruences
During a break, $n$ children at school sit in a circle around their teacher to play a game. The teacher walks clockwise close to the children and hands out candies to some of them according to the following rule. He selects one child and gives him a candy, then he skips the next child and gives a candy to the next one, then he skips 2 and gives a candy to the next one, then he skips 3, and so on. Determine the values of $n$ for which eventually, perhaps after many rounds, all children will have at least one candy each.

PEN D Problems, 12
Tags: modular arithmetic , floor function , abstract algebra , number theory , relatively prime , group theory , Congruences
Suppose that $m>2$, and let $P$ be the product of the positive integers less than $m$ that are relatively prime to $m$. Show that $P \equiv -1 \pmod{m}$ if $m=4$, $p^n$, or $2p^{n}$, where $p$ is an odd prime, and $P \equiv 1 \pmod{m}$ otherwise.

PEN D Problems, 5
Tags: modular arithmetic , Congruences
Prove that for $n\geq 2$, \[\underbrace{2^{2^{\cdots^{2}}}}_{n\text{ terms}}\equiv \underbrace{2^{2^{\cdots^{2}}}}_{n-1\text{ terms}}\; \pmod{n}.\]

PEN D Problems, 8
Tags: Congruences
Characterize the set of positive integers $n$ such that, for all integers $a$, the sequence $a$, $a^2$, $a^3$, $\cdots$ is periodic modulo $n$.

PEN D Problems, 17
Tags: modular arithmetic , Congruences
Determine all positive integers $n$ such that $ xy+1 \equiv 0 \; \pmod{n} $ implies that $ x+y \equiv 0 \; \pmod{n}$.

PEN D Problems, 7
Tags: modular arithmetic , number theory , Congruences
Somebody incorrectly remembered Fermat's little theorem as saying that the congruence $a^{n+1} \equiv a \; \pmod{n}$ holds for all $a$ if $n$ is prime. Describe the set of integers $n$ for which this property is in fact true.

PEN D Problems, 6
Tags: modular arithmetic , induction , Euler , search , Congruences
Show that, for any fixed integer $\,n \geq 1,\,$ the sequence \[2, \; 2^{2}, \; 2^{2^{2}}, \; 2^{2^{2^{2}}}, \cdots \pmod{n}\] is eventually constant.

PEN D Problems, 9
Tags: modular arithmetic , Congruences
Show that there exists a composite number $n$ such that $a^n \equiv a \; \pmod{n}$ for all $a \in \mathbb{Z}$.

PEN D Problems, 20
Tags: Congruences
Show that $1994$ divides $10^{900}-2^{1000}$.

PEN D Problems, 3
Tags: modular arithmetic , number theory , prime numbers , Congruences
Show that \[(-1)^{\frac{p-1}{2}}{p-1 \choose{\frac{p-1}{2}}}\equiv 4^{p-1}\pmod{p^{3}}\] for all prime numbers $p$ with $p \ge 5$.

PEN D Problems, 18
Tags: algebra , polynomial , modular arithmetic , function , Congruences
Let $p$ be a prime number. Determine the maximal degree of a polynomial $T(x)$ whose coefficients belong to $\{ 0,1,\cdots,p-1 \}$, whose degree is less than $p$, and which satisfies \[T(n)=T(m) \; \pmod{p}\Longrightarrow n=m \; \pmod{p}\] for all integers $n, m$.

PEN D Problems, 2
Tags: modular arithmetic , Putnam , group theory , abstract algebra , blogs , Congruences
Suppose that $p$ is an odd prime. Prove that \[\sum_{j=0}^{p}\binom{p}{j}\binom{p+j}{j}\equiv 2^{p}+1\pmod{p^{2}}.\]

PEN D Problems, 23
Tags: quadratics , modular arithmetic , Congruences
Let $p$ be an odd prime of the form $p=4n+1$. [list=a][*] Show that $n$ is a quadratic residue $\pmod{p}$. [*] Calculate the value $n^{n}$ $\pmod{p}$. [/list]

PEN D Problems, 15
Tags: modular arithmetic , inequalities , Congruences
Let $n_{1}, \cdots, n_{k}$ and $a$ be positive integers which satify the following conditions:[list][*] for any $i \neq j$, $(n_{i}, n_{j})=1$, [*] for any $i$, $a^{n_{i}} \equiv 1 \pmod{n_i}$, [*] for any $i$, $n_{i}$ does not divide $a-1$. [/list] Show that there exist at least $2^{k+1}-2$ integers $x>1$ with $a^{x} \equiv 1 \pmod{x}$.

PEN D Problems, 22
Tags: logarithms , Congruences
Prove that $1980^{1981^{1982}} + 1982^{1981^{1980}}$ is divisible by $1981^{1981}$.

PEN D Problems, 13
Tags: algebra , polynomial , modular arithmetic , calculus , integration , Congruences
Let $\Gamma$ consist of all polynomials in $x$ with integer coefficients. For $f$ and $g$ in $\Gamma$ and $m$ a positive integer, let $f \equiv g \pmod{m}$ mean that every coefficient of $f-g$ is an integral multiple of $m$. Let $n$ and $p$ be positive integers with $p$ prime. Given that $f,g,h,r$ and $s$ are in $\Gamma$ with $rf+sg\equiv 1 \pmod{p}$ and $fg \equiv h \pmod{p}$, prove that there exist $F$ and $G$ in $\Gamma$ with $F \equiv f \pmod{p}$, $G \equiv g \pmod{p}$, and $FG \equiv h \pmod{p^n}$.