[math]Euler関数の和公式 mathPhoto by Karolina Grabowska on Pexels.com Twitter Facebook はてブ Pocket LINE コピー 2023.01.292021.10.24 【定理】正の整数nに対して、nと互いに素である1以上n以下の整数の個数をϕ(n)とする。これはEulerのTotient関数と呼ばれ、以下が成り立つ。∑d∣nϕ(d)=n 【実験】n=12とすると、nの約数は1,2,3,4,6,12である。ϕ(1)=1 ϕ(2)=1 ϕ(3)=2 ϕ(4)=2 ϕ(6)=2 ϕ(12)=4であるから、確かに∑d∣nϕ(d)=nである。 【証明】1≤a≤nとする。aとnの最大公約数をdとすると、adとndは互いに素な整数である。また、1≤ad≤ndである。これを満たすaの個数は、定義からϕ(ad)となる。nのすべての最大公約数について同様に考えると、n=∑d∣nϕ(ad)が分かる。ndはnの約数であるから(最大公約数ではないが)、目標の式がわかる。
コメント