# The Ring Z/nZ, Fermat Little Theorem, Chinese Theorem (French)

Revision: Modular Arithmetics

(1/2) Fermat Little Theorem

(1/2) Chinese Theorem

(Note: This is the “RING” foundation of “The Chinese Remainder Theorem” which deals with remainders )

# A General Proof of “The Theorem Wu”

“The Theorem Wu” as submitted by Mr. William Wu on the public Math Research Papers site viXra (dated 19-Nov-2014) can be further generalized as follows :

The Theorem Wu (General Case)
Prove that: if p is prime and p> 2 , for any integer $k \geq 1$

$\boxed {(p - 1)^{p^k} \equiv -1 \mod {p^k}}$

[Special case: For p=2, k = 1 (only)]

General case :
$p = p_1.p_2... p_j...$ for all pj satisfying the theorem.

Examples:
$p = 3, k=2, 3^2 = 9$
$(3-1)^9 = 512 \equiv -1 \mod 3^2$
p = 9 = 3×3
p = 21= 3×7
p = 27 = 3×9 = 3x3x3
p =105 = 3x5x7
p =189 = 3x7x3x3

[Mr. William Wu proved the non-general case by using the Binomial Theorem and Legendre’s Theorem]

I envisage below to prove for all cases
by using the Advanced Algebra “Galois Finite Field Theory” :

Let $\boxed {q = p^k}$
where p prime and k >=1, the Fundamental Theorem of Galois Finite Field states that
1. The Galois Finite Field GF(p) is a multiplicative cyclic group;
2. GF(q) is the Galois Field extension of GF(p)
.

Step 1: Identity Equation:

$\boxed { (X+Y)^q \equiv X^q + Y^q \mod q }$

Proof:
$\displaystyle{ (X+Y)^q = \sum_{r=0}^{q}\binom {q}{r}.X^{r}.Y^{q-r} }$
Except the first term X^q and the last term Y^q (both with coefficient 1), all the middle terms with coefficients as :
$\binom {q}{r} = \frac { q! }{(r!)(q-r)!} = \frac { q.(q-1)! }{(r!)(q-r)!}$
are divisible by q,
$\binom {q}{r} \equiv 0 \mod q$
thus,
$(X+Y)^q \equiv X^q + Y^q \mod q$
[QED]

Step 2:
Apply the Identity Equation:
$(X^q + Y^q) \equiv (X+Y)^q \mod q$
we get,
$(p-1)^q + 1^q= [(p-1)+(1)]^q = p^q$
$\boxed {(p-1)^q + 1^q = p^q }$ ….. [*]
Since GF(q) is a multiplicative cyclic group of order q, we get
$p^q \equiv 0 \mod q$

$(p-1)^q + 1^q \equiv 0 \mod q$
$\boxed {(p-1)^{p^k} \equiv -1 \mod p^k }$
[QED]

Step 3: General case
Let $p = p_1.p_2.... p_j... \forall p_j \text { satisfying the Theorem}$

Apply the Step 2 equation [*],
$(p-1)^q + 1^q = p^q$
$p^q=( p_1.p_2.... p_j... )^q$
$p^q = ( p_1)^q.(p_2)^q...(p_j)^q...$
$\forall j, (p_j)^q \equiv 0 \mod q$
$(p-1)^q + 1^q \equiv 0 \mod q$
$\boxed {(p-1)^{p^k} \equiv -1 \mod p^k }$
[QED]

Lemma :
$\boxed { \text {The Theorem Wu is true for any ODD numbers p} }$

Proof: By The Fundamental Theorem of Arithmetic, any number (even and odd numbers) can be factorized as a product of primes.
Since The Theorem Wu is true for primes only,
=> it is false for even numbers
=> by the General case above, it is true for all odd numbers.

If m an even number,
$\boxed {(m - 1)^{m^k} \equiv +1 \mod {m^k}}$

Note: Wolfram Alpha verification
For p any prime or product of primes:
$\boxed {\forall k \geq 1, q= p^k \implies p^q \equiv 0 \mod q}$

Galois Fundamental Finite Field Theorem

Note:
This is an excellent example of marriage of ancient Chinese Math, Middle-Age French Maths (Fermat & Galois) and modern Chinese (Singaporean) Maths — across 2,000 years!
The Theorem Wu is more general than the Ancient Chinese Remainder Theorem in 2 CE, which was further improved by 17 CE Fermat’s Little Theorem.
The Theorem Wu proves any number is/isn’t
1) a prime or
2) a product of primes > 2 (this property is neither found in Chinese Remainder Theorem nor Fermat’s).