ฟังก์ชันและสมภาคครับ

[Jew]

สำหรับจำนวนเต็มบวก n ใดๆจงแสดงว่า
$\sum_{d = 1}^{n}\ Phi (n)\left\lfloor\,n/d\right\rfloor=n(n+1)/2$

สำหรับจำนวนเต็ม $n\succ 2$ จงแสดงว่า
$\Phi (n^2) + \Phi ((n+1)^2)\leqslant 2n^2$

จงพิสูจน์ว่าแต่ละสมภาคตอไปนี้

$x^{(p-1)/2}-1\equiv 0(mod p),((x^{p-1/2}+1 \equiv 0 \pmod{p} ))$
มีราก(มอดุโล p) จำนวน (p-1)/2 รากเท่ากัน
เมื่อ p เป็นจำนวนเฉพาะที่มากกว่า 2
ขอบคุณล่วงหน้าครับ

[nooonuii]

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

สำหรับจำนวนเต็ม $n > 2$ จงแสดงว่า
$\phi(n^2) + \phi((n+1)^2)\leq 2n^2$

ลองพิสูจน์ว่า $\phi(n)\leq n-\sqrt{n}$

เมื่อ $n$ เป็นจำนวนประกอบ

[Jew]

รบกวนช่วยพิสูจน์ว่า $\phi(n)\leq n-\sqrt{n}$

เมื่อ $n$ เป็นจำนวนประกอบ หน่อยได้ไหมครับ

[nooonuii]

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

รบกวนช่วยพิสูจน์ว่า $\phi(n)\leq n-\sqrt{n}$

เมื่อ $n$ เป็นจำนวนประกอบ หน่อยได้ไหมครับ

If $n$ is composite, $n$ has at least one prime factor $p\leq\sqrt{n}$.

$\phi(n)=n\Big(1-\dfrac{1}{p_1}\Big)\cdots\Big(1-\dfrac{1}{p_k}\Big)$

$\leq n(1-\dfrac{1}{p})$

$\leq n-\sqrt{n}$.

[Jew]

อ๋อได้แล้วครับ
รบกวน้อ มอดุโลได้ไหมครับ

[nooonuii]

ยังงงๆกับโจทย์ข้อแรกอยู่เลยครับ

ตรง $\phi(n)$ นี่คือ $\phi(d)$ หรือเปล่าครับ

[picmy]

