この証明も群の言葉を使います。

証明

n が素数のときには a を mod n の原始根とすればよい。 逆に条件を満たす a があるとし, p を n の素因子とする。 d を a mod p の位数とすれば a(n-1)/2 ≡ -1 mod p   であるから d は (n - 1)/2 を割りきらない。 d は (n - 1) を割りきる。 d は p - 1 を割りきる。 ---> d は h 2k-1 を割りきらない。 d は h 2k を割りきる。 d は p - 1 を割りきる。 以上より 2k は d を割りきり, 更に p - 1 を割りきる。よって p = x 2k + 1   と書ける。 n ≡ p ≡ 1 mod 2k   となるから n = pm とすれば m ≡ 1 mod 2k。よって n = (x 2k + 1)(y 2k + 1) 　　 (x > 1, y > 0)   となる。このとき n - 1 = 2k(xy 2k + x + y)   従って h = xy 2k + x + y   ところが条件より h < 2k であるから y = 0。よって n = p。