証明.k が p で割り切れるとき, kn−k は p の倍数.k が p で割り切れないとき,フェルマーの小定理から,kn≡k(modp) となるので,この場合も kn−k は p の倍数.p≤n より,f(p,n)=pn−p は g(n) で割り切れる.pn−p は p で丁度一回割り切れるため,補題が示される.
補題2.p を素数であって, n−1 が p−1 で割り切れないものとすると,g(n) は p で割り切れない.
証明. 以下の場合分けによって示される.
p≤n! のとき modp での原始根を一つとり, r とする.r≤n! となるように取ることができ,条件より n−1 を p−1 で割った余りを t とすると,t は 0 でないため,rt≡1(modp) であり,フェルマーの小定理と合わせて,rn≡rt+1(modp) となるため,f(r,n) は p で割り切れない.したがって,g(n) は p で割り切れない.
p>n! のとき f(2,n)=2n−2≤n!<p となるため,f(2,n) は p で割り切れず,したがって g(n) は p で割り切れない.
補題1と補題2により,以下を得る.
g(n)=p−1∣n−1p:prime∏p⋯(1)
補題3. 任意の素数 p に対して,Mp=⌊p−1107−1⌋ である.
証明g(2),…,g(107) の中で p で割り切れるものの数は,(1)式より,1,…,107−1 の中にある p−1 の倍数の個数と一致する.これは ⌊p−1107−1⌋ と計算できる.