สำหรับข้อที่ 3 นะครับ
Step1:
จาก Fermat’s theorem เราจะได้ว่า
สำหรับทุกจำนวนเฉพาะ $p$
$x^p \equiv x (mod p) $
และถ้า $(x,p)=1$
จะได้ว่า $x^{p-1} \equiv 1 (mod p)$
นั่นคือ $(x^{\frac{p-1}{2}}-1)( x^{\frac{p-1}{2}}+1)\equiv 0 (mod p)$
ดังนั้น $ x^{\frac{p-1}{2}}-1 \equiv 0 (mod p)$-----(1)
หรือ $ x^{\frac{p-1}{2}}+1 \equiv 0 (mod p)$-----(2)
นอกจากนั้น จาก $p> 2$ จะได้ว่า $x$ ไม่มีทางที่จะสอดคล้อง (1)และ(2)พร้อมๆกันได้
(ถ้าไม่เช่นนั้น สังเกต (1)+(2): $2x^{\frac{p-1}{2}} \equiv 0 (mod p)$ ซึ่งเป็นไปไม่ได้)
Step2:
ข้างล่าง จะแสดงว่า “ $x^{\frac{p-1}{2}}-1 \equiv 0 (mod p)$ ก็ต่อเมื่อ มีจำนวนเต็ม $y$ ที่ทำให้ $y^2\equiv x (mod p)$”
“ขาไป” สมมติ $x^{\frac{p-1}{2}}-1\equiv 0 (mod p)$
จะได้ว่า $p \nmid x$
หลังจากนั้นพิจารณา สมการ $ay\equiv x (mod p)$
จาก $p \nmid x$ จะได้ว่า สำหรับทุก $1\leqslant a \leqslant p-1$
มี $y=y_a \in \{1,2,…,p-1\}$ เพียงตัวเดียวเท่านั้นที่ทำให้ $ay\equiv x (mod p)$
สมมติ ถ้าไม่มีจำนวนเต็ม $y$ ที่ทำให้ $y^2 \equiv x (mod p)$
พิจารณาการจับคู่ของจำนวนในเซต $\{1,2,…,p-1\}$
โดยเราจะสามารถจับคู่ระหว่าง $a$ กับ $y_a$ ซึ่งจะจับคู่กันได้$\frac{p-1}{2}$คู่พอดี
ทำให้ได้ว่า $(p-1)! \equiv x^{\frac{p-1}{2}} \equiv 1 (mod p)$
ซึ่งขัดแย้งกับ Wilson’s theorem : $(p-1)! \equiv -1 (mod p)$
ดังนั้น จึงได้ว่า มีจำนวนเต็ม $y$ ที่ทำให้ $y^2\equiv x (mod p)$
“ขากลับ” สมมติ มีจำนวนเต็ม $y_0$ ที่ทำให้ ${y_0}^2 \equiv x (mod p)$
จะได้ว่า ${y_0}^{p-1} \equiv x^{\frac{p-1}{2}} (mod p)$
จาก $p \nmid x$ ดังนั้น $p \nmid y_0$
จาก Fermat’s theorem ได้ว่า ${y_0}^{p-1} \equiv 1(mod p)$
ดังนั้น $x^{\frac{p-1}{2}} \equiv 1 (mod p)$
Step3:
ต่อไป จะแสดงว่า “มี $x \in \{1,2,…,p-1\}$ อยู่ $\frac{p-1}{2}$ ตัวพอดีที่จะทำให้ มีจำนวนเต็ม $y$ ที่ $y^2 \equiv x (mod p)$ ”
ที่จริงแล้ว พิจารณา $y=-\frac{p-1}{2},-\frac{p-1}{2}+1,…,-1,1,…,\frac{p-1}{2}-1, \frac{p-1}{2}$ ( นี่คือค่าทั้งหมดที่เป็นไปได้ที่ไม่คอนกรูเอนซ์กัน mod p ของ $y$)
จึงได้ว่า $x \equiv (-\frac{p-1}{2})^2,(-\frac{p-1}{2}+1)^2,…,(-1)^2,1^2,…,(\frac{p-1}{2}-1)^2,( \frac{p-1}{2})^2 (mod p)$
นั่นคือ $x \equiv 1^2,…,(\frac{p-1}{2}-1)^2,( \frac{p-1}{2})^2 (mod p)$
โดยที่ ทุก $1\leqslant i < j \leqslant \frac{p-1}{2} ,$ $i^2 \not\equiv j^2 (mod p)$
ดังนั้น มี $x \in \{1,2,…,p-1\}$ อยู่ $\frac{p-1}{2}$ ตัวพอดีที่จะทำให้ มีจำนวนเต็ม $y$ ที่ $y^2\equiv x (mod p)$

จาก Step1,2,3 จะได้ว่า $ x^{\frac{p-1}{2}}-1 \equiv 0 (mod p)$ มีราก(มอดุโล p) อยู่ $\frac{p-1}{2}$รากพอดี
และจาก Step1 เราได้แสดงแล้วว่า ทุก $x$ ถ้า $p \nmid x$ แล้ว $x$ จะต้องสอดคล้อง (1) หรือ (2) สมการใดสมการหนึ่ง (และสอดคล้องพร้อมกันไม่ได้)
ดังนั้น ถ้า $x \in \{1,2,…,p-1\}$ ไม่ใช่รากของ $ x^{\frac{p-1}{2}}-1\equiv 0 (mod p)$ ก็จะต้องเป็นรากของ $ x^{\frac{p-1}{2}}+1 \equiv 0 (mod p)$
นั่นคือ $ x^{\frac{p-1}{2}}+1 \equiv 0 (mod p)$ มีราก(มอดุโล p) อยู่ $(p-1)-\frac{p-1}{2}=\frac{p-1}{2}$รากพอดี

[picmy]

สำหรับข้อแรกนะครับ
ผมเห็นด้วยกับคุณ nooonuii ครับว่า ตรง $\phi(n)$ควรจะเป็น $\phi(d)$

