Re: [中學] 方程式有根求範圍與函數問題
Gauss 的證法:
For any a|n, we define S(a):={(n/a)*k | k=1~a and (k,a)=1}.
Then we have
1. S(a) and S(b) are disjoint for any a!=b
pf. n*k/a = n*k'/b iff kb=k'a
Then the condition (k,a)=1 & (k',b)=1 => a=b ><.
2. U S(a) = {1,2,..,n}
a|n
pf. Let m an integer between 1 and n, and d=gcd(m,n)
Then gcd(m/d,n/d)=1 and m=n/(n/d)*(m/d) is clearly in S(n/d).
3. Since |S(a)|=ψ(a) and by 1) & 2), we see that Σψ(d) = n.
d|n
※ 引述《JohnMash (Paul)》之銘言：
: ※ 引述《JohnMash (John)》之銘言：
: ※ 引述《Bourbaki (大狐狸)》之銘言：
: : ψ(n)=1,2,...,n-1中跟n互質的數的個數
: : 證明f(n)=Σψ(d) = n
: : d|n
: (2)
: 設不大於n，且與n互質之自然數個數，以f(n)表示，設為p、q相異質數。
: f(pq)=_____
: 1 1
: ANS:f(pq)=pq(1- ─)(1- ─)
: p q
: Let
: n=k*q^s (1)
: and (k,q)=1
: for every m≦n and m|n
: we have
: m=g*q^t where g|k and t=0,1,2...,s
: ψ(m)=ψ(g)ψ(q^t)
: and then
: Σψ(m)= Σ ψ(g)[ψ(1)+ψ(q)+...+ψ(q^s)] (2)
: m|n g|k
: by MATHEMATICAL INDUCTION
: Σ ψ(g)=k (3)
: g|k
: and
: [ψ(1)+ψ(q)+...+ψ(q^s)]
: =1+[q+q^2+...+q^s](1-1/q)
: =1+q^s-1=q^s (4)
: by (1),(2),(3),(4)
: Σψ(m)=k*q^s=n Done.
: m|n
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 99.109.197.44
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 5 篇)：