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 )

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 )

Does below picture looks like a ring, or a clock if it is Z12 = {1 2 3 … 12 = 0}.

Integers (Z) have 3 operations : {+ – x} but not {÷} (or multiplicative inverse) – otherwise 2 integers divide would give a fraction (Q) which falls out of Z family.

An important property of “special ring” Zp for any prime number p, eg. Z2 = {0 , 1} has additional “÷” operation (or multiplicative inverse) besides {+ – ×}, so it is a “Field”.

Example: Z5 = {0 1 2 3 4}

2.3 = 6 = 1 (mod 5)

=> 2 has a multiplicative inverse 3 in Z5, vice versa.

Zp is useful in encryption coding “RSA” using prime number theorems such as The Chinese Reminder Theorem and Fermat’s Little Theorem.

The answer is : “Yes” but with some exceptions.

Most pedagogy mistake made in Abstract Algebra teaching is in the wrong order (by historical chronological sequence of discovery):

[X] Group -> Ring -> Field

It would be better, conceptual wise, to reverse the teaching order as:

Field -> Ring -> Group

or better still as (the author thinks):

Ring -> Field -> Group

- Reason 1:
**Ring**is the Integers, most familiar to 8~ 10-year-old kids in primary school arithmetic class involving only 3 operations: ” + – x”. - Reason 2:
**Field**is the Real numbers familiar in calculators involving 4 operations: ” + – × ÷”, 1 extra division operation than Ring. - Reason 3:
**Group**is “Symmetry”, although mistakenly viewed as ONLY 1 operation, but not as easily understandable like Ring and Field, because group operation can be non-numeric such as “rotation” of triangles, “permutation” of roots of equation, “composition” of functions, etc. The only familiar Group is (Z,+), ie Integers under ” +” operation.

Some features which separate Advanced Math from Elementary Math are:

Proof [1] Infinity [2] Abstract [3] Non Visual [4]

Note [1]: “Proof” is, unfortunately, postponed from high-school Math to university level. This does not include the Euclidean Geometry axiomatic proof or Trigonometry Identity proof, which are still in Secondary school Elementary Math but less emphasized since the 1990s (unfortunately).

Note [2]: However, some “potential” infinity still in Elementary math, such as 1/3 = 0.3333…only the “Cantor” Infinity of Real number, etc are excluded.

Note [3]: Some abstract Algebra like the axioms in Ring and Field (but not Group) can be in Elementary Math to “prove” (as in [1]): eg. By distributive law

By commutative law

Note [4]: Geometry was a “Visual” Math in Euclidean Geometry since ancient Greek. By 17 CE, Fermat and Descartes introduced Algebra into Geometry as the **Analytical Geometry**, still visual in (x, y) coordinate graphs.

20 CE Klein proposed treating Geometry as Group Transformation of Symmetry.

Abstract Algebra concept “Vector Space” with inner (*aka dot*) product is introduced into High School (Baccalaureate) Elementary Math – a fancy name in “AFFINE GEOMETRY” (仿射几何 , see Video 31).

eg. Let vectors

**Translation**:

**Stretching** by a factor (“scalar”):

**Distance** (x,y) from origin: |(x,y)|

Angle between 2 vectors :

**Ref**: 《Elements of Mathematics – From Euclid to Gödel》by John Stillwell (Princeton University Press, 2016) [NLB # 510.711]

Lord of the “Ring”:

The term Ring first introduced by David Hilbert (1862-1943) for Z and Polynomial.

The fully abstract axiomatic theory of commutative rings by his student Emmy Noether in her paper “Ideal Theory in Rings” @1921.

eg. 3 Classical Rings:

1. Matrices over Field

2. Integer Z

3. Polynomial over Field.

**Ring Confusions**

Assume all Rings with 1 for * operation.

Ring has operation + forms an Abelian group, operation * forms a semi group (Close, Associative).

1) Ever ask why must be Abelian + group ?

Apply Distributive Axioms below:

(a+b).(1+1) = a.(1+1) + b.(1+1)

= a + a + b + b …[1]

Or,

(a+b).(1+1) = (a+b).1 + (a+b).1

= a + b + a + b …[2]

[1]=[2]:

a + (a + b) + b = a + (b + a) +b

=> a + b = b + a

Therefore, + must be Abelian in order for Ring’s * to comply with distributive axiom wrt +.

2). Subring

Z/6Z ={0,1,2,3,4,5}

3.4=0 => 3, 4 zero divisor

has subrings: {0,2,4},{0,3}

3). Identity 1 and Units of Ring

Z/6Z has identity 1

but 2 subrings do not have 1 as identity.

subrings {0,2,4}:

0.4=0

2.4=2,

4.4=4 => identity is 4

4 is also a unit.

**Units**: Ring R with 1.

∀a ∈ R ∃b ∈ R s.t.

a.b=b.a = 1

=> a is unit

and b its inverse a^-1

Z/6Z: identity for * is 1

5.5 = 1

5 is Unit besides 1 which is also unit. (1.1=1)

Ring Homomorphism

Math Olympiad uses Elementary Math up to upper-secondary school level, for Number Theory questions students are forced to memorize complex tricks without knowing the essence of Math.

