Upload
others
View
48
Download
0
Embed Size (px)
Citation preview
บทที่ 6
รากปฐมฐานและดรรชนี (Primitive root and index)
ใบบทที่ 3 เราพิจารณาหาผลเฉลยของสมภาคเชิงเส้น ในบทนี้เราจะพิจารณาหา
ผลเฉลยของสมภาคที่อยู่ในรูป xr a mod m เรียก r ว่ารากปฐมฐาน (primitive
root) มอดุโล m และเรียก x ว่าดรรชนี (Index) โดยเราจะเริ่มต้นด้วยการศึกษาอันดับ
ของจ านวนเต็มและศึกษาทฤษฎีบทเกี่ยวกับอันดับของจ านวนเต็ม จากนั้นจะกล่าวถึงสมบัติ
ของรากปฐมฐานมอดุโล m และศึกษาทฤษฎีบทของดรรชนีเพ่ือที่จะน าไปใช้หาผลเฉลย
ของสมภาค ได้สะดวกและรวดเร็วยิ่งขึ้น
6.1 อันดับของจ านวนเต็มมอดุโล m
ในบทที่ 3 หัวข้อ 3.7 ได้กล่าวถึงทฤษฎีบท 3.7.2 ทฤษฎีบทของออยเลอร์
แล้วว่า m เป็นจ านวนเต็มบวก และ a เป็นจ านวนเต็ม ซึ่ง a,m 1 จะได้ว่า m
a 1 modm
ดังนั้นได้ว่าจะมีจ านวนเต็ม k มีค่าน้อยสุด ที่ ka 1 modm
ดังบทนิยามต่อไปนี้ (จรินทร์ทิพย์ เฮงคราวิทย์, 2558, น. 170; จิราภา ลิ้มบุพศิริพร,
2555, น. 140; Raji, W., 2013, p. 91; Rosen, K. H., 2005, p. 334)
บทนิยาม 6.1.1
ให้ a และ m เป็นจ านวนเต็มบวก โดยที่ m 1 และ a,m 1 เรียกจ านวนเต็ม
บวก k ที่มีค่าน้อยสุด ที่ ka 1 modm ว่า อันดับของ a มอดุโล m (the
order of a modulo m ) เขียนแทนด้วย mord a k
174 ทฤษฎีจ านวน
ตัวอย่าง 6.1.1 จงหาอันดับของ 2 มอดุโล 7
วิธีท า เนื่องจาก 12 2 mod7
2
3
2 4 mod7
2 1 mod7
42 2 mod7
5
6
2 4 mod7
2 1 mod7
จะเห็นว่า 3 เป็นจ านวนเต็มบวกค่าน้อยสุด ที่ท าให้ 32 1 mod7
นั่นคือ อันดับของ 2 มอดุโล 7 คือ 3 หรือ 7ord 2 3
การใช้ Wolfram Alpha เพ่ือหาอันดับของ 2 มอดุโล 7 ดังภาพที่ 6.1.1
ผลลัพธ์ 3
ภาพที่ 6.1.1 อันดับของ 2 มอดุโล 7 คือ 3
ตัวอย่าง 6.1.1 เราได้ k2 1 mod7 เมื่อ k เป็นพหุคูณของ 3 โดยที่ 3
เป็นอันดับของ 2 มอดุโล 7 เป็นกรณีตัวอย่าง กรณีทั่วไปจะกล่าวดังทฤษฎีบทต่อไปนี้ (จิราภา ลิ้มบุพศิริพร, 2555, น. 140; สมใจ จิตพิทักษ์, 2547, น. 176; Raji, W., 2013,
p. 90)
ทฤษฎีบท 6.1.1
ก าหนดให้ a เป็นจ านวนเต็ม ที่ a,m 1 และ k เป็นอันดับของ a มอดุโล m
ส าหรับทุกจ านวนเต็มบวก h จะได้ว่า ha 1 modm ก็ต่อเมื่อ k h
order of 2 mod 7
บทที่ 6 รากปฐมฐานและดรรชนี 175
บทพิสูจน์
สมมติให้ h เป็นอันดับของ a มอดุโล m ที่ ha 1 modm
โดยขั้นตอนวิธีการหารจะมีจ านวนเต็ม q และ r
โดยที่ h qk r, 0 r k
ดังนั้น kq
rqk rha a a a
จากสมมติ ha 1 modm และ ka 1 modm
จะได้ว่า ra 1 modm เนื่องจาก 0 r k
จะได้ว่า r 0 ดังนั้น h qk
นั่นคือ k h
สมมติให้ k h จะมีจ านวนเต็ม j ที่ท าให้ h kj
เนื่องจาก ka 1 modm
ดังนั้น j
jka 1 modm
นั่นคือ ha 1 modm
บทแทรกที่ได้จากทฤษฎีบท 6.1.1 ดังต่อไปนี้ (จิราภา ลิ้มบุพศิริพร , 2555, น. 141; สมใจ จิตพิทักษ์, 2547, น. 176; อัจฉรา หาญชูวงศ์, 2542, น. 71; Rosen, K. H.,
2005, p. 335)
บทแทรก 6.1.1
ถ้า mord a k แล้ว k m
บทพิสูจน์
โดยทฤษฎีบทของออยเลอร์ m
a 1 modm
และจากทฤษฎีบท 6.1.1
จะได้ k m
176 ทฤษฎีจ านวน
ตัวอย่าง 6.1.2 จงหาอันดับของ 2 มอดุโล 13
วิธีท า เนื่องจาก 13 12
ดังนั้นเราจะพิจารณาจ านวนเต็มบวก k ที่ เป็นไปได้ทั้งหมดซึ่ง k 12
นั่นคือ k 1,2,3,4,6 และ 12 ขั้นตอนการค านวณอาจเป็นได้ดังนี้
12 2 mod13
2
3
2 4 mod3
2 8 mod13
42 3 mod13
6
12
2 4 3 12 mod13
2 4 8 3 96 1 mod13
ดังนั้นจ านวนเต็มบวก k ค่าน้อยสุด ซึ่ง k 13 และ ka 1 mod13
คือ k 12
นั่นคือ อันดับของ 2 มอดุโล 13 คือ 12 หรือ 13ord 2 12
การใช้ Wolfram Alpha เพ่ือหาอันดับของ 2 มอดุโล 13 ดังภาพที่ 6.1.2
ผลลัพธ์ 3
ภาพที่ 6.1.2 อันดับของ 2 มอดุโล 13 คือ 12
ทฤษฎีบทต่อไปนี้เป็นทฤษฎีเบื้องต้นเกี่ยวกับอันดับของจ านวนเต็มอีกทฤษฎีหนึ่ง (จิราภา ลิ้มบุพศิริพร, 2555, น. 142; สมใจ จิตพิทักษ์, 2547, น. 177; Raji, W., 2013,
pp. 90-91)
order of 2 mod 13
บทที่ 6 รากปฐมฐานและดรรชนี 177
ทฤษฎีบท 6.1.2
ถ้า mord a k จะได้ว่า tsa a modm ก็ต่อเมื่อ r s modk
บทพิสูจน์
สมมติให้ tsa a modm ซ่ึง a,m 1 และให้ ts
โดยทฤษฎีบท 6.1.1 จะได้ k ts
นั่นคือ s t modk
สมมติให้ s t modk โดยบทนิยาม 3.1.1 จะได้ k ts
จะได้ว่ามีจ านวนเต็ม q ที่ท าให้ s t qk
ดังนั้น t qk t qksa a a a
แต ่k เป็นอันดับของ a มอดุโล m
ดังนั้น ka 1 modm
qka 1 modm
qkt ta a a modm
นั่นคือ tsa a modm
บทแทรกที่ได้จากทฤษฎีบท 6.1.2 ดังต่อไปนี้ (จิราภา ลิ้มบุพศิริพร, 2555, น.
142; สมใจ จิตพิทักษ์, 2547, น. 177; Burton, D. M., 2007, p. 149)
บทแทรก 6.1.2
ถ้า mord a k จะได้ว่า 2 ka,a , ,a จะไม่สมภาคมอดุโล m กัน
บทพิสูจน์
ถ้ามี s และ t ซ่ึง 1 s t k ซ่ึง tsa a modm
โดยทฤษฎีบท 6.1.2 จะได้ว่า s t modk
แต่ในกรณีนี้จะเกิดข้ึนไม่ได้นอกเสียจากว่า s t
178 ทฤษฎีจ านวน
ทฤษฎีบทต่อไปนี้จะกล่าวเกี่ยวกับอันดับของ a ก าลัง (power of a) ดังต่อไปนี้ (จรินทร์ทิพย์ เฮงคราวิทย์, 2558, น. 174; จิราภา ลิ้มบุพศิริพร, 2555, น. 142; สมวงษ์
แปลงประสพโชค, 2545, น. 145; Burton, D. M., 2007, p. 149)
ทฤษฎีบท 6.1.3
ถ้า mord a k และ h 0 จะได้ว่า h
m
kord a
h,k
บทพิสูจน์
ให้ d h,k จะได้ว่า 1h h ,d และ 1
k k ,d เมื่อ 1 1h ,k 1
จะได้ว่า 1
1 1
kk h d khh da a a 1 modm
สมมตวิ่า h
mord a r จากทฤษฎีบท 6.1.1 จะได้ 1
r k
และ hr
a 1 modm แต่ mord a k ดังนั้น k hr
จะได้ 1 1
k d h dr ดังนั้น 1 1
k h r แต่ 1 1h ,k 1 ดังนั้น
1k r
เมื่อ 1
k r และ 1
r k ดังนั้น 1
k kr k
d h,k
บทแทรกต่อไปนี้เป็นผลโดยตรงจากทฤษฎีบท 6.1.3 (จรินทร์ทิพย์ เฮงคราวิทย์, 2558, น. 174; สมใจ จิตพิทักษ์, 2547, น. 177; Burton, D. M., 2007, p. 149)
บทแทรก 6.1.3
ถ้า mord a k และถ้า h,k 1 จะได้ว่า h
mord a k
บทพิสูจน์
จากทฤษฎีบท 6.1.3 ถ้า mord a k จะได้ว่า h
m
kord a
h,k
ถ้า h,k 1 จะได้ว่า h
mord a k
บทที่ 6 รากปฐมฐานและดรรชนี 179
ตัวอย่าง 6.1.3 จงหาอันดับของ 2 3 4 5 65,5 ,5 ,5 ,5 ,5 มอดุโล 7
วิธีท า ขั้นตอนการค านวณอาจเป็นได้ดังนี้
15 5 mod7
25 4 mod7
35 5 4 20 6 mod7
45 4 4 16 2 mod7
5
6
5 2 5 10 3 mod7
5 5 3 15 1 mod7
เพราะฉะนั้น ทราบอันดับของทุกตัว ดังนี้
7
6ord 5 6
1,6 ,
2
7
6ord 5 3
2,6
3
7
6ord 5 2
3,6 ,
4
7
6ord 5 3
4,6
5
7
6ord 5 6
5,6 ,
6
7
6ord 5 1
6,6
ตัวอย่าง 6.1.4 จงหาอันดับมอดุโล 13 ของจ านวนเต็มบวกที่น้อยกว่า 13
วิธีท า ให้ n 1,2,3,4,5,6,7,8,9,10,11,12 หาอันดับมอดุโล 13 ดังตารางที่ 6.1.1
ตารางท่ี 6.1.1 อันดับมอดุโล 13 ของจ านวนเต็มบวกท่ีน้อยกว่า 13
n 1 2 3 4 5 6 7 8 9 10 11 12
13ord n 1 12 3 6 4 12 12 4 3 6 12 2
จากตารางที่ 6.1.1 จะเห็นว่า 13
ord 2 12
ในขณะเดียวกัน 2
13ord 2 6 และ 3
13ord 2 4
โดยทฤษฎีบท 6.1.3 สามารถตรวจสอบจ านวนเต็มอ่ืน ๆ
180 ทฤษฎีจ านวน
ซึ่งมีอันดับ 12 มอดุโล 13 คือ k2 ซ่ึง k,12 1 ได้แก่
52 6 mod13
72 11 mod13
112 7 mod13
ซ่ึง 5,7 และ 11 เป็นจ านวนเฉพาะสัมพัทธ์กับ 12
ถ้าจ านวนเต็ม a มีอันดับสูงสุดเท่าที่เป็นไปได้ เราจะเรียก a ว่า รากปฐมฐานของ m (primitive root of m ) ดังบทนิยามต่อไปนี้ (จรินทร์ทิพย์ เฮงคราวิทย์, 2558, น.
175; สมใจ จิตพิทักษ์ , 2547, น. 178; สมวงษ์ แปลงประสพโชค , 2545, น. 146;
Burton, D. M., 2007, p. 150)
บทนิยาม 6.1.2
ถ้า a,m 1 และ mord a m จะเรียก a ว่ารากปฐมฐานของ m
(primitive root of m ) กล่าวอีกอย่างหนึ่งว่า m มีรากปฐมฐานเป็น a ก็ต่อเมื่อ m
a 1 modm
แต่ ka 1 modm ส าหรับจ านวนเต็มบวก k ซ่ึง
k m
ตัวอย่าง 6.1.5 จงตรวจสอบว่า 2 และ 3 เป็นรากปฐมฐานของ 7 หรือไม่
วิธีท า 7 6 ให้ a 2 และ 3 ขั้นตอนค านวณดังนี้
a 2 a 3
1
2
3
4
5
6
2 2 mod7
2 4 mod7
2 1 mod7
2 2 mod7
2 4 mod7
2 1 mod7
1
2
3
4
5
6
3 3 mod7
3 2 mod7
3 6 mod7
3 4 mod7
3 5 mod7
3 1 mod7
นั่นคือ 3 เป็นรากปฐมฐานของ 7 แต่ 2 ไม่เป็นรากปฐมฐานของ 7
บทที่ 6 รากปฐมฐานและดรรชนี 181
การใช้ Wolfram Alpha เพ่ือหารากปฐมฐานของ 7 ดังภาพที่ 6.1.3
ผลลัพธ์ 3
ภาพที่ 6.1.3 รากปฐมฐานของ 7 คือ 3
ตัวอย่าง 6.1.6 จงตรวจสอบว่า 3 และ 7 เป็นรากปฐมฐานของ 10 หรือไม่
วิธีท า 1 1
10 2 5 10 1 1 42 5
ตรวจสอบ k3 และ k7 เมื่อ k 4 ดังนี้
1
2
3
4
3 3 mod10
3 9 mod10
3 7 mod10
3 1 mod10
1
2
3
4
7 7 mod10
7 9 mod10
7 3 mod10
7 1 mod10
จะเห็นว่าเมื่อ k 4 ได้ว่า k3 1 mod10 และ k7 1 mod10
แต่ 43 1 mod10 และ 47 1 mod10
นั่นคือ 3 และ 7 เป็นรากปฐมฐานของ 10
การใช้ Wolfram Alpha เพ่ือตรวจสอบว่า 3 และ 7 เป็นรากปฐมฐานของ
10 ดังภาพที่ 6.1.4 และ ดังภาพที่ 6.1.5
PrimitiveRoot 7
182 ทฤษฎีจ านวน
ผลลัพธ์ 3
ภาพที่ 6.1.4 3 เป็นรากปฐมฐานของ 10
ผลลัพธ์ 7
ภาพที่ 6.1.5 7 เป็นรากปฐมฐานของ 10
ตัวอย่าง 6.1.5 และ ตัวอย่าง 6.1.6 จะเห็นว่ารากปฐมฐานของ 7 และ 10 มี
มากกว่า 1 ตัว แต่จ านวนเต็มทุกจ านวนไม่จ าเป็นต้องมีรากปฐมฐานส่วนส าหรับจ านวน
เฉพาะเราจะพิสูจน์ต่อไปว่ามีรากปฐมฐานเสมอ ดังทฤษฎีบทต่อไปนี้ (จรินทร์ทิพย์ เฮงครา
วิทย์, 2558, น. 175; สมใจ จิตพิทักษ์, 2547, น. 176; สมวงษ์ แปลงประสพโชค, 2545,
น. 147; Burton, D. M., 2007, pp. 150-151)
ทฤษฎีบท 6.1.4
ถ้า a เป็นรากปฐมฐานของ m จะได้ว่า 1 2 ma ,a , ,a
จะเป็นระบบส่วนตกค้างลดรูปมอดุโล m
บทพิสูจน์
เนื่องจาก a เป็นรากปฐมฐาน จะได้ว่า a,m 1
ดังนั้น 1 2 ma ,a , ,a
เป็นจ านวนเฉพาะสัมพัทธ์กับ m
PrimitiveRoot [10,7]
PrimitiveRoot [10,3]
บทที่ 6 รากปฐมฐานและดรรชนี 183
และเนื่องจาก a เป็นรากปฐมฐาน ดังนั้น mord a m
โดยบทนิยาม 6.1.2 จะได้ว่า m
a 1 modm
แต่ ka 1 modm
ส าหรับจ านวนเต็มบวก k ซ่ึง k m จากบทแทรก 6.1.2
จะได้ว่า 1 2 ka ,a , ,a ไม่สมภาคมอดุโล m กัน
นั่นคือ 1 2 ma ,a , ,a
จะเป็นระบบส่วนตกค้างลดรูปมอดุโล m
จากทฤษฎีบท 6.1.4 1 2 ma ,a , ,a
จะเป็นระบบส่วนตกค้างลดรูปมอดุโล
m ดังนั้นสมาชิกแต่ละตัวจึงไม่สมภาคกับ 1 2 ma ,a , ,a
มอดุโล m เป็นคู่ ๆ แบบหนึ่ง
ต่อหนึ่งโดยที่ i
1 a m ในกรณีที่รากปฐมฐานหาได้ เราจะได้จากบทแทรกต่อไปนี้
(จรินทร์ทิพย์ เฮงคราวิทย์, 2558, น. 177; สมใจ จิตพิทักษ์, 2547, น. 179; Burton,
D. M., 2007, p. 151)
บทแทรก 6.1.4
ถ้า m มีรากปฐมฐานแล้ว m จะมีรากปฐมฐานอยู่ m จ านวน
บทพิสูจน์
สมมติให้ a เป็นรากปฐมฐานหนึ่งของ m
ดังนั้น mord a m พิจารณา 1 2 ma ,a , ,a
ซึ่งเป็นระบบส่วนตกค้างลด
รูปมอดุโล m โดยทฤษฎีบท 6.1.4 จะหารากปฐมฐานตัวอ่ืนได้
จากสมาชิกของเซต 1 2 ma ,a , ,a
โดยหา mord a แต่ละตัว
จากทฤษฎีบท 6.1.3 ดังนี้
2
m
mord a
2, m
3
m
mord a
3, m
184 ทฤษฎีจ านวน
m
m
mord a
3, m
ดังนั้น k
mord a m ก็ต่อเมื่อ k, m 1
แต่จ านวน k ที่น้อยกว่า m ซ่ึง k, m 1
มี m จ านวน
นั่นคือ m มีรากปฐมฐานทั้งหมด m จ านวน
ตัวอย่าง 6.1.7 จงหารากปฐมฐานของ 9
วิธีท า 2 29 3 3 3 6
9 6 2 3 2
นั่นคือรากปฐมฐานของ 9 มี 2 จ านวน
6.2 ทฤษฎีบทของดรรชนี
ในหัวข้อนี้จะศึกษาวิธีการใช้รากปฐมฐานกับสมภาค ถ้า r เป็นรากปฐมฐานมอดุโล
m โดยทฤษฎีบท 6.1.4 จะได้ว่าจ านวนเต็ม 2 3 mr, r , r , , r
เป็นระบบส่วนตกค้างลด
รูปมอดุโล m ดังนั้น ถ้า a เป็นจ านวนเต็มที่เป็นจ านวนเฉพาะสัมพัทธ์กับ m จะได้ว่ามี
จ านวนเต็ม x เพียงจ านวนเดียว ซึ่ง 1 x m เขียนในรูปดังนี้
xr a modm
ดังจะกล่าวบทนิยามต่อไปนี้ (จรินทร์ทิพย์ เฮงคราวิทย์, 2558, น. 196; Burton,
D. M., 2007, p. 163)
บทนิยาม 6.2.1
ก าหนดให้ r เป็นรากปฐมฐานของ m ถ้า a,m 1 จะได้ว่ามีจ านวนเต็ม x ที่มี
ค่าบวกน้อยสุด ที่ท าให้ xr a modm แล้วจะเรียก x ว่า ดรรชนี (Index) ของ
a เทียบกับฐาน r ซ่ึง 1 x m เขียนแทนด้วย rx ind a
บทที่ 6 รากปฐมฐานและดรรชนี 185
ตัวอย่าง 6.2.1 ก าหนดให้ 2 เป็นรากปฐมฐานมอดุโล 5 และ
12 2 mod5
22 4 mod5
32 3 mod5
42 1 mod5
จึงได้ดรรชนีมอดุโล 5 เทียบกับฐาน 2
นั่นคือ 2 2 2ind 1 4, ind 2 1, ind 3 3 และ 2ind 4 2
ทฤษฎีต่อไปนี้กล่าวถึงสมบัติที่ส าคัญของดรรชนีท านองเดียวกับลอการิทึม
ดังทฤษฎีบทต่อไปนี้ (จรินทร์ทิพย์ เฮงคราวิทย์, 2558, น. 197; จิราภา ลิ้มบุพศิริพร ,
2555, น. 169; Burton, D. M., 2007, p. 164)
ทฤษฎีบท 6.2.1
ถ้า m เป็นจ านวนเต็มบวกซ่ึงมี r เป็นรากปฐมฐาน ให้ a และ b เป็นจ านวนเต็ม โดยที่ a,m 1 และ b,m 1 จะได้ว่า
1 rind 1 0 mod m และ rind r 1 mod m
2 r r rind ab ind a ind b mod m
3 k
r rind a k ind a mod m เมื่อ k เป็นจ านวนเต็มบวก
บทพิสูจน์
1 เนื่องจาก 0ind 1rr 1 r modm และ 1indrrr r r modm
โดยทฤษฎีบท 6.1.2 จะได้ว่า
1ind r 0 mod m และ rind r 1 mod m
2 จาก indrar a modm และ indrbr b modm
โดยทฤษฎีบท 3.1.4 ข้อ 2.3 จะได้ว่า
ind ind ind indr r r ra b a br r r ab modm
186 ทฤษฎีจ านวน
โดยทฤษฎีบท 6.1.2 จะได้ว่า
r r rind ab ind a ind b mod m
3 ก าหนดให้ k เป็นจ านวนเต็มบวก จาก indrar a modm
โดยทฤษฎีบท 3.1.4 ข้อ 1.5 จะได้ว่า
k
a kk ind indr rar r a modm
เนื่องจาก k
kind arr a modm
เพราะฉะนั้น k
rind a k ind arr r modm
โดยทฤษฎีบท 6.1.2 จะได้ว่า
k
r rind a k ind a mod m เมื่อ k เป็นจ านวนเต็มบวก
ตัวอย่าง 6.2.2 ก าหนดให้ m 7 และ r 5 เป็นรากปฐมฐานมอดุโล 7 ถ้า
5ind 2 4 และ
5ind 3 5 แล้วจงหา
5ind 6 และ
5ind 81
วิธีท า เนื่องจาก 7 6 ขั้นตอนการค านวณจะได้
1 2 3
4 5 6
5 5 mod7 5 4 mod7 5 6 mod7
5 2 mod7 5 3 mod7 5 1 mod7
แสดงดรรชนีของจ านวนเต็มเมื่อเทียบกับรากปฐมฐาน 5 มอดุโล 7
ดังตารางที่ 6.2.1
ตารางท่ี 6.2.1 ดรรชนีของจ านวนเต็มเมื่อเทียบกับรากปฐมฐาน 5 มอดุโล 7
a 1 2 3 4 5 6
5ind a 6 4 5 2 1 3
โดยทฤษฎีบท 6.2.1 ข้อ 2 และ 3 จะได้
5 5 5 5ind 6 ind 2 3 ind 2 ind 3 4 5 9 3 mod6 และ
4
5 5 5ind 81 ind 3 4 ind 3 4 5 20 2 mod6
นั่นคือ 5
ind 6 3 และ 5
ind 81 2
บทที่ 6 รากปฐมฐานและดรรชนี 187
จากตาราง 6.2.1 สามารถหาส่วนตกค้างน้อยสุดได้ดังตาราง 6.2.2
ตารางท่ี 6.2.2 ส่วนตกค้างน้อยสุดเมื่อเทียบกับรากปฐมฐาน 5 มอดุโล 7
a 1 2 3 4 5 6
5ind a 6 4 5 2 1 3
5ind a5 5 4 6 2 3 1
โดยบรรทัดที่ 3 เป็นส่วนตกค้างน้อยสุดและจะเห็นว่า
5ind 2 42 5 5 mod7 และ 5ind 6 36 5 5 mod7
ทฤษฎีบทของดรรชนีสามารถใช้หาผลเฉลยของสมภาคบางชนิดได้ เช่นสมภาคเชิง
พหุนาม พิจารณา
kx a modm 6.2.1
โดยที่ m เป็นจ านวนเต็มบวกท่ีมีรากปฐมฐานและ a.m 1 และ k 2 โดยทฤษฎี
บท 6.2.1 ข้อ 2 และ ข้อ 3 จึงได้ว่าสมภาค 6.2.1 สมมูลกับสมภาคเชิงเส้น
k indx inda mod m 6.2.2
เมื่อสมภาค 6.2.2 เป็นสมภาคเชิงเส้นที่มีตัวไม่ทราบค่าหรือตัวแปร
ถ้า d k, m และ d | inda จะได้ว่าสมภาค 6.2.2 ไม่มีผลเฉลย
ถ้า d inda จะได้ว่า 6.2.2 มีผลเฉลย ของ indx มีจ านวน d ผลเฉลยมอดุโล m
ท าให้ตัวแปร x ในสมภาค 6.2.1 มีผลเฉลย d ผลเฉลยมอดุโล m ด้วย
ตัวอย่าง 6.2.3 จงหาผลเฉลยของ 42x 5 mod13 เมื่อก าหนดให้ r 2 เป็นราก
ปฐมฐานมอดุโล 13
วิธีท า เนื่องจาก 13 12 ก าหนดดังตารางที่ 6.2.3 ดังนี้
188 ทฤษฎีจ านวน
ตารางท่ี 6.2.3 ดรรชนีของจ านวนเต็มเมื่อเทียบกับฐาน 2 มอดุโล 12
a 1 2 3 4 5 6 7 8 9 10 11 12
2ind a 12 1 4 2 9 5 11 3 8 10 7 6
2ind a2 2 4 8 3 6 12 11 9 5 10 7 1
2 2 2ind 2 4ind x ind 5 mod12 โดยทฤษฎีบท 6.2.1 ข้อ 2
21 4ind x 9 mod12 โดยทฤษฎีบท 6.2.1 ข้อ 1
2
4ind x 9 1 8 mod12
ซึ่งสมมูลกับ 2
12ind x 2 mod 3
4,12
จึงได้ว่า 2ind x 2,5,8,11 mod12 จากบทนิยาม 6.1.1
จะได้ว่า 2 5 8 11x 2 ,2 ,2 ,2 mod13 จากตารางที่ 6.2.3
จะได้ 2 2 2
ind 4 2, ind 6 5, ind 9 8
และ 2
ind 7 11
ดรรชนีจึงได้ว่าสมภาค 42x 5 mod13 มีผลเฉลยดังนี้
x 4,6,9,7 mod13
นั่นคือ ผลเฉลยของ 42x 5 mod13 คือ x 4,6,9,7 mod13
เราสร้างตารางดรรชีนีของรากปฐมฐานมอดุโล m ซ่ึง m ไม่จ าเป็นต้องเป็น
จ านวนเฉพาะ ในการหาผลเฉลยของสมภาคโดยอาศัยส่วนตกค้างน้อยสุด ดังตัวอย่าง
ต่อไปนี้
ตัวอย่าง 6.2.4 จงหาผลเฉลยของ 84x 25 mod27 เมื่อก าหนดให้ r 2 เป็นราก
ปฐมฐานมอดุโล 27
วิธีท า เนื่องจาก 3 3 227 3 3 3 18 ก าหนดดังตารางที่ 6.2.4 ดังนี้
บทที่ 6 รากปฐมฐานและดรรชนี 189
ตารางท่ี 6.2.4 ดรรชนีของจ านวนเต็มเมื่อเทียบกับฐาน 2 มอดุโล 18
a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 2ind a2 2 4 8 16 5 10 20 13 26 25 23 19 11 22 17 7 14 1
2 2 2ind 4 8ind x ind 25 mod18 โดยทฤษฎีบท 6.2.1 ข้อ 2
22 8ind x 10 mod18 โดยทฤษฎีบท 6.2.1 ข้อ 1
2
8ind x 8 mod18
ซึ่งสมมูลกับ 2
18ind x 1 mod 9
8,18
จึงได้ว่า 2ind x 1,10 mod18 จากบทนิยาม 6.1.1
จะได้ว่า 1 10x 2 ,2 mod27 จากตารางที่ 6.2.4
จะได้ 2
ind 2 1 และ 2
ind 25 10
ดรรชนีจึงได้ว่า 42x 5 mod13 มีผลเฉลยดังนี้
x 2,25 mod27
นั่นคือ ผลเฉลยของ 84x 25 mod27 คือ x 2,25 mod27
ทฤษฎีบทต่อไปนี้จะช่วยในการตรวจสอบว่าสมภาคมีผลเฉลยหรือไม่ (Burton,
D. M., 2007, p. 166)
ทฤษฎีบท 6.2.2
ให้ m เป็นจ านวนเต็มบวกท่ีมีรากปฐมฐาน ถ้า k เป็นจ านวนเต็มบวกและ a เป็นจ านวนเต็มโดยที่ a,m 1 จะได้ว่า kx a modm มีผลเฉลยก็ต่อเมื่อ
m
da 1 modm
เมือ่ d m, m และถ้าสมภาค kx a modm มี
ผลเฉลยแล้ว จะมีจ านวนผลเฉลยเท่ากับ d ผลเฉลย
190 ทฤษฎีจ านวน
บทพิสูจน์
ให้ r เป็นรากปฐมฐานมอดุโล m จากทฤษฎีบท 6.2.1 ข้อ 3
จะได้ว่า สมภาค k indx inda mod m ซึ่งมีตัวไม่ทราบค่า
คือ indx ดังนั้นโดยวิธีการหาผลเฉลยของสมภาคเชิงเส้น จะหาผลเฉลยได้
ก็ต่อเมื่อ d inda เมื่อ d m, m และจะมีผลเฉลยที่แตกต่างกัน
d ผลเฉลย ดังนั้นสรุปได้ว่า kx a modm จะมีผลเฉลยก็ต่อเมื่อ
d inda และถ้ามีผลเฉลยแล้วจะมี d ผลเฉลย
พิจารณา
m
da 1 modm
เมื่อ d m, m
จากทฤษฎีบท 6.2.1 ข้อ 1 สมภาคนี้จะสมมูลกับ
m
inda 0 mod md
สมภาคนี้จะเป็นจริงก็ต่อเมื่อ d inda
นั่นคือ
m
da 1 modm
ก็ต่อเมื่อ d inda
ตัวอย่าง 6.2.5 จากตัวอย่าง 6.2.4 จงหาผลเฉลยของ 84x 25 mod27 มีผลเฉลย
หรือไม่ และถ้ามีจะมีก่ีผลเฉลย
วิธีท า 3 3 227 3 3 3 18 ดังนั้น m ,n 18,8 2
นั่นคือมีผลเฉลย 2 ผลเฉลย
ในบทที่ 6 ได้กล่าวถึงการหาผลเฉลยของสมภาค ที่อยู่ในรูป xr a modm
เรียก r ว่ารากปฐมฐานและเรียก x ว่า ดรรชนี โดยเริ่มต้นจากการหาอันดับของ r
มอดุโล m และอาศัยรากปฐมฐาน r ในการหาดรรชนีที่มีสมบัติส าคัญเดียวกันกับ
ลอการิทึมและในบทที่ 7 ศึกษาเก่ียวกับการหาผลเฉลยของสมภาคก าลังสองต่อไป
บทที่ 6 รากปฐมฐานและดรรชนี 191
แบบฝึกหัดบทท่ี 6
1. จงหาอันดับของจ านวนเต็ม 2,3 และ 5 1.1 มอดุโล 17 1.2 มอดุโล 19 1.2 มอดุโล 23
2. จงพิสูจน์ข้อความต่อไปนี้ 2.1 ถ้า
mord a hk แล้ว h
mord a k
2.2 ถ้า p เป็นจ านวนเฉพาะคี่และp
ord a 2k แล้ว ka 1 modp
2.3 ถ้า m
ord a m 1 แล้ว n เป็นจ านวนเฉพาะ 3. ให้
mord a h และ
mord b k จงแสดงว่า
mord ab hk และ ถ้า
h,k 1 แล้ว m
ord ab hk
4. จงแสดงว่า 2 เป็นรากปฐมฐานของ 19 แต่ไม่เป็นรากปฐมฐานของ 17 5. จงหารากปฐมฐานของ 11,13 และ 19 6. จงแสดงว่า 15 ไม่มีรากปฐมฐาน
7. ถ้า a เป็นรากปฐมฐานของจ านวนเต็ม m จงพิสูจน์ว่าถ้า ka เป็นรากปฐมฐาน
ของ m ก็ต่อเมื่อ k, m 1
8. จงหาดรรชนีของ 5 เทียบกับแต่ละฐานที่เป็นรากปฐมฐานของ 13 9. ตารางต่อไปนี้แสดงดรรชนีของ a เทียบกับฐาน 3 ซึ่งเป็นรากปฐมฐานของ 17
a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3ind a 16
14
1 12 5 15 11 10 2 3 7 13 4 9 6 8
จงใช้ตารางดรรชนีดังกล่าวหาผลเฉลยของสมภาคต่อไปนี้ 9.1 2x 13 mod17
9.2 28x 10 mod17
9.3 29x 8 mod17
192 ทฤษฎีจ านวน
10. จงหาดรรชนีของ a เทียบกับฐาน 2 ซึ่งเป็นรากปฐมฐานของ 11 แล้วเขียนลงในตาราง
a 1 2 3 4 5 6 7 8 9 10
2ind a
11. จงตรวจสอบว่าสมภาคต่อไปนี้ มีผลเฉลยหรือไม่ ถ้ามีมีกี่ผลเฉลย 11.1 37x 3 mod11
11.2 43x 8 mod11
11.3 8x 10 mod11
12. ถ้า p เป็นจ านวนเฉพาะคี่แล้ว จงพิสูจน์ว่า 12.1 2x 1 modp มีผลเฉลยก็ต่อเมื่อ p 1 mod4
12.2 4x 1 modp มีผลเฉลยก็ต่อเมื่อ p 1 mod8
13. ถ้า r เป็นรากปฐมฐานของจ านวนเฉพาะคี่ p จงแสดงว่า
r r
1ind 1 ind p 1 p 1
2