(Thue's theorem) Let $p$ be a prime. Show that for any integer $a$ such that $p\not\mid a$, there exist positive integers $x$, $y$ not exceeding $\lfloor{\sqrt{p}}\rfloor$ satisfying $ax\equiv y\pmod{p}$ or $ax\equiv -y\pmod{p}$.

Show that if the equation $a^2 + 1\equiv 0\pmod{p}$ is solvable for some $a$, then $p$ can be represented as a sum of two squares.

Show that a prime $p > 2$ is a sum of two squares if and only if $p\equiv 1\pmod{4}$.

Let $a$ and $b$ be two positive integers such that both of them can be written as a sum of two squares. Show that their product can be written as a sum of two squares in two ways.

(Two Squares Theorem) Show that a positive integer $n$ is a sum of two squares if and only if each prime factor $p$ of $n$ such that $p\equiv 3\pmod{4}$ occurs to an even power in the prime factorization of $n$.

Find the multiplicative order of $2$ modulo $125$.

Calculate $3^{64}\pmod{67}$.

Find the smallest integer $N$ such that $\varphi(n) \ge 5$ holds for all integer $n \ge N$.

Show that two positive integers $m$ and $n$ are co-prime if and only if $\varphi(mn)=\varphi(m)\varphi(n)$.

Solve the system of congruence $$\left\{ \begin{array}{l} x\equiv 1\pmod{3}\\ x\equiv 2\pmod{5}\\ x\equiv 3\pmod{7} \end{array}  \right.$$

Find the multiplicative order of $3$ modulo $301$.

Solve the congruent system: $4x\equiv 2\pmod{6}$ and $3x\equiv 5\pmod{8}$.

Find the smallest positive integer $n$ such that $$\left\{  \begin{array}{l} n\equiv 1\pmod{3} \\ n\equiv 3\pmod{5} \\ n\equiv 5\pmod{7} \end{array} \right.$$

Let $n$ be an integer greater than $1$. If none of $1!$, $2!$, $\cdots$, $n!$ has the same remainder when being divided by $n$, show that $n$ is a prime.

Let integers $x$, $y$, $z$ satisfy $$(x-y)(y-z)(z-x)=x+y+z$$

Show that $27 \mid (x+y+z)$

Let $n$ be a positive odd integer. Show that at least one of the following numbers is a multiple of $n$. $$2-1, 2^2 -1, \cdots, 2^{n-1} -1$$

Let $p$ be a prime. Show that there exist infinitely many positive integer $n$ such that $p\mid (2^n-n)$.

Let $n^2$ be a square. Show that $n^2\equiv 0, 1\pmod{3}$.

Let $a$, $b$, $c$, and $d$ be four positive integers. Show that $\left(a^{4b+d}-a^{4c+d}\right)$ must be a multiple of $240$.

Let sequence $\{x_n\}$ satisfy the relation $x_{n+2}=x_{n+1}+2x_n$ for $n\ge 1$ where $x_1=1$ and $x_2=3$.

Let sequence $\{y_n\}$ satisfy the relation $y_{n+2}=2y_{n+1}+3y_n$ for $n\ge 1$ where $y_1=7$ and $y_2=17$.

Show that these two sequences do not share any common term.

Let $n$ be an odd integer greater than $3$, and $\mathbb{S}=\{0, 1, \cdots, n-1\}$. Show that after removing any element from $\mathbb{S}$, it is always possible to equally divide the remaining elements in $\mathbb{S}$ into two groups such that their sum are congruent modulo $n$.

Let $n$ be a positive integer not less than $4$. Show that there exists a polynomial with integral coefficients $$f(x) = x^n + a_{n-1}x^{n-1} + a_{n-2}x^{n-2}+\cdots + a_1 x + a_0$$

such that for any positive integer $m$ and any $k \ge 2$ distinct integers $r_1$, $r_2$, $\cdots$, $r_k$, it always hold that $f(m)\ne f(r_1)f(r_2)\cdots f(r_k)$.

Show that there are infinite many composite numbers in the sequence $$1, 31, 331, 3331, 33331, \cdots$$