FFTMO9

[PP_nine]

ข้อสองวงเล็บปีกกาคือเซตครับ

ถ้ากล่าวถึงเซตโดยมีคำว่า modulo $p$ มันจะแปลว่า เซตของเศษเหลือใน mod $p$ ประมาณนี้อ่ะครับ (ละไว้ในฐานที่เข้าใจ)

พูดง่ายๆ ข้อสองก็คือ ให้พิสูจน์ว่ากลุ่มเซตของอินเวิร์สเป็นการเรียงสับเปลี่ยนกันเอง เช่น

พิจารณา mod 7 เซตเศษเหลือ (เอาแบบง่ายๆ) ก็คือ $\left\{\, 1,2,...,6 \right\} $ ซึ่ง

$$1 \cdot 1 \equiv 1 (mod \, \, 7)$$$$2 \cdot 4 \equiv 1 (mod \, \, 7)$$$$3 \cdot 5 \equiv 1 (mod \, \, 7)$$$$4 \cdot 2 \equiv 1 (mod \, \, 7)$$$$5 \cdot 3 \equiv 1 (mod \, \, 7)$$$$6 \cdot 6 \equiv 1 (mod \, \, 7)$$

สังเกตว่าอินเวิร์สมีแบบที่ไม่ซ้ำกันเลย นี่แหละคือคำถาม ให้พิสูจน์ว่าอินเวอร์สไม่ซ้ำกันสำหรับจำนวนเฉพาะ $p$ ใดๆเท่านั้นเอง

[PP_nine]

จริงๆผมชอบเรื่อง inverse modulo มากที่สุดใน number แล้วครับ มาต่อโจทย์ให้เลยละกัน

7.สำหรับจำนวนเฉพาะ $p$ ซึ่ง $p \equiv 3 \pmod{4}$ ถ้าเรา partition เซต $\left\{\,1,2,...,p-1 \right\}$ ออกเป็นสองเซตที่มีจำนวนสมาชิกเท่ากัน

โดยที่สมาชิกในแต่ละเซตมี inverse modulo $p$ อยู่ในเซตเดียวกันแล้ว เราจะสามารถ partition แบบนี้ได้กี่วิธี

(ข้อนี้ไม่ยากครับ แค่ทดสอบความรู้พื้นฐานของอินเวอร์ส)


8.จงใช้ความรู้เรื่อง inverse พิสูจน์ทฤษฎีบทของ Wilson ที่กล่าวว่า สำหรับจำนวนเฉพาะ $p$ ใดๆ,
$$(p-1)! \equiv -1 \pmod{p}$$

9.พิสูจน์ทฤษฎีของ Wolstenholme ดังนี้
9.1) สำหรับจำนวนเฉพาะ $p \ge 5$ และจำนวนเต็ม $a,b$ ซึ่ง $(a,b)=1$ และ
$$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}=\frac{a}{b}$$
พิสูจน์ว่า $p^2|a$
9.2) สำหรับจำนวนเฉพาะ $p \ge 5$ และจำนวนเต็ม $a,b$ ซึ่ง $(a,b)=1$ และ
$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{(p-1)^2}=\frac{a}{b}$$
พิสูจน์ว่า $p|a$

[จูกัดเหลียง]

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

5. พิสูจน์ว่า ถ้าจำนวนเต็ม $a_i$ สำหรับ $i=1,2,...,p-1$ เมื่อ $p$ เป็นจำนวนเฉพาะ เป็นจำนวนที่ต่างกันใน modulo $p$ ซึ่ง $(a_i,p)=1$ แล้ว
$$\left\{\, a_1, a_2, ..., a_{p-1} \right\} = \left\{\, a_1^{-1}, a_2^{-1}, ..., a_{p-1}^{-1}\right\}$$ ใน modulo $p$

My Unsure SolN

