# Some Special Congruences

## Wilson's Theorem
Wilson's Theorem provides an elegant characterization of prime numbers using the factorial function.

:::danger
**Thereom (Wilson's Theorem)**
If $p$ is a prime number, then $$(p-1)! \equiv -1 \pmod{p}$$
:::

:::warning
**Example** For $p=7$, $$(7-1)! = 6! = 720$$ Since $720 = 103 \cdot 7 - 1$, we have $720 \equiv -1 \pmod{7}$.
:::

:::danger
**Thereom (Converse of Wilson's Theorem)**
If $n$ is an integer greater than or equal to 2 such that $$(n-1)! \equiv -1 \pmod n$$ then $n$ is a prime number.
:::

:::warning
**Example** For $n=6$, $$(6-1)! = 5! = 120$$

* Since $120 = 20 \cdot 6$, we have $120 \equiv 0 \pmod{6}$.
* Since $120 \not\equiv -1 \pmod{6}$, the integer 6 is not prime.
:::

## Fermat's Little Theorem
:::danger
**Thereom (Fermat's Little Theorem)**
If $p$ is a prime and $a$ is an integer such that $p \nmid a$, then
$$
a^{p-1} \equiv 1 \pmod{p}
$$
:::

:::warning
**Example** For $p=7$ and $a=3$, $$3^{7-1} = 3^6 = 729$$ Since $729 = 104 \cdot 7 + 1$, we have $3^6 \equiv 1 \pmod{7}$.
:::

### Consequences
1. **(Modular Inverse)** If $p$ is a prime and $p \nmid a$, then $a^{p-2}$ is a modular inverse of $a$ modulo $p$.
2. **(Linear Congruences)** If $p$ is a prime and $p \nmid a$, the solutions of $ax \equiv b \pmod p$ are integers $x$ such that $$x \equiv a^{p-2}b \pmod p$$
3. **(General Form)** If $p$ is a prime and $a$ is any integer (even if $p \mid a$), then $a^p \equiv a \pmod{p}$.

:::warning
**Example** Find the least positive residue of $3^{201}$ modulo 11.

* Fermat's Little Theorem states $3^{11-1} = 3^{10} \equiv 1 \pmod{11}$.
* We divide the exponent: $201 = 20 \cdot 10 + 1$.
* $$3^{201} = 3^{10 \cdot 20 + 1} = 3^1 \cdot (3^{10})^{20} \equiv 3 \cdot 1^{20} \equiv 3 \pmod{11}$$The least positive residue is 3.
:::

:::success
**Exercises**
1. Show that $10!+1$ is divisible by 11, by grouping together pairs of inverses modulo 11 that occur in $10!$.
2. What is the remainder when $16!$ is divided by 19?
3. What is the remainder when $18!$ is divided by 437?
4. Using Fermat's little theorem, find the least positive residue of $3^{999,999,999}$ modulo 7.
5. Show that $42 | (n^7-n)$ for all positive integers $n$.
6. Using Wilson's Theorem, show that if $p$ is a prime and $p \equiv 1 \pmod 4$, then the congruence $x^2 \equiv -1 \pmod p$ has two incongruent solutions given by $x \equiv \pm \left(\frac{p-1}{2}\right)! \pmod p$.
:::

## Quadratic Congruences and Sums of Squares
These results connect Wilson's Theorem to the solvability of $x^2 \equiv -1 \pmod p$ and the representation of integers as a sum of two squares.

:::danger
**Proposition (Solvability of $x^2 \equiv -1 \pmod p$)**

1. If $p \equiv 1 \pmod{4}$, then the quadratic congruence $x^2 \equiv -1 \pmod p$ has exactly two incongruent solutions, which are specifically given by: $$\left(\left(\frac{p-1}{2}\right)!\right)^2 \equiv -1 \pmod{p}$$
2. If $p \equiv 3 \pmod{4}$, then the quadratic congruence $x^2 \equiv -1 \pmod{p}$ is unsolvable (i.e., has no solutions).
:::

:::danger
**Corollary**
Let $p$ be a prime number such that $p \equiv 3 \pmod{4}$. Then for any two integers $a$ and $b$, if $p \mid (a^2 + b^2)$, we must have that $p \mid a$ and $p \mid b$.
:::

### Representation as a Sum of Two Squares
These theorems, famously established by Fermat and others, determine which integers can be written as the sum of two perfect squares.

:::danger
**Theorem (Fermat's Theorem on Sums of Two Squares)**
Let $p$ be a prime satisfying $p \equiv 1 \pmod{4}$. Then there exist unique positive integers $a$ and $b$ such that $a^2 + b^2 = p$.
:::

:::danger
**Theorem (Characterization of Sums of Two Squares)**
Let $n$ be an integer greater than 1. We write the prime factorization of $n$ as:$$n = 2^\alpha \cdot p_1^{\beta_1} \cdots p_k^{\beta_k} \cdot q_1^{\gamma_1} \cdots q_l^{\gamma_l}$$ where $\alpha, \beta_i, \gamma_j$ are nonnegative integers, the $p_i$'s are distinct primes of the form $4k + 1$, and the $q_j$'s are distinct primes of the form $4k + 3$.

Then there exist integers $a, b \in \mathbb{Z}$ such that $a^2 + b^2 = n$ if and only if every prime factor of the form $4k+3$ has an even exponent (i.e., $\gamma_j$ is even for all $j=1, \ldots, l$).
:::