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

# Fermat’s Little Theorem Co-prime Condition

It is confusing for students regarding the two forms of the Fermat’s Little Theorem, which is the generalization of the ancient Chinese Remainder Theorem (中国剩馀定理) — the only theorem used in modern Computer Cryptography .

General: For any number a

$\boxed { a^p \equiv a \mod p, \forall a}$

We get,
$a^{p} - a \equiv 0 \mod p$
$a. (a^{(p-1)} -1) \equiv 0 \mod p$
$p \mid a.(a^{(p-1)} -1)$
If (a, p) co-prime, or g.c.d.(a, p)=1,
then p cannot divide a,
thus
$p \mid (a^{(p-1)} -1)$
$a^{(p-1)} -1 \equiv 0 \mod p$

Special: g.c.d. (a, p)=1

$\boxed {a^{(p-1)} \equiv 1 \mod p, \forall a \text { co-prime p}}$

# Chinese Remainder Theorem 中国剩余定理

X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (mod 7)
Solve X?

3人同行70稀
5树梅花21支
7子团圆半个月(15)

Let remainders:
$r_3=2, r_5=3, r_7=2$
$r= r_3.70+ r_5.21 + r_7.15 (mod 3.5.7)$
r= 2.70 +3.21 +2.15 (mod 105)
r= 140 +63 +30 (mod 105)
r= 233 (mod 105)
$r= 23 = x_{min}$
or X= 23 +105Z (23 + multiples of 105)

——————————————-
CRT: Why 3:70, 5:21, 7:15
X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (mod 7)

1) Find A such that
A ≡ 1 (mod 3)
A ≡ 0 (mod 5)
A ≡ 0 (mod 7)

=> 5|A, 7|A => 35 |A

A=35, 70 …
70 ≡ 1 (mod 3)
=> 70×2 ≡ 2 (mod 3)
2) Find B s.t.:
B ≡ 0 (mod 3)
B ≡ 1 (mod 5)
B ≡ 0 (mod 7)
3|B, 7|B => 21|B
21 ≡ 1 (mod 5)
=> 21×3 ≡ 3 (mod 5)
3) Find C s.t. :
C ≡ 0 (mod 3)
C ≡ 0 (mod 5)
C ≡ 1 (mod 7)
=> 3|C, 5|C => 15|C
=> C=15≡ 1 (mod 7)
15×2 ≡ 2 (mod 7)
4)
X ≡ 70×2 +21×3+ 15×2 (mod 3x5x7)
X≡ 233 (mod 105)
X≡ 23 (mod 105)
X= 23+105Z

—————-Ring Theory ——————————-
Commutative Ring CRT by Ring/ Ideal Theory:
If R is a commutative ring & A1,…An are pairwise coprime ideals,
Prove that if
$r_1, r_2, \cdots, r_n$ belong to R
Then there exists ‘a’ belongs to R with
$a + A_j= r_j + A_j$ ; j ∈[1,n]
Interpretation:
Let R= Z ring
X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (mod 7)
Or
X ≡ rj (mod mj)

Ideal = (m) = mZ
$A_3=(3), A_5=(5), A_7=(7)$
$r_3=2, r_5=3, r_7=2$
There exists
a=23
$a +A_3 = r_3 + A_3$
23+(3)= 2+ (3)
23 + 1×3 =2 + 8×3 =26