จากโจทย์ จะได้ว่า $a_{i}\in\mathbb{I}$ให้ $b_{i}\in\mathbb{I}$ เเละ $a_{i}b_{i}\equiv 1 \pmod p\rightarrow p|({a_ib_i-1})$
เเละ กำหนด $A=\left\{\,a_{i}|(a_{i},p)=1 \wedge i\in \left\{\,1,2,3...,p-1\right\} \right\} $
สมมุติว่า $b_{i}\not\in A\therefore b_{i}=pk$ สำหรับบางค่า $k\in\mathbb{I}$
เเละจาก $p|a_{i}b_i-1 \rightarrow a_ipk-1=px$ สำหรับบางค่า $x\in\mathbb{I}$ ซึ่งเกิดข้อขัดเเย้ง
เพราะฉะนั้น $b_{i}$ ก็หล่นไปอยู่ใน $A$ ทำให้ได้ว่า $\left\{\,a_{i}\right\} =\left\{\,b_{i}\right\} $

ปล.ลองเฉลยข้อ 6 พอเป็นเเนวทางหน่อยได้ไหมครับ TT

[PP_nine]

มีคนเคยมาถามผมแล้ว และก็เขียนเฉลยในแบบของผมเอาไว้ในนี้ล่ะครับ (อาจจะงงๆหน่อยนะครับ ค่อยๆอ่าน )

http://www.mathcenter.net/forum/showthread.php?t=13589



อันนี้เป็นขั้นตอนการพิสูจน์ทีละขั้น ส่วนวิธีการพิสูจน์ในแต่ละข้อก็ประปรายอยู่ในลิ้งค์นั้นแล้ว

1.พิสูจน์ว่าอินเวอร์สของแต่ละสมาชิกในเซ็ต $\left\{\, 1,2,...,p-1 \right\} $ เมื่อ $p$ เป็นจำนวนเฉพาะ คือการเรียงสับเปลี่ยนกันเองในเซต

ตัวอย่างเช่น http://www.mathcenter.net/forum/show...5120&page=2#16

ซึ่งในตัวอย่างนี้อาจขยายเป็นกรณีทั่วไปได้ โดยเป็นเซตที่ไม่มีสามชิกตัวใด congruence กันเองใน mod $p$

และกรณีทั่วไปนี้เองที่ผมตั้งเป็นโจทย์ข้อห้าใน http://www.mathcenter.net/forum/show...php?t=15120#14

2.พิสูจน์ว่าอินเวอร์สของสมาชิกในเซต $\left\{\, 1^2,2^2,...,(p-1)^2 \right\} $ จะมีบางตัวซ้ำกัน

แต่ แต่ แต่... มันจะซ้ำกันเพียงแค่ $\frac{p-1}{2}$ แบบเท่านั้น (อย่างก่อนหน้านี้ ข้อ 3 เราบอกว่ามันไม่ซ้ำกัน ซึ่งก็หมายความว่าแตกต่างกัน $p-1$ ตัวนั่นเอง)

3.พิสูจน์ว่าอินเวอร์สของสมชิกในเซต $\left\{\, 1^2,2^2,...,(\frac{p-1}{2})^2 \right\} $ ก็คือการเรียงสับเปลี่ยนของตัวมันเอง คล้ายกับข้อ 3

***4.พอจะนึกออกหรือยังครับว่าการดีไซน์โจทย์ประเภทนี้ก็คือ ใช้ลักษณะพิเศษที่ว่า มันเป็นเพียงการเรียงสับเปลี่ยน

ดังนั้น สำหรับจำนวนเฉพาะ $p$ ใดๆ เราอาจกล่าวได้ว่า
$$1^{-1}+2^{-1}+...+(p-1)^{-1} \equiv 1+2+...+(p-1) (mod \, \, p)$$
(เพื่อความสะดวก จะเขียน $a^{-2}$ แทน $(a^{-1})^2$) และเช่นเดียวกันกับ $a^{-2}$ ก็จะได้ว่า
$$1^{-2}+2^{-2}+...+\Big( \frac{p-1}{2} \Big) ^{-2} \equiv 1^2+2^2+...+\Big( \frac{p-1}{2} \Big) ^2 (mod \, \, p)$$

5.เก็บรายละเอียดด้วย Wilson's Theorem โดยการคูณพวก factorial ลงไปเพื่อให้เป็นจำนวนเต็ม เราจึงจะนำมันมาพิจารณาใน congruence ได้

เพราะเราไม่ได้บอกว่า $\frac{1}{a}$ ในสมการ คือ $a^{-1}$ ในสมภาค แล้วค่อยลดทอนลงไปเรื่อยๆจนได้ดังที่ผมเฉลยไว้ครับ [/quote]

