[中學] 方程式有根求範圍與函數問題
※ 引述《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
If n=rs and (r,s)=1
Claim: ψ(n)=ψ(r)ψ(s)
Proof.
Define Φ(n)={a<=n | (a,n)=1}
denote #Φ(n)=ψ(n)
obviously, if d1 in Φ(r) and d2 in Φ(s)
then d1*d2 in Φ(n),
Hence, ψ(n) >= ψ(r)ψ(s)....(1)
if d,h in Φ(n)
and d=d1=h mod r
d=d2=h mod s
then d-h=0 mod r
d-h=0 mod s
hence d-h=kr=ms
however, (r,s)=1 and d-h<n
hence, k=m=0=d-h
that is, d→(d1,d2) is a one-one map
ψ(n) <= ψ(r)ψ(s)........(2)
by (1),(2) we have ψ(n) = ψ(r)ψ(s)
Furthermore,
if p is prime, then f(p^n)=p^n-p^{n-1}
----------------------------------------------------------
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: 112.104.169.203
推
10/26 00:20,
10/26 00:20
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 112.104.208.153
→
08/28 14:23, , 1F
08/28 14:23, 1F
※ 編輯: JohnMash 來自: 112.104.170.141 (08/28 18:49)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 2 之 5 篇)：