ก่อนอื่น จะแสดงก่อนว่า
$\{(x,y) \in \aleph \times \aleph |1\leqslant y\leqslant x\leqslant n \}=\{(id,(\sum_{m\mid id, m<d } \phi(m)) +j) | 1\leqslant d\leqslant n , 1\leqslant i\leqslant \left\lfloor \frac{n}{d}\right\rfloor,0< j\leqslant \phi(d) \}$
เพื่อความสะดวก กำหนดให้
$A=\{(x,y) \in \aleph \times \aleph |1\leqslant y\leqslant x\leqslant n \}$
$B=\{(id,(\sum_{m\mid id, m<d } \phi(m)) +j) | 1\leqslant d\leqslant n , 1\leqslant i\leqslant \left\lfloor \frac{n}{d}\right\rfloor,0< j\leqslant \phi(d) \}$
(ถ้างงว่าเซต B คืออะไร ก็ลองวาดกราฟออกมาดูนะครับ แล้วจะเห็นชัดขึ้น)
พิสูจน์ :
ก่อนอื่น ง่ายที่จะแสดงว่า $B\subseteq A$ (ใช้ $\sum_{m \mid x}\phi(m) = x$)
ต่อไป จะแสดงว่า $A \subseteq B$
ทุก $(x',y') \in A$
เนื่องจาก $\sum_{m \mid x'}\phi(m) =x'$ และ $1\leqslant y' \leqslant x'$
จะได้ว่า มี $d \in \{1,2,...,n\}$ ซึ่ง $d \mid x'$ ที่ทำให้ $\sum_{m\mid x', m<d } \phi(m)< y' \leqslant \sum_{m\mid x', m\leqslant d } \phi(m))$
$(x',y') = ((\frac{x'}{d})d,\sum_{m\mid x', m<d } \phi(m)+(y'-\sum_{m\mid x', m<d } \phi(m))) \in B$
(หมายเหตุ:ลองเลือก $i= \frac{x'}{d} , j= y'-\sum_{m\mid x', m<d } \phi(m)$)
นั่นคือ $A \subseteq B$
ดังนั้น $A=B$
และเนื่องจาก $\#A= \frac{n(n+1)}{2}$
$\#B= \sum_{d=1}^{n}\phi(d)\left\lfloor\frac{n}{d}\right\rfloor $
จึงได้ว่า $\frac{n(n+1)}{2}=\sum_{d=1}^{n}\phi(d)\left\lfloor\frac{n}{d}\right\rfloor $

[beginner01]

ขอเสริมข้อ 3 ด้วยว่า จริงๆแล้วมันมีทฤษฎีบทหนึ่งกล่าวไว้ว่า:

ให้ m เป็นจำนวนเต็มบวกที่มี primitive root ถ้า k เป็นจำนวนเต็มบวกและ a เป็นจำนวนเต็มที่ $(a,m)=1$ แล้วสมการ $x^k\equiv a\pmod{m}$ จะมีคำตอบก็ต่อเมื่อ $a^{\frac{\phi(m)}{d}}\equiv 1\pmod{m}$ เมื่อ $d=(k,\phi(m))$
นอกจากนี้ ถ้าสมการ $x^k\equiv a\pmod{m}$ มีคำตอบ แล้วสมการนี้จะมีคำตอบที่ไม่คอนกรูเอนท์กัน $d$ คำตอบในมอดุโล $m$

ข้อ 3 ก็จะกลายเป็น corollary ของทฤษฎีบทนี้ด้วย

[Jew]

จงใช้อุปนัยเพื่อแสดงว่า
$2^{3^n} \equiv-1(mod3^n)$ขอบคุรมากๆครับ

[LightLucifer]

ให้ $P(n)$ แทนประโยคเปิด $2^{3^n}\equiv -1 (mod 3^n)$

Basic step
$8\equiv -1 (mod 3)$
$\therefore P(1)$ จริง

Induction step
ให้ $k\in \mathbb{N} $ โดยที่ $P(k)$ จริง
จะได้ว่า $2^{3^k}\equiv -1 (mod 3^k) $
นั่นคือจะมี $m\in \mathbb{Z} $ ซึ่ง $2^{3^k}+1=3^k(m)$

เนื่องจาก $2\equiv -1 (mod3)$
จะได้ว่า
$2^{23^k}\equiv 1 (mod3)$
$2^{3^k}\equiv -1 (mod3)$
ดังนั้น
$2^{23^k}-2^{3^k}+1\equiv 1-(-1)+1\equiv 3\equiv 0 (mod3)$
นั่นคือ $3\mid 2^{23^k}-2^{3^k}+1$
นั่นคือจะมี $l\in \mathbb{Z} $ ซึ่ง $2^{23^k}-2^{3^k}+1=3l$
พิจรณา $2^{3^{k+1}}+1=(2^{3^k})^3+1=(2^{3^k}+1)(2^{23^k}-2^{3^k}+1)=3^k(m)(3l)=3^{k+1}(ml)$
จะได้ว่า $2^{3^{k+1}}\equiv -1 (mod3^{k+1})$
$\therefore P(k+1)$ เป็นจริง

$\therefore P(n)$จริงโดย หลักการอุปนัยเชิงคณิตศาสตร์