Olympiad problems

PEN D Problems, 8

Tags: congruence

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, 10

Tags: congruence , quadratic , modular arithmetic

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, 18

Tags: algebra , polynomial , congruence , modular arithmetic , function

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

Russian TST 2019, P2

Tags: congruence , number theory

Prove that for every odd prime number $p{}$, the following congruence holds \[\sum_{n=1}^{p-1}n^{p-1}\equiv (p-1)!+p\pmod{p^2}.\]

PEN D Problems, 3

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

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, 9

Tags: congruence , modular arithmetic

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, 11

Tags: symmetry , modular arithmetic , induction , quadratic , congruence

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.

1998 Belarus Team Selection Test, 2

Tags: modular arithmetic , congruence , algebra , polynomial

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

1997 IMO Shortlist, 12

Tags: polynomial , modular arithmetic , congruence , algebra

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

PEN D Problems, 13

Tags: modular arithmetic , algebra , calculus , polynomial , congruence , integration

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

PEN D Problems, 14

Tags: modular arithmetic , congruence

Determine the number of integers $n \ge 2$ for which the congruence \[x^{25}\equiv x \; \pmod{n}\] is true for all integers $x$.

2019 Oral Moscow Geometry Olympiad, 2

Tags: geometry , diagonal , congruent , quadrilateral , congruence

The angles of one quadrilateral are equal to the angles another quadrilateral. In addition, the corresponding angles between their diagonals are equal. Are these quadrilaterals necessarily similar?