[PP_nine]

เพิ่งจะลองเปิดดูเฉลย จริงๆข้อนี้ทำแบบ contradiction ง่ายกว่าเยอะครับ

ข้อความเดิมเขียนโดยคุณ จูกัดเหลียง

My Unsure SolN

จากโจทย์ จะได้ว่า $a_{i}\in\mathbb{I}$ให้ $b_{i}\in\mathbb{I}$ เเละ $a_{i}b_{i}\equiv 1 \pmod p\rightarrow p|({a_ib_i-1})$
เเละ กำหนด $A=\left\{\,a_{i}|(a_{i},p)=1 \wedge i\in \left\{\,1,2,3...,p-1\right\} \right\} $
สมมุติว่า $b_{i}\not\in A\therefore b_{i}=pk$ สำหรับบางค่า $k\in\mathbb{I}$
เเละจาก $p|a_{i}b_i-1 \rightarrow a_ipk-1=px$ สำหรับบางค่า $x\in\mathbb{I}$ ซึ่งเกิดข้อขัดเเย้ง
เพราะฉะนั้น $b_{i}$ ก็หล่นไปอยู่ใน $A$ ทำให้ได้ว่า $\left\{\,a_{i}\right\} =\left\{\,b_{i}\right\} $

ปล.ลองเฉลยข้อ 6 พอเป็นเเนวทางหน่อยได้ไหมครับ TT

โจทย์บอกว่า $\left\{\, a_1, a_2,...,a_{p-1} \right\}$ เป็นจำนวนที่ต่างกันใน modulo $p$ แสดงว่าไม่มีคู่ใดที่ congruence กันเอง

แปลได้ว่า สำหรับทุก $i,j \in \left\{\, 1,2,...,p-1 \right\}$ ซึ่ง $i \not= j$ แล้ว $a_i \not\equiv a_j \pmod{p}$

สมมติว่ามีบาง $a_i, a_j$ ที่ใช้อินเวอร์สร่วมกัน แสดงว่า $a_i^{-1} \equiv a_j^{-1} \pmod{p}$

คูณด้วย $a_ia_j$ ซะก็จบ เพราะจะได้ว่า $a_j \equiv a_i \pmod{p}$ ทันที จึงเกิดข้อขัดแย้ง

ดังนั้น จะไม่มีคู่ $a_i,a_j$ ต่างกันใดๆที่มีอินเวอร์สตัวเดียวกันใน modulo $p$

(พอมันใช้อินเวอร์สอย่างไม่ซ้ำกัน ก็แสดงว่ามันเป็นการเรียงสับเปลี่ยนเท่านั้นเอง สองเซตดังกล่าวจึงเท่ากัน)

[จูกัดเหลียง]

#21 เจ๋งดีอ่ะครับ

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

7.สำหรับจำนวนเฉพาะ $p$ ซึ่ง $p \equiv 3 \pmod{4}$ ถ้าเรา partition เซต $\left\{\,1,2,...,p-1 \right\}$ ออกเป็นสองเซตที่มีจำนวนสมาชิกเท่ากัน
โดยที่สมาชิกในแต่ละเซตมี inverse modulo $p$ อยู่ในเซตเดียวกันแล้ว เราจะสามารถ partition แบบนี้ได้กี่วิธี

ข้อนี้ผมก็จะขอเดาว่า $$(k+1)\binom{3k}{k+1}\binom{2k-1}{k+1} $$
เมื่อ $p=4k+3,k\ge 2$

[PP_nine]

ยังไม่ถูกครับ

ที่ผมบอกว่าทดสอบความรู้พื้นฐานก็เพราะว่า...

hint

$1^{-1} \equiv 1 \pmod{p}$ และ $(p-1)^{-1} \equiv p-1 \pmod{p}$ เสมอ

ซึ่งตัวนี้จะช่วยให้มองเห็นภาพการ partition ได้ดีขึ้นเยอะเลยครับ

แถมยังช่วยในการแก้ปัญหาข้อ 8 อีกด้วย

พอเราค่อยๆเข้าใจทีละนิดๆมันก็จะสนุกไปเอง ผมถึงได้ชอบ

[จูกัดเหลียง]

