congruence problems

[tatari/nightmare]

1.จงหาคำตอบของระบบสมการ
$$a^2+bc\equiv a(mod 37)$$
$$b(a+d)\equiv b(mod 37)$$
$$c(a+d)\equiv c(mod 37)$$
$$bc+d^2\equiv d(mod 37)$$
$$ad-bc\equiv 1(mod 37)$$

2.จงแสดงว่าสมการ $y^{37}\equiv x^3+11(mod p)$ ไม่สามารถแก้ได้สำหรับทุกจำนวนเฉพาะ $p\leq 100$

3.ให้ $n$ เป็นจำนวนนับและ $p$ เป็นจำนวนเฉพาะซึ่ง $n>p$ จงพิสูจน์ว่า
$$\binom{n}{p}\equiv \left\lceil\,\dfrac{n}{p}\right\rceil (mod p)$$
have fun!!!

[square1zoa]

เอ่อ รอดูพวกเทพๆๆๆๆเฉลยนะเนี่ย

[beginner01]

แน่ใจข้อ 2 นะคับ ไม่งั้น ผมให้ $p=2,a=1,b=2$ ก็พังเลยนะคับ
โจทย์มันน่าจะเป็น "สามารถแก้ได้สำหรับทุก..." หรือเปล่าคับ?

ข้อความเดิมเขียนโดยคุณ beginner01

แน่ใจข้อ 2 นะคับ ไม่งั้น ผมให้ $p=2,a=1,b=2$ ก็พังเลยนะคับ
โจทย์มันน่าจะเป็น "สามารถแก้ได้สำหรับทุก..." หรือเปล่าคับ?

คุณ tatari/nightmare ช่วยไขกระจ่างด้วยครับ

[Ai-Ko]

สำหรับข้อ 3 ถ้าตรงที่เป็น ceiling function มันเป็น floor function ก็คิดว่ามีบทพิสูจน์ให้เจ้าค่ะ (รบกวนเจ้าของโจทย์ตรวจสอบความถูกต้องด้วยนะเจ้าคะ)

คิดว่ามีอยู่หลายวิธีเหมือนกัน แต่ในที่นี้จะขอเสนอวิธีการพิสุจน์โดยการอุปนัยเชิงคณิตศาสตร์บน $n$ เจ้าค่ะ
ก่อนอื่น เห็นได้ชัดว่า $\binom{p}{p} \equiv \lfloor \frac{p}{p} \rfloor \pmod{p}$ และ $\binom{p+1}{p} \equiv \lfloor \frac{p+1}{p} \rfloor \pmod{p}$ เป็นจริง

ต่อไป สมมติว่า $\binom{n}{p} \equiv \lfloor \frac{n}{p} \rfloor \pmod{p}$ เป็นจริง จะพิสูจน์ว่า $\binom{n+1}{p} \equiv \lfloor \frac{n+1}{p} \rfloor \pmod{p}$ เป็นจริงด้วย

ก่อนอื่น ถ้า $p$ หาร $n+1$ ไม่ลงตัว จะได้ว่า $(n+1,n-p+1)=(n+1,p)=1$
แต่ $(n+1)\frac{1}{n-p+1}\binom{n}{p}=\binom{n+1}{p}\in \mathbb{Z}$ จึงสรุปได้ว่า $\frac{1}{n-p+1}\binom{n}{p}\in \mathbb{Z}$ ด้วย
ดังนั้น
$$\binom{n+1}{p}=\frac{n+1}{n-p+1}\binom{n}{p}\equiv (n+1)(n-p+1)^{-1}\binom{n}{p} \pmod{p}$$
แต่ $n+1 \equiv n-p+1 \pmod{p}$ ดังนั้น
$$\binom{n+1}{p} \equiv \binom{n}{p} \pmod{p}$$
ในอีกทางหนึ่ง เพราะว่า $p$ หาร $n+1$ ไม่ลงตัว จึงได้ว่า $\lfloor \frac{n+1}{p} \rfloor = \lfloor \frac{n}{p} \rfloor$
เมื่อรวมกับขอสมมติฐานการอุปนัยที่ว่า $\binom{n}{p} \equiv \lfloor \frac{n}{p} \rfloor \pmod{p}$ จึงได้ว่า $\binom{n+1}{p} \equiv \lfloor \frac{n+1}{p} \rfloor \pmod{p}$ ตามต้องการ

