Φ(n) là số các giá trị nguyên tố cùng nhau với n trong khoảng [0;n-1].Tìm φ(p^e)?(p nguyên tố,e>0)

[newbie_lap_trinh (newbie lập trình)]

Φ(n) là số các giá trị nguyên tố cùng nhau với n trong khoảng [0;n-1].Tìm φ(p^e)?(p nguyên tố,e>0)

Đây là bài tập 1.2.4-27 trong “The art of computer programming”.

Đáp án trong sách là:
φ(p^e) = p^e - p^(e-1)

Rõ ràng trong khoảng [0;p^e-1] chỉ e giá trị(p^1;p^2;…;p^(e-1)) không nguyên tố cùng nhau với p^e.Vậy:φ(p^e) = p^e - e (!?).
Chả lẽ mình đếm sót giá trị nào à ?

*Edit:Mình mới nghĩ ra tức thì

[rogp10]

Vậy còn 2p^2, 3p^2, … thì sao?

[newbie_lap_trinh (newbie lập trình)]

Bội của p gần nhất với p^e - 1 là: p^e - p = [p^(e-1) - 1].p
0.p -> [p^(e-1) - 1].p => p^(e-1) giá trị không ntcn với m

[rogp10]

Nó ntn: chỉ cần chia hết cho p là out, vậy cứ p số bỏ 1 số => trừ đi 1/p.