# 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).