#22 งั้นผมขอดองโจทย์ไว้พรุ่งนี้ก่อนละกัน

เเต่ก็ต้องขอบคุณ# ก่อนๆไปก่อน คงต้องทำความเข้าใจอีกเยอะ 555
ขอบคุณมากๆเลยครับ

[AnDroMeDa]

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

8.จงใช้ความรู้เรื่อง inverse พิสูจน์ทฤษฎีบทของ Wilson ที่กล่าวว่า สำหรับจำนวนเฉพาะ $p$ ใดๆ,
$$(p-1)! \equiv -1 \pmod{p}$$

เล่นด้วยนะ
สำหรับ $p=2,3$เช็คง่ายๆให้$p>3$จาก $p$ เป็นจำนวนเฉพาะจะได้$p$จำนวนเฉพาะสัมพัทธ์กับ$1,2,...,p-1$
จะมี$a,b\in {1,2,...,p-1}$ซึ่ง$ab\equiv 1 \pmod{p}$โดย#20ได้ว่า$b$ใช้ไปครั้งเดียวแน่นอน
$\Rightarrow 2\bullet 3\bullet 4\bullet ...\bullet (p-2)\equiv 1 \pmod{p}$
$\Rightarrow 2\bullet 3\bullet 4\bullet ...\bullet (p-2)\bullet (p-1)\equiv p-1 \equiv -1 \pmod{p}$

[AnDroMeDa]

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

9.พิสูจน์ทฤษฎีของ Wolstenholme ดังนี้
9.1) สำหรับจำนวนเฉพาะ $p \ge 5$ และจำนวนเต็ม $a,b$ ซึ่ง $(a,b)=1$ และ
$$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}=\frac{a}{b}$$
พิสูจน์ว่า $p^2|a$
9.2) สำหรับจำนวนเฉพาะ $p \ge 5$ และจำนวนเต็ม $a,b$ ซึ่ง $(a,b)=1$ และ
$$1+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{(p-1)^2}=\frac{a}{b}$$
พิสูจน์ว่า $p|a$

9.1 ให้ $H_{p-1}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$ note:$p-i \equiv -i \pmod{p}$
จะแสดงว่า ถ้า$p$เป็นจำนวนเฉพาะที่$\geqslant 5$แล้ว $$p^2|(p-1)!(H_{p-1}) =\sum_{i = 1}^{\frac{p-1}{2} } (p-1)!(\frac{1}{i} +\frac{1}{p-i} ) =\sum_{i = 1}^{\frac{p-1}{2} } (p-1)!\frac{p}{i(p-i)} \Leftrightarrow p|\sum_{i = 1}^{\frac{p-1}{2} } (p-1)!\frac{1}{i(p-i)} $$
$$\Leftrightarrow \sum_{i = 1}^{\frac{p-1}{2} } (p-1)!\frac{1}{i(p-i)}\equiv 0 \pmod{p}$$
จาก note ,wilson's theorem และ inverse modulo ได้ว่า $$\sum_{i = 1}^{\frac{p-1}{2} } (p-1)!\frac{1}{i(p-i)}\equiv \sum_{i = 1}^{\frac{p-1}{2} } (p-1)!\frac{1}{-i^2} \equiv \sum_{i = 1}^{\frac{p-1}{2} } \frac{1}{i^2} \equiv \sum_{i = 1}^{\frac{p-1}{2} } i^2 = \frac{p(p^2-1)}{24}\equiv 0 \pmod{p} $$
เป็นจริงเพราะว่า $(p,24)=1$
ข้อ 9.2 ก็ทำคล้ายๆกันนะ

[BLACK-Dragon]

ผมพอจะเข้า #20 แล้วว่าจะต้องให้ทำอะไีรขอบคุณมากครับ

การที่ inverse ของ ${1,2,3,...,p-1}$ คือ การเรียงสับเปลี่่ยนของตัวมันเอง นั่นหมายถึง inverse จะต้องไม่ซ้ำกัน หรือ congruence

สมมุิติให้ $a,b \in { {1,2,3,...,p-1} }$ โดยที่ $a^{-1} \equiv b^{-1} \pmod {p}$

$1 \equiv a \cdot b^{-1} \pmod {p}$ แต่ว่า $1 \equiv b \cdot b^{-1} \pmod{p}$

