nに関する数学的帰納法で示す
n=1のとき明らか
n＜mとなるときn|a(n)となると仮定する。

n=mのとき
mが素数ベキのときは補題4より正しい

mが素数のベキではないとき
pをmの素因数とすると、m=p^h*s　(ただし、sはpで割り切れない自然数)と書ける
a(m)=2^(p^h*s)-2^{p^(h-1)*s}-農[p^h，w＜m]a(w)
補題4より2^(p^h)-2^{p^(h-1)}はp^hで割り切れる、したがって補題1より2^(p^h*s)-2^{p^(h-1)*s}もp^hで割り切れる。
帰納法の仮定より、a(w)はwで割り切れるので、a(w)はp^hで割り切れる。
したがって、a(m)はp^hで割り切れる。･･･※
mの任意の素因数pで※がいえるので、a(m)がmで割り切れることもいえる。
よってmが素数のベキでないときもm|a(m)がいえた。

以上より任意の自然数nに対して、n|a(n)がいえた。