สองข้อที่ไม่ได้ใช้ asymptotic approximation ใช้แนวคิดคล้ายๆกันครับ
อ้างอิง:
ข้อความเดิมเขียนโดยคุณ จูกัดเหลียง
Prove that \(\displaystyle \sum_{\substack{1\le k\le n\\\gcd(k,n)=1}} k=\dfrac{n}{2}\varphi(n)\)
|
กำหนดให้ $n \ge 2$ และ $P(x)$ แทนข้อความว่า $x$ เป็นจำนวนเต็มซึ่ง $1 \le x < n$ และ $\gcd(x,n)=1$
สังเกตว่า $P(k)$ เป็นจริงก็ต่อเมื่อ $P(n-k)$ เป็นจริง เลยได้ว่าผลรวมดังกล่าวสามารถเขียนได้สองแบบคือ $A:=\sum_{P(k)} k$ หรือ $A=\sum_{P(n-k)} n-k=\sum_{P(k)} n-k$ บวกกันหารสองก็จะได้
$$A=\frac{1}{2} \sum_{P(k)} n = \frac{1}{2} \cdot \varphi(n) \cdot n$$
เมื่อ $\varphi(n)$ คือ Euler's totient function
อ้างอิง:
ข้อความเดิมเขียนโดยคุณ จูกัดเหลียง
Prove that \(\displaystyle\prod_{d|n}d=n^{\tau(n)/2}\)
|
กำหนดให้ $n \ge 2$ และ $P(x)$ แทนข้อความว่า $x$ เป็นจำนวนเต็มบวกซึ่ง $x \mid n$
สังเกตว่า $P(d)$ เป็นจริงก็ต่อเมื่อ $P(\frac{n}{d})$ เป็นจริง เลยเขียนผลคูณได้สองแบบคือ $A:=\prod_{P(d)}d$ หรือ $A=\sum_{P(\frac{n}{d})} \frac{n}{d}=\sum_{P(d)} \frac{n}{d}$ คูณกันแล้วถอดสแควร์รูทได้
$$A=\sqrt{\prod_{P(d)} n}=n^{\frac{\tau(n)}{2}}$$
เมื่อ $\tau(n)$ คือ divisor funtion อันดับ 0 (จำนวนของตัวหารบวกของ $n$)