37 / 62
37
ปีที่ 41 ฉบับที่ 182 พฤษภาคม - มิถุนายน 2556
จากขั้นตอน (2) ถ้าเราเขียน 1 ใหม่ แล้วแทนค่าย้อนกลับ
ขึ้นไปเรื่อย ๆ จะได้
จะเห็นว่า เราสามารถเขียน 1 ในรูปการรวมเชิงเส้นของ 192
และ 7 ได้คือ 1 = 55 . 7 – 2 . 192
ออยเลอร์ฟีฟังก์ชัน (Euler
φ
-function)
สำ
�หรับจำ
�นวนเต็ม n > 1 ให้
φ
(n) แทนจำ
�นวนสมาชิกใน
เซต {1, 2, …, n – 1} ที่เป็นจำ
�นวนเฉพาะสัมพัทธ์กับ n กล่าว
คือเป็นจำ
�นวนของจำ
�นวนเต็ม a ซึ่ง 1 ≤ a ≤ n และ gcd (a, n)
= 1 เช่น ถ้า n = 8 พิจารณาเซต {1, 2, 3, 4, 5, 6, 7} จะพบว่า
gcd (1, 8) = gcd (3, 8) = gcd (5, 8) = gcd (7, 8) = 1
นั่นคือมี a เท่ากับ 1, 3, 5, และ 7 เพียง 4 จำ
�นวนเท่านั้น
ที่เป็นจำ
�นวนเฉพาะสัมพัทธ์กับ 8 ดังนั้น
φ
(8) = 4 เห็นได้ชัด
ว่า ถ้า p เป็นจำ
�นวนเฉพาะแล้ว
φ
(p) = p – 1 เช่น
φ
(11)
= 10 เพราะจำ
�นวนเต็มทุกจำ
�นวนในเซต {1, 2, …, 10} เป็น
จำ
�นวนเฉพาะสัมพัทธ์กับ 11 เรียก
φ
(n) ว่า ออยเลอร์ฟีฟังก์ชัน
ทฤษฎีบทที่สำ
�คัญคือ ถ้า p และ q เป็นจำ
�นวนเฉพาะแล้ว
φ
(pq)
= (p – 1)(q – 1) เช่น ถ้า p = 13 และ q = 17 แล้ว
φ
(pq)
= 12 . 16 = 192 เป็นต้น
จำ
�นวนเต็มมอดุโล n
ให้ a, b และ n เป็นจำ
�นวนเต็มซึ่ง n >1 ถ้า n หาร a – b
ได้ลงตัวแล้ว เราจะกล่าวว่า a คอนกรูเอน (congruence) กับ
b มอดุโล n หรือเขียน a
≡
b (mod n) เช่น
2
≡
5 (mod 3) เพราะ 3 หาร 2 – 5 = –3 ได้ลงตัว หรือ
–7
≡
4 (mod 11) เพราะ 11 หาร –7 – 4 = –11 ได้ลงตัว
เราสามารถพิสูจน์สมบัติ 2 ข้อ ต่อไปนี้ได้ไม่ยากนัก
1. ถ้า a
≡
b (mod n) และ b
≡
c (mod n) แล้ว a
≡
c (mod n)
2. ถ้า a
≡
b (mod n) และ c
≡
d (mod n) แล้ว ac
≡
bc (mod n)
จากสมบัติข้อ 2. ถ้าให้ c = a และ d = b เราได้ a
2
≡
b
2
(mod n) ในกรณีทั่วไป เราสรุปได้ว่า a
k
≡
b
k
( mod n)
สำ
�หรับ k ที่เป็นจำ
�นวนเต็มบวกใด ๆ
ตัวอย่าง 3
เนื่องจาก 5
5
= 3125
≡
31 (mod 221) และจากสมบัติ
ข้อ 2. เราได้
(5
5
)
3
≡
31
3
(mod 221) แต่
31
3
= 29791
≡
177 (mod 221)
จากสมบัติข้อ 1. สรุปได้ว่า (5
5
)
3
≡
177 mod(221) จาก
สมบัติข้อ 2. เราได้
5
17
= (5
5
)
3
. 5
2
≡
177 . 25
≡
4425
≡
5 (mod 221)
ตัวอย่าง 4
จากสมบัติข้อ 1. และข้อ 2. เช่นกัน เราได้
114
5
≡
173 (mod 221) และ 114
55
= (114
5
)
11
≡
173
11
≡
75 (mod 221)
ในกรณีที่เลขชี้กำ
�ลังมีขนาดใหญ่มาก ๆ และใหญ่กว่า n ทฤษฎีบท
ของออยเลอร์มีประโยชน์ต่อการคำ
�นวณเป็นอย่างยิ่ง
ทฤษฎีบทของออยเลอร์ (Euler’s Theorem)
ถ้า gcd
(a, n) = 1 แล้ว a
φ
(n)
≡
1 (mod n)
ดังนั้น ถ้า p เป็นจำ
�นวนเฉพาะซึ่ง gcd (p, a) =1 แล้ว
a
p – 1
≡
1 (mod p) เพราะ
φ
(p) = p – 1
ตัวอย่าง 5
การคำ
�นวณค่า 2
43210
(mod 101) เราทำ
�ได้ดังนี้
เนื่องจาก gcd (101, 2) = 1 ดังนั้น 2
100
≡
1 (mod 101)
และ 2
43210
≡
(2
100
)
432
2
10
≡
1
432
2
10
≡
1024
≡
14 (mod 101)
– 27 . 7)
+ 54 . 7
– 2 . 192
– 2 . 192
2 . 3
2(192
2 . 192
54 . 7)
54) . 7
2 . 192
–
–
–
+
+
–
7
7
7
(7
(1
55 . 7
=
=
=
=
=
=
1