redcat_math https://blog.hatena.ne.jp/redcat_math/ Red cat の数学よもやま話 https://redcat-math.hatenadiary.org/ 数学・代数 フェルマー(Fermat)の小定理、と言うものをご存知でしょうか。それは p を素数とするとき、p と互いに素な整数 a に対して と言うものです。 さて、ある自然数が素数かどうか判定する方法として「エラストテネスの篩(ふるい)」と呼ばれる方法は有名ですが、これはアルゴリズムとしては合理的な方法ではありません。そこで実際には、フェルマーの小定理を利用して、ある自然数 n と、n と互いに素な整数 a を取ってきて が成り立つとき、これは「素数ではない」と判定する方法(フェルマーテスト)が使われます。しかし「逆必ずしも真ならず」の言葉どおり、この方法では実際には素数でないものがチェック漏れする可… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fredcat-math.hatenadiary.org%2Fentry%2F20060301%2F1141188885" title="擬素数とカーマイケル数 - Red cat の数学よもやま話" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2006-03-01 13:54:45 rich https://redcat-math.hatenadiary.org/entry/20060301/1141188885 1.0 100%