Congruence with Prime Modulus

A single congruence $\pmod{n}$ is equivalent to a set of simultaneous congruences modulo the prime powers $p^e$ appearing in the factorization of $n$.We therefore explore the congruences $\pmod{p^e}$, where $p$ is prime.We will first consider the simplest case $e=1$

Arithmetic in $\mathbb{Z}_p$

We saw  that a linear congruence $ax \equiv b \pmod{n}$ has a unique solution $\pmod {n}$ if $gcd(a,n) = 1$. Now if $n$ is a prime $p$, then $gcd(a,n) =gcd(a, p)$ is either 1 or $p$; in the first case, we have a unique solution $\pmod {p}$,while in the second case (where $p|a$), either every $x$ is a solution (when $p| b$) or no $x$ is a solution (when $p \nmid b)$.

One can view this elementary result as saying that if the polynomial $ax -b$ has degree $d = 1$ over $\mathbb{Z}$, (that is, if $a \ne 0 \pmod {p})$, then it has at most one root in $\mathbb{Z}_p$. Now in algebra we learn that a non-trivial polynomial of degree $d$, with real or complex coefficients, has at most $d$ distinct roots in $\mathbb{R}$ or $\mathbb{C}$; it is reasonable to ask whether this is also true for the number system $\mathbb{Z}_p$, since we have just seen that it is true when $d = 1$. Our first main theorem, due to Lagrange, states that this is indeed the case.

Theorem:Let $p$ be prime and let $f(x) = a_dx^d+ \ldots +a_1x + a_0$ be a polynomial with integer coefficients, where $a_i \not \equiv 0 \pmod{p}$ for some $i$. Then the congruence $f(x) \equiv 0 \pmod{p}$ is satisfied by at most $d$ congruence classes $[x] \in Z_p$.

Congruence modulo prime $p$ can be solved using Fermat's Little Theorem and Euler's Theorem.

 

Willson's Theorem is another useful result in the prime modulo congruence.