1.ง่าย
ใช้ขั้นตอนวิธีของยูคลิดเพื่อหา gcd(1248, 648)
a = 1248b = 648
gcd(1248, 648) =
ใบงาน ทฤษฎีจำนวนและเลขคณิตมอดูลาร์ พร้อมเฉลย
2.ง่าย
จงหา (−95) mod 9 ซึ่งเป็นเศษ r ที่ 0 ≤ r < 9
a = −95n = 9
(−95) mod 9 =
3.ปานกลาง
จงหาฟังก์ชันโทเทียนต์ของออยเลอร์ φ(675) ซึ่งเป็นจำนวนของจำนวนเต็มตั้งแต่ 1 ถึง 675 ที่เป็นจำนวนเฉพาะสัมพัทธ์กับ 675
n = 675 = 33·52
φ(675) =
4.ปานกลาง
จงหาตัวผกผันของ 58 มอดูโล 65: จำนวน x ที่ 0 < x < 65 และ 58·x ≡ 1 (mod 65)
a = 58n = 65
58−1 mod 65 =
5.ยาก
จงแก้ 10x ≡ 6 (mod 24) ให้คำตอบที่เป็นบวกและน้อยที่สุด x
10x ≡ 6 (mod 24)
x =
6.ยาก
89 เป็นจำนวนเฉพาะ ใช้ทฤษฎีบทเล็กของแฟร์มาเพื่อหา 1955043 mod 89
p = 89k = 55043
1955043 mod 89 =
เฉลย
- 1. gcd(1248, 648) = 24
- 2. (−95) mod 9 = 4
- 3. φ(675) = 360
- 4. 58−1 mod 65 = 37
- 5. x = 3
- 6. 1955043 mod 89 = 14
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com