As the great 19th century German Math educator Felix Klein said we should look at Elementary Math in secondary schools from the angle of higher Math, below is an example applying Abstract Algebra of “Ring Homomorphism”:

Let integer N= a1a2…aj

Prove: N is divisible by 9 if

9 | (a1+ a2+ a3+…+ aj)

Proof

Let Φ: Z -> Z/9Z = {0,1,2,3…8}

Φ(z) = z mod 9

Φ is a Ring homomorphism from Ring Z to its Subring Z/9Z.

Note: Homomorphism in Math Structure (Group, Ring, etc) is like “Similarity” of triangles in Geometry.

WLOG (Without Loss of Generality)

Let j=4

N = a1a2a3a4

= a1.10³ + a2.10² + a3.10+ a4

Since in Z/9Z

Φ(aj) = aj for all j

Φ (10) = 1

Φ (10ⁿ) = Φ(10)ⁿ= 1ⁿ = 1

Φ(N)

= Φ(a1.10³ + a2.10² + a3.10+ a4)

= Φ(a1.10³ ) + Φ(a2.10² )

+ Φ(a3.10 ) + Φ(a4 )

= Φ(a1).Φ(10³ ) + Φ(a2).Φ(10² ) +

Φ(a3).Φ(10 ) + Φ(a4 )

= (a1).1 +(a2).1+ (a3).1 + (a4)

= a1+ a2+ a3+ a4

Hence,

Φ(a1a2a3a4) = a1+ a2+ a3+ a4

=> a1a2a3a4 is divisible by 9 if

9 | ( a1+ a2+ a3+ a4)

[QED]

Anything inside x outside still comes back inside

=> Zero x Anything = Zero

=> Even x Anything = Even

Mathematically,

1. nZ is an Ideal, represented by (n)

Eg. Even subring (2Z) x anything big Ring Z = 2Z = Even

2. (football) Field F is ‘sooo BIG’ that

(inside = outside)

=> Field has NO Ideal (except trivial 0 and F)

**Why was Ideal invented** ? because of ‘failure” of UNIQUE Primes Factorization” for this case (example):

6 = 2 x 3

but also

=> two factorizations !

=> violates the *Fundamental Law of Arithmetic* which says UNIQUE Prime Factorization

Unique Prime factors exist called **Ideal** Primes: , ,

**Greatest Common Divisor (gcd or H.C.F.)**:

For n,m in Z

gcd (a,b)= ma+nb

Example: gcd(6,8) = (-1).6+(1).8=2

(m=-1, n=-1)

**Dedekind’s Ideals (Ij):**

6 =2×3= u.v =I1.I2.I3.I4 ;

Let gcd(2,u) = 2M+N.u

M,N in form of

1. Principal Ideals:

2M = (2) = multiple of 2

2. Ideals (nonPrincipal) = 2M+N.u

3. Ideal prime factors: 6=2 x 3=u.v

Let

I1= gcd(2, u)

I2=gcd(2, v)

I3=gcd(3, u)

I4=gcd(3, v)

* Easy to verify (by definition)*:

I1.I2=(2)

I3.I4=(3)

I1.I3=(u)

I1.I4=(v)

=> Ij are prime & unique factors of 6=I1.I2.I3.I4

=> Fundamental Law of Arithmetic satisfied!

=>Ij “**Ideal**“-ly exist! hidden behind ‘compound’ (2,3,u,v) !

**Verify** : gcd(2, 1+√-5).gcd(2, 1-√-5)=(2) ?

Proof by definition:

[2m+n(1+√-5)][2m’+n'(1-√-5)]

=[2m+n+n√-5 ][2m’+n’-n’√-5]

= 4mm’+2mn’+2nm’+6nn’

= 2(2mm’+mn’+m’n+3nn’)

= 2M

= 2 multiples

= (2) = Principal Ideal

Memorize Trick For Ring:

1. Ring (R) is for Marriage with 2 operations: + (addition of kids), * (multiply asset).

2. (R , +) is Commutative Group

Analogy: your kids are also your wife’s kids, vice versa.

3. (R ,*) is Semi-Group (only closure & associative)

Analogy: your asset to multiply (*) is semi (50%) owned by your wife.

4. Fair distributive law for * with respect to +

=> distribute your asset (a) to your kids (k) & wife (w):

a*(k+w) = a*k + a*w

5. No division (/) operation => Ring can’t be broken.

中国剩余定理CRT (Chinese Remainder Theorem)

X ≡ 2 (mod 3)

X ≡ 3 (mod 5)

X ≡ 2 (mod 7)

Solve X?

明. 程大位 “算法统宗” (1593)

3人同行70稀

5树梅花21支

7子团圆半个月(15)

除百零五(105)便得知

Let remainders:

r= 2.70 +3.21 +2.15 (mod 105)

r= 140 +63 +30 (mod 105)

r= 233 (mod 105)

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

belong to R

Then there exists ‘a’ belongs to R with

; 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

There exists

a=23

23+(3)= 2+ (3)

23 + 1×3 =2 + 8×3 =26