ในอีกกรณี ถ้า $p$ หาร $n+1$ ลงตัวแล้ว เราให้ $n+1=kp$ สำหรับบาง $k\in \mathbb{N}$ ดังนั้น
$$\binom{n+1}{p}=\frac{(n+1)n(n-1)\ldots(n-p+2)}{p!}=k\frac{(kp-1)\ldots(kp-p+2)}{(p-1)!}$$
แต่ $\frac{(kp-1)\ldots(kp-p+2)}{(p-1)!}=\binom{kp-1}{p-1}\in \mathbb{Z}$ ดังนั้น
\[\begin{array}{rcl}
\frac{(kp-1)\ldots(kp-p+2)}{(p-1)!} & \equiv & (kp-1)\ldots(kp-p+2)((p-1)!)^{-1} \pmod{p}\\
& \equiv & (-1)\ldots(-p+2)((p-1)!)^{-1} \pmod{p}\\
& \equiv & (-1)^{p-2}(p-2)!((p-1)!)^{-1} \pmod{p}\\
& \equiv & (-1)^{p-2}(p-1)^{-1} \pmod{p}\\
& \equiv & (-1)^{p-2}(-1) \pmod{p}\\
& \equiv & (-1)^{p-1} \pmod{p}
\end{array}\]
กรณีที่ $p>2$ จะได้ว่า $(-1)^{p-1} = 1$ ส่วนในกรณี $p=2$ นั้น $1 \equiv -1 \pmod{2}$ อยู่แล้ว ดังนั้นสำหรับทุกๆ จำนวนเฉพาะ $p$
$$\frac{(kp-1)\ldots(kp-p+2)}{(p-1)!} \equiv 1 \pmod{p}$$
จึงได้ว่า
$$\binom{n+1}{p} \equiv k = \frac{n+1}{p} = \lfloor \frac{n+1}{p} \rfloor \pmod {p}$$

ดังนั้น ด้วยหลักการอุปนัยเชิงคณิตศาสตร์จึงพิสูจน์ตามต้องการ... เจ้าค่ะ

[Ai-Ko]

แล้วก็สำหรับข้อ 1 เจ้าค่ะ...

ก่อนอื่น สังเกตว่า 37 เป็นจำนวนเฉพาะเจ้าค่ะ
เราเริ่มจากการแยกกรณีว่า $b$ หารด้วย 37 ลงตัวหรือไม่

กรณีที่ $b$ หารด้วย 37 ลงตัว จากสมภาคแรกจะได้ว่า
$$a \equiv a^2+bc \equiv a^2 \pmod{37}$$
จะได้ว่า $37|a$ หรือ $a \equiv 1 \pmod{37}$ แต่ถ้า $37|a$ จะทำให้สมภาคที่ห้ากลายเป็น
$$0 \equiv ad-bc \equiv 1 \pmod{37}$$
เกิดข้อขัดแย้ง ดังนั้น $a \equiv 1 \pmod{37}$ แล้วจากสมภาคที่ห้าจะได้ว่า $d \equiv 1 \pmod{37}$ ด้วย สุดท้ายแทนเข้าไปในสมภาคที่สาม จะได้ว่า $2c \equiv c \pmod{37}$ นั่นคือ $c \equiv 0 \pmod{37}$

ดังนั้นในกรณีนี้
\[\begin{array}{rcl}
a & \equiv & 1 \pmod{37}\\
b & \equiv & 0 \pmod{37}\\
c & \equiv & 0 \pmod{37}\\
d & \equiv & 1 \pmod{37}\\
\end{array}\]

กรณีที่ $b$ หารด้วย 37 ไม่ลงตัว จากสมภาคที่สองจะได้ว่า $a+d \equiv 0 \pmod{37}$ ตรงนี้หากเราพิจารณาผลบวกของสมภาคที่หนึ่งและสี่ จะได้ว่า
$$a^2+2bc+d^2 \equiv a+d \equiv 0 \pmod{37}$$
แต่ในอีกแง่หนึ่ง $a+d \equiv 0 \pmod{37} \rightarrow a \equiv -d \pmod{37}$ ดังนั้น $a^2 \equiv d^2 \pmod{37}$
จึงได้ว่า
$$2a^2 +2bc \equiv 0 \pmod{37} \rightarrow a^2+bc \equiv 0 \pmod{37}$$
นำไปเทียบกับสมภาคที่หนึ่งอีกครั้ง จะได้ว่า $a \equiv 0 \pmod{37}$ ในทำนองเดียวกันก็แสดงได้ว่า $d \equiv 0 \pmod{37}$ แล้วแทนค่าเหล่านี้ลงในสมภาคที่สอง จะได้ว่า
$$b \equiv b(a+d) \equiv 0 \pmod{37}$$
จึงขัดแย้งกับที่สมมติได้ว่า $b$ หารด้วย 37 ไม่ลงตัว

ดังนั้นคำตอบของระบบสมภาคนี้จึงมีเพียง
\[\begin{array}{rcl}
a & \equiv & 1 \pmod{37}\\
b & \equiv & 0 \pmod{37}\\
c & \equiv & 0 \pmod{37}\\
d & \equiv & 1 \pmod{37}\\
\end{array}\]
เท่านั้น... เจ้าค่ะ

[Onasdi]

เห็นด้วยครับว่าข้อ 3 ต้องเป็น floor function