[warut]

555...ผมเป็นโรคบ้าจี้ซะด้วยเล่นชมกันอย่างงี้ผมเลยต้องทำต่ออีก...

ข้อ 13 เนี่ยตามความเห็นของผมคิดว่าผู้ออกข้อสอบต้องการวัดความรู้ 3 อย่างคือ

1. Fermat's Little Theorem
ถ้า p เป็นจำนวนเฉพาะและ a เป็นจำนวนเต็มที่ p หารไม่ลงตัวแล้ว a^p-1 บ 1 (mod p)
จะเห็นว่าทฤษฎีนี้เป็นกรณีพิเศษของ Euler_Fermat Theorem

2. Wilson's Theorem
p เป็นจำนวนเฉพาะก็ต่อเมื่อ (p - 1)! บ -1 (mod p)

3. Chinese Remainder Theorem
ถ้า gcd(m, n) = 1 แล้วระบบสมการ
x บ r (mod m)
x บ s (mod n)
จะมีคำตอบเพียงหนึ่งเดียวใน modulo mn

ให้ N = 29³⁰ + 31²⁸ + 28!30!
เนื่องจาก 29 | 29³⁰ และ 31²⁸ บ 1 (mod 29) โดย Fermat's Little Theorem และ 29 | 28!30!
ดังนั้น N บ 0 + 1 + 0 = 1 (mod 29)

ต่อไปเราจะหาว่า 28!30! บ ? (mod 31)
โดย Wilson's Theorem เรารู้ว่า 30! บ -1 (mod 31) ----- (*)
นั่นคือ -1 บ 30*29*28! บ (-1)(-2)28! = 2*28! (mod 31)
ดังนั้น 28! บ (-1)((31+1)/2) = -16 (mod 31) ----- (**)
จับ (*) คูณ (**) จะได้ 28!30! บ 16 (mod 31)
แต่เนื่องจาก 29³⁰ บ 1 (mod 31) โดย Fermat 's Little Theorem และ 31 | 31²⁸
ดังนั้น N บ 1 + 0 + 16 = 17 (mod 31)

สรุปว่าเราต้องแก้ระบบสมการ
N บ 1 (mod 29)
N บ 17 (mod 31)

นั่นคือ N = 31s + 17 โดยที่ s เป็นจำนวนเต็ม
ดังนั้น 31s + 17 บ 1 (mod 29)
เพราะฉะนั้น 31s บ 2s บ -16 (mod 29)
สรุปได้ว่า s บ -8 บ 21 (mod 29)
นั่นคือ s = 29t + 21 โดยที่ t เป็นจำนวนเต็ม
ดังนั้น N = 31(29t + 21) + 17 = 31*29t + 31*21 + 17 = 31*29t + 668
สรุปได้ว่าคำตอบที่ต้องการคือ 668 ครับผม