[math]Euler関数の和公式

smartphone with calculator app showing total amount math
Photo by Karolina Grabowska on Pexels.com

【定理】正の整数nに対して、nと互いに素である1以上n以下の整数の個数をϕ(n)とする。これはEulerのTotient関数と呼ばれ、以下が成り立つ。dnϕ(d)=n

【実験】n=12とすると、nの約数は1,2,3,4,6,12である。ϕ(1)=1 ϕ(2)=1 ϕ(3)=2 ϕ(4)=2 ϕ(6)=2 ϕ(12)=4であるから、確かにdnϕ(d)=nである。

【証明】1anとする。anの最大公約数をdとすると、adndは互いに素な整数である。また、1adndである。これを満たすaの個数は、定義からϕ(ad)となる。nのすべての最大公約数について同様に考えると、n=dnϕ(ad)が分かる。ndnの約数であるから(最大公約数ではないが)、目標の式がわかる。

コメント

タイトルとURLをコピーしました