ニコニコ大百科モバイル

7/2(月)よりスマホまたはPCでアクセスした場合、各デバイス向けのサイトへ自動で転送致します


フェルマーの小定理


ヨミ: フェルマーノショウテイリ
掲示板をミル!
10カキコ!

フェルマーの小定理とは、フェルマー明しなかった定理である。


概要


p を素数とし、a を p と互いに素な整数とすると次の式が成り立つというもの。

ap-1 1 (mod p)

(mod p)はpで割った時の余りが等しいという意味。この定理の逆は成り立たない、がそんなに気にするほどでもないので確率素数判定に用いられている。

「小」定理があるなら「大」定理はどこ? と思う人もいるかもしれない。大定理フェルマーの最終定理のことで、これと区別するために小定理と呼ばれている。ちなみに最終定理よりも小定理のほうがいろいろと応用範囲が広く、素数剰余を扱う問題では頻出の定理である。

このフェルマーの小定理を拡したオイラー定理オイラー定理をさらに拡したカーマイケルの定理が存在する。


例題


21841を19で割った余りめよ。


答え


21841 25 13 (mod 19)


関連項目



最終更新日: 16/10/24 04:05
タグ検索 パソコン版を見る


[0]TOP
ニコニコ動画モバイル
運営元:ドワンゴ