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)
Showing posts with label Ring. Show all posts
Showing posts with label Ring. Show all posts
Sunday, 21 April 2013
Sunday, 7 April 2013
Ring Homomorphism
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]
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]
Saturday, 6 April 2013
What is Ideal ?
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
$latex 6=(1+\sqrt{-5})(1-\sqrt{-5})$
=> two factorizations !
=> violates the Fundamental Law of Arithmetic which says UNIQUE Prime Factorization
Unique Prime factors exist called Ideal Primes: $latex \mbox{gcd = 2} , \mbox{ 3}$, $latex (1+\sqrt{-5})$, $latex (1-\sqrt{-5}) $
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 =2x3= u.v =I1.I2.I3.I4 ;
$latex u= (1+\sqrt{-5})$
$latex v=(1-\sqrt{-5})$
Let gcd(2,u) = 2M+N.u
M,N in form of $latex a+b\sqrt{-5}$
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
=> 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
$latex 6=(1+\sqrt{-5})(1-\sqrt{-5})$
=> two factorizations !
=> violates the Fundamental Law of Arithmetic which says UNIQUE Prime Factorization
Unique Prime factors exist called Ideal Primes: $latex \mbox{gcd = 2} , \mbox{ 3}$, $latex (1+\sqrt{-5})$, $latex (1-\sqrt{-5}) $
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 =2x3= u.v =I1.I2.I3.I4 ;
$latex u= (1+\sqrt{-5})$
$latex v=(1-\sqrt{-5})$
Let gcd(2,u) = 2M+N.u
M,N in form of $latex a+b\sqrt{-5}$
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
Saturday, 30 March 2013
Ring Memorize Trick
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.
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.
Chinese Remainder Theorem 中国剩余定理
中国剩余定理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:
$Latex r_3=2, r_5=3, r_7=2$
$Latex 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)
$latex 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
----------------Ring Theory -------------------------------
Commutative Ring CRT by Ring/ Ideal Theory:
If R is a commutative ring & A1,...An are pairwise coprime ideals,
Prove that if
$Latex r_1, r_2, \cdots, r_n$ belong to R
Then there exists 'a' belongs to R with
$Latex 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
$Latex A_3=(3), A_5=(5), A_7=(7)$
$latex r_3=2, r_5=3, r_7=2$
There exists
a=23
$Latex a +A_3 = r_3 + A_3$
23+(3)= 2+ (3)
23 + 1x3 =2 + 8x3 =26
X ≡ 2 (mod 3)
X ≡ 3 (mod 5)
X ≡ 2 (mod 7)
Solve X?
明. 程大位 "算法统宗" (1593)
3人同行70稀
5树梅花21支
7子团圆半个月(15)
除百零五(105)便得知
Let remainders:
$Latex r_3=2, r_5=3, r_7=2$
$Latex 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)
$latex 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)
=> 70x2 ≡ 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)
=> 21x3 ≡ 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)
15x2 ≡ 2 (mod 7)
4)
X ≡ 70x2 +21x3+ 15x2 (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
$Latex r_1, r_2, \cdots, r_n$ belong to R
Then there exists 'a' belongs to R with
$Latex 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
$Latex A_3=(3), A_5=(5), A_7=(7)$
$latex r_3=2, r_5=3, r_7=2$
There exists
a=23
$Latex a +A_3 = r_3 + A_3$
23+(3)= 2+ (3)
23 + 1x3 =2 + 8x3 =26
Subscribe to:
Posts (Atom)