が奇素数のときであることを示す。
以下、で考える。
がの倍数となる…(*)。
ここで、あるについてであるから、をで割った余りの分布は独立かつ一様である。
(i) のとき
(*)はと同値であり、そのようになる確率は。
(ii) のとき
であるから、とは互いに素。よってが存在する。
(*)はと同値であり、そのようになる確率は。
(i),(ii)より示された。
これよりである。
が奇素数のときであることを示す。
以下、で考える。
がの倍数となる…(*)。
ここで、あるについてであるから、をで割った余りの分布は独立かつ一様である。
(i) のとき
(*)はと同値であり、そのようになる確率は。
(ii) のとき
であるから、とは互いに素。よってが存在する。
(*)はと同値であり、そのようになる確率は。
(i),(ii)より示された。
これよりである。