20
บทที6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที3 เราพิจารณาหาผลเฉลยของสมภาคเชิงเส้น ในบทนี้เราจะพิจารณาหา ผลเฉลยของสมภาคที่อยู่ในรูป x r 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 mod m ดังนั้นได้ว่าจะมีจานวนเต็ม k มีค่าน้อยสุด ที k a 1 mod m ดังบทนิยามต่อไปนี(จรินทร์ทิพย์ เฮงคราวิทย์ , 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 ที่มีค่าน้อยสุด ที k a 1 mod m ว่า อันดับของ a มอดุโล m (the order of a modulo m ) เขียนแทนด้วย m ord a k

¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

  • Upload
    others

  • View
    48

  • Download
    0

Embed Size (px)

Citation preview

Page 1: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

บทที่ 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

Page 2: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

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

Page 3: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

บทที่ 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

Page 4: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

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

Page 5: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

บทที่ 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

Page 6: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

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

Page 7: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

บทที่ 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 สามารถตรวจสอบจ านวนเต็มอ่ืน ๆ

Page 8: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 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

Page 9: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

บทที่ 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

Page 10: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

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]

Page 11: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 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

Page 12: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

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

Page 13: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

บทที่ 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

Page 14: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

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

Page 15: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

บทที่ 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 ดังนี้

Page 16: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 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 ดังนี้

Page 17: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

บทที่ 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 ผลเฉลย

Page 18: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

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 ศึกษาเก่ียวกับการหาผลเฉลยของสมภาคก าลังสองต่อไป

Page 19: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

บทที่ 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

Page 20: ¸šทที่ 6.pdfบทที่ 6 รากปฐมฐานและดรรชนี (Primitive root and index) ใบบทที่ . 3 เราพิจารณาหาผลเฉล

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