素数か否かの粗い判定法

「変わらない」ことは意味をもたない気もするかもしれませんが、 そうではありません。

$p$ が素数なら、 $2^p \mod p=2$ でないといけないし、 $3^p \mod p=3$, $4^p\mod p=4$, $5^p \mod p=5$, $\dots$, でないといけない。 あとで少しだけ触れるように、べき乗は比較的短時間で計算できるので、 このことは$p$ が素数か否かの粗い判定法を与えます。 たとえば、 $2^p \mod p \neq 2$ であればただちに $p$ が素数でないことがわかるというわけです。