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