$a \cdot b^{-1} \equiv b \cdot b^{-1} \pmod{p}$ นั่นแปลว่า $a \equiv b \pmod{p}$

$p | a-b$ เกิดข้อขัดแย้งจากที่เราสมมุติว่า $a,b \in { {1,2,3,...,p-1} }$

[PP_nine]

ถ้าเริ่มเข้าใจ inverse modulo $p$ สำหรับจำนวนเฉพาะ $p$ แล้วล่ะก็ ขอขยับขึ้นมาให้ใกล้กับกรณีทั่วไปอีกหน่อยละกัน

10. สำหรับจำนวนนับ $k,a,b$ ซึ่ง $k \ge 2$ และ $(a,b)=1$ สอดคล้องกับ
$$1+\frac{1}{3}+\frac{1}{5}+\cdots+\frac{1}{2^k-1}=\frac{a}{b}$$
พิสูจน์ $2^k|a$

more stronger

พิสูจน์ $4^{k-1}|a$

[PP_nine]

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

9.1 ให้ $H_{p-1}=1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{p-1}$ note:$p-i \equiv i \pmod{p}$
จะแสดงว่า ถ้า$p$เป็นจำนวนเฉพาะที่$\geqslant 5$แล้ว $$p^2|H_{p-1} \Rightarrow p^2|2H_{p-1}=\sum_{i = 1}^{p-1} (\frac{1}{i} +\frac{1}{p-i} ) =\sum_{i = 1}^{p-1} \frac{p}{i(p-i)} \Leftrightarrow p|\sum_{i = 1}^{p-1} \frac{1}{i(p-i)} \Leftrightarrow \sum_{i = 1}^{p-1} \frac{1}{i(p-i)}\equiv 0 \pmod{p}$$
จาก note และ inverse modulo ได้ว่า $$\sum_{i = 1}^{p-1} \frac{1}{i(p-i)}\equiv \sum_{i = 1}^{p-1} \frac{1}{i^2} \equiv \sum_{i = 1}^{p-1} i^2 = \frac{(p-1)p(2p-1)}{6}\equiv 0 \pmod{p} $$
เป็นจริงเพราะว่า $(p,6)=1$
ข้อ 9.2 ก็ทำคล้ายๆกันนะ

เพิ่งจะมีเวลามาตรวจสอบ ตรงนี้ไม่จริงนะครับ
$$\sum_{i = 1}^{p-1} \frac{1}{i^2} \equiv \sum_{i = 1}^{p-1} i^2$$
เพราะ $k^2 \equiv (p-k)^2 \pmod{p}$ เสมอ นั่นแสดงว่าสำหรับกำลังสอง มีการใช้ inverse ซ้ำกัน

แต่สำหรับกำลังหนึ่งจะไม่มีคู่ใดใช้อินเวอร์สซ้ำกัน ระวังด้วยนะครับๆ

[AnDroMeDa]

#29
ถามหน่อยครับ ถึงว่าจะซ้ำคู่แต่ก็เขียนให้มันเป็นแบบนั้นได้ไม่ใช่หรอครับเช่นให้ $p=7$
จะได้ $\sum_{i = 1}^{6} \frac{1}{i^2} = \frac{1}{1^2} +\frac{1}{2^2} +\frac{1}{3^2} +\frac{1}{4^2} +\frac{1}{5^2} +\frac{1}{6^2} \equiv 1^2+3^2+2^2+5^2+4^2+6^2 = \sum_{i = 1}^{6} i^2\pmod{7}$

[จูกัดเหลียง]

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

8.จงใช้ความรู้เรื่อง inverse พิสูจน์ทฤษฎีบทของ Wilson ที่กล่าวว่า สำหรับจำนวนเฉพาะ $p$ ใดๆ,
$$(p-1)! \equiv -1 \pmod{p}$$

จากที่ $1,2,...,p-1$ จะมีอินเวอร์สในเซตเดีวกัน เเต่ $p-1$ มีอินเวิร์สเป็นตัวมันเอง จึงถือว่าไม่มีในเซต
ทำให้ได้ว่า $$1\cdot 2\cdot3...(p-1)\equiv p-1 =-1\pmod p$$