1.ง่าย
ใช้ขั้นตอนวิธีของยูคลิดเพื่อหา gcd(99, 51)
a = 99b = 51
gcd(99, 51) =
ใบงาน ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ พร้อมเฉลย
2.ง่าย
จงหาตัวคูณร่วมน้อย lcm(148, 60) ใช้ขั้นตอนวิธีของยูคลิดหา gcd ก่อน
a = 148b = 60
lcm(148, 60) =
3.ปานกลาง
จงหาฟังก์ชันโทเทียนต์ของออยเลอร์ φ(675) ซึ่งเป็นจำนวนของจำนวนเต็มตั้งแต่ 1 ถึง 675 ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ 675
n = 675 = 33·52
φ(675) =
4.ปานกลาง
จงหาตัวผกผันของ 30 มอดูโล 47: จำนวน x ที่ 0 < x < 47 และ 30·x ≡ 1 (mod 47)
a = 30n = 47
30−1 mod 47 =
5.ยาก
73 เป็นจำนวนเฉพาะ ใช้ทฤษฎีบทเล็กของแฟร์มาเพื่อหา 2662705 mod 73
p = 73k = 62705
2662705 mod 73 =
6.ยาก
89 เป็นจำนวนเฉพาะ ใช้ทฤษฎีบทเล็กของแฟร์มาเพื่อหา 1191933 mod 89
p = 89k = 91933
1191933 mod 89 =
เฉลย
- 1. gcd(99, 51) = 3
- 2. lcm(148, 60) = 2220
- 3. φ(675) = 360
- 4. 30−1 mod 47 = 11
- 5. 2662705 mod 73 = 29
- 6. 1191933 mod 89 = 73
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com