カーマイケルの定理
$ ^{\forall a\in(\Z/n\Z)^\times}[a^x\overset n\equiv1] を満たす最小の$ x=\lambda(n)を求める定理
オイラーの定理より$ x=\varphi(n)とすれば式を満たすが、コレは最小とは限らない なお、$ ^{\exist a\in(\Z/n\Z)^\times}\lbrack a^{x(a)}\overset n\equiv1\rbrackを満たす最小の$ x(a)は$ \lambda(n)となるとは限らない
$ n=\prod_{p\in\mathbb P|n}\hat p\quad(\hat p=p^{w_p})と素因数分解できるなら $ \lambda(n)=\lambda\left(\prod_{p\in\mathbb P|n}\hat p\right)=\underset{{p\in\mathbb P|n}}{\rm lcm}\lambda(\hat p)
$ \lambda(\hat p)=\phi(\hat p)\quad(p\in\mathbb P_{\ge3})
$ =\frac{\hat p}{p}(p-1)
$ \lambda(\hat 2)=\begin{cases}\hat2/4&(\hat 2\ge8)\\2&(\hat 2=4)\\1&(\hat 2=1)\end{cases}
$ a^{p-1}\overset p\equiv1より
$ a^{n-1}\ \overset n{\not\equiv}\ 1なる数$ aが見つかったら$ nは素数ではないと返す
いくつかの$ aでこれを通過したら$ nは確率的に素数であろうと返す
$ a^{\lambda(n)}\overset n\equiv1
$ \lambda(n)が$ n-1の約数なので$ a^{n-1}\overset n\equiv1となって、フェルマー素数判定法に通ってしまう