ท้ายสุดของปัญหาในข้อนี้จะขอนำทฤษฎีของระบบจำนวนมาแนะนำให้ใช้
เพื่อเกิดประโยชน์ในการคิดเลขให้เร็วขึ้น ดังนี้
ทฤษฎีบท 2
ถ้า $p$ เป็นจำนวนเฉพาะ และ $a$ เป็นจำนวนบวกที่ $p$ หาร $a$ ไม่ลงตัวแล้ว
$ a^{p- 1} \equiv 1 \pmod{p} $
ตัวอย่าง 13.
จงหาเศษเหลือจากการหาร $10^{100}$ ด้วย $17$
วิธีทำ
เพราะว่า
$10^{16} \equiv 1 \pmod{17 } $ และ $ \ \ 100 = 6(16) + 4 $
เพราะฉะนั้น
$10^{16} \equiv 1 \pmod{17} $
$(10^{16})^6 \equiv 1^6 \pmod{17} $
$10^{6(16)} \equiv 1 \pmod{17} $
$10^{6(16)+4} \equiv 10^4 \pmod{17} $
เพราะว่า
$10^2 \equiv 100 \pmod{17} \ \ \ \equiv 15 \pmod{17} $
$10^3 \equiv 150 \pmod{17} \ \ \ \equiv 14 \pmod{17} $
$10^4 \equiv 140 \pmod{17} \ \ \ \equiv 4 \pmod{17} $
เพราะฉะนั้น $10^{100}$ หารด้วย $17$ เหลือเศษ $4$
ตัวอย่าง 14.
จงหาเศษเหลือจากการหาร $2^{100!}$ ด้วย ${19}$
วิธีทำ
เพราะว่า $2^{18} \equiv 1 \pmod{19} \ $ และ $\frac{100!}{18} \ $ เป็นจำนวนเต็ม
เพราะฉะนั้น
$(2^{18})^{\frac{100!}{18}} \equiv 1 \pmod{19} $
$2^{100!} \equiv 1 \pmod{19} $
เพราะฉะนั้น $19$ หาร $2^{100!}$ เหลือเศษ $1$
__________________
มาหาความรู้ไว้ติวหลาน
แต่หลานไม่เอาเลขแล้ว
เข้ามาทำเลขเอามันอย่างเดียว
ความรู้เป็นสิ่งเดียวที่ยิ่งให้ ยิ่งมีมาก
รู้อะไรไม่สู้ รู้จักพอ
(ยกเว้นความรู้ ไม่ต้องพอก็ได้ หาไว้มากๆแหละดี)
(แต่ก็อย่าให้มากจนท่วมหัว เอาตัวไม่รอด)
|