Class Notes
(808,123)

Canada
(493,018)

University of Waterloo
(18,169)

Mathematics
(1,874)

MATH 135
(334)

Wentang Kuo
(7)

Lecture

# MATH 135 Algebra Notes VI (Oct 28 - Nov 11): Fermate Little Theorem, Linear Congruences, Chinese Remainder Theorem

Unlock Document

University of Waterloo

Mathematics

MATH 135

Wentang Kuo

Fall

Description

MATH 135: Algebra for Honours Mathematics
Notes VI
Michael Brock Li
Computational Mathematics IA
October : Mid-November MXIII
Concordia Cum Veritate
I: Fermat Little Theorem
If p is a prime number that p - a, then
ap▯1 ▯ 1 (mod p)
A simple theorem...a hard proof.
Analyze this:
Proof. If p - a, we show that a;2a;3a;:::(p ▯ 1)a are distinct modulo p.
Suppose,
ra ▯ sa (mod p);1 ▯ r < s ▯ (p ▯ 1)
Since, gcd(a;p) = 1, by CD,
r ▯ s (mod p)
But it is not possible for 1 ▯ r < s ▯ (p ▯ 1). Since a;2a;3a;:::(p ▯ 1)a are
distinct modulo p, they must be ▯ to 1;2;3;:::;(p ▯ 1). Multiply these integers
together, we get
a ▯ (2a) ▯ (3a) ▯ ::: ▯ (p ▯ 1)a ▯ 1 ▯ 2 ▯ 3 ▯ ::: ▯ (p ▯ 1) (mod p)
p▯1
(p ▯ 1)!a ▯ (p ▯ 1)! (mod p)
Due to the fact that gcd(p;(p ▯ 1)!) = 1, by CD, we get
p▯1
a ▯ 1 (mod p)
▯
1 Again, this is a hard proof, and most ▯nal exams didn’t contain this type of
question. As a follow up for this theorem,
Remark: For any integer a and any prime p,
p
a ▯ a (mod p)
Proof. Case I: p j a for that a ▯ 0 (mod p)
p
) a ▯ 0 (mod p)
) a ▯ a (mod p)
Case II: if p - a by FlT,
ap▯1 ▯ 1 (mod p)
but a ▯ a (mod p), thus
p▯1
) a a ▯ 1a (mod p)
) a ▯ a (mod p)
▯
Remark: (Existence of Inverses in Z (INV Z ))
p p
Let p be a prime number. If [a] is any non-zero element inpZ , then there exist
an element [b] 2 p such that [a][b] = [1]
Example I:
Allow p = 29 and a = 18. Then thus by FlT,
1828▯ 1 (mod 29)
Example II:
Find p such that
II: Linear Congruences
It has the form
ax ▯ c (mod m)
A solution to such linear congruence is an intege0 x such that
ax 0 c (mod m)
2 Remark: If
ax ▯ c (mod m)
has a solution ()
9 x 2 Z;ax ▯ c (mod m)
0 0
()
9 x0;0 2 Z;ax0+ my =0c
()
gcd(a;m) j c
Thus we approach to a new theorem of linear congruences:
i: Linear Congruence Theorem
Let gcd(a;m) = d 6= 0.
The linear congruence equation
ax ▯ c (mod m)
or
[a][x] = [c] 2mZ
has a solution ()
gcd(a;m) j c
Moreover, the single solution is when x ▯ x . However, if there is more than
0
one solution, it’s representation can be expressed as follows
m m x
x ▯ x0;x0+ ;x0+ 2 ;:::0x + (d ▯ 1)(mod m)
d d d
or
m m x
f[0 ];[0 + ];[0 + 2 ];:::;0x + (d ▯ 1) ]g m Z
d d d
Example I:
Solve 3x ▯ 5 (mod 6).
Solution:
gcd(3;6) = 3 - 5
Thus, there is no solution.
3 Example II:
Solve 4x ▯ 6 (mod 6)
Solution:
gcd(4;10) = 2 j 6
Thus, there is a solution, and by inspection, x = 4 is a solution. Since, 10 is a
small modulus, let’s test all ten possibilities in modulo 10.
x (mod 10) 0 1 2 3 4 5 6 7 8 9
4x (mod 10) 0 4 8 2 6 0 4 8 2 6
We get x ▯ 4 or 9 (mod 10)
III: Chinese Remainder Theorem
This theorem was posed due to the fact that we need to ▯nd a solution in
simultaneous linear congruences. Imagine you are in a classroom with students,
and all of the sudden after a few days, students are dropping out. Assume you
do not have a calculator, calculate how many students are left in the classroom
(without counting every each one of them).
But if you do count them all, 30 students wouldn’t be so bad. But imagine you
have 5000 students in one classroom. Thus, this theorem will come in handy.
i: Chinese Remainder Theorem (CRT)
Let a1;a2;m 1m 22Z with m ;m 1 1.2If gcd(m ;m ) 1 1,2then
(
x ▯ a 1mod m ) 1
(1)
x ▯ a 2mod m ) 2
has a unique solution
x ▯ x (mod m m )
0 1 2
Proof. x ▯ a1(mod m ) 1
()
x = a1+ m y1y 2 Z
Set
x = a + m y;y 2 Z
1 1
into x ▯ a1(mod m )1 and we get,
a1+ m y1▯ a (2od m ) 2
()
a 1 m y1= a ▯2m z;z22 Z
4 ()
m 1 + m z2= a ▯2a ;y1z 2 Z
Since gcd(m 1m )2= 1 j (a 2 a )1 then by Linear Dolphantine Equation Part
1,
m 1 + m z2= a ▯2a ;y1z 2 Z
has a solution.
Thus the complete solution is
m 2
y = y 0 n

More
Less
Related notes for MATH 135