一般に2集合 X,Y について X=(Y∩X)∪(Y\X) と書ける。
同様に2自然数 a≤n について
a=
gcd(n,a)*
(n/gcd(n,a)と互いに素な数)
と一意に書ける。
例: n=12 のとき
3 =
3*
1,
8 =
4*
2,
5 =
1*
5,
など
a を 1 から n まで動かしたとき、
gcd(n,a) の値は n の各約数 d をとり、
(n/dと互いに素な数)
は各 d に対して φ(n/d) 通りある。
例: n=24, d=
3 のとき、
24とのGCDが
3である数 a は4個ある。
各 a を
3で割ると、
24/3=8と互いに素な数が出る。
その個数 (4個) が、 φ(24/3)=φ(8) に対応している。
つまり n の約数
d と、
(n/dと互いに素な数) (φ(n/d)個) の組み合わせが、
1 から n までの数と1対1に対応している。
よって Σ
(d: nの約数)φ(n/d) = n
d が n の約数を動くとき、 (n/d) も n の約数を1回ずつ取るので、
Σ
(d: nの約数)φ(d) = n も成り立つ。