素数のとき二乗した結果が≡1になるのは、もとの数が≡1または≡-1のときに限られる。したがって最後の項よりひとつ手前の項は≡1または≡-1である。≡-1なら証明は完了する。同じ議論によってそのまた前の項は≡1または-1である。このようにしてどこかで≡-1になれば証明は完了する。なければ、そのまた前そのまた前と進んでついにいちばん最初の項までぜんぶ≡1ということになる。以上がまさに示したいことであった。互いに素なら何でも良い。いう事実は使っていない。そもそもテストの意味がない。大きな(例えば100桁の)整数なので、大きい底は計算量的にも現実的でない。与えられたときに上のような数列を作るとする。最初の項が≡1になったら、以下計算するまでもなくぜんぶの項が≡1になるのでその数は合格。最初の項か途中の項で≡-1が出たら、それも合格で、そこで計算をやめていい。他方、最後の項のひとつ手前まできても≡-1が一度も現れない場合、その時点でミラーテスト失格となる。絶対にミラーテストに合格できない。それだけではまだ充分でない。フェルマーテストで落ちる数に対してはミラー数列のどこにも1が現れないのだから、必要最低基準さえ満たさず、お話にならない。これはフェルマーテストに合格できることを意味している。したがってフェルマーテストに合格できない数はミラー数列に1が現れず、当然にミラーテストにも合格できない。ミラーテストにかけるとほとんどふるい落とされる。最初に1が現れる項のひとつ前の項は≡-1であることを要求される。±1でないものを二乗して≡1になる、などというのは素数を法とする秩序正しい世界では起こり得ないからである。初項からすでに1の場合、この性質についての検証を行うことができない。素数でないにもかかわらずミラー数列で初めて1が現れる場所のひとつ手前がたまたま≡-1ということが考えられる。と合同になるのは確かだからだ。確定できるわけではない。言っても、素数でないくせにミラーテストをあざむくのは相当に難しい。「Znに非自明な1の平方根がある」というしっぽを出さないようにしなければならないからだ。フェルマーテストをあざむく擬素数であっても「非自明な1の平方根の存在」をさらけだし、化けの皮がはがれる。これに対して、フェルマーテストの場合、底をいろいろ変えても素数のふりをし通せるような「とんでもないニセ素数」が存在するのである。その一億分の一の検査すら非現実である。ミラーテストまでしなくても、フェルマーテストでも、充分に実用的ではある。フェルマーテストをあざむくような擬素数そのものがかなりまれだからだ。ミラーのテストに合格する数は、強力な素数候補と呼ばれる。強力な素数候補と認定される数のほとんどすべては実際に素数である。実際には素数でないのに強力な素数候補にノミネートされてしまうようなずうずうしい数を強擬素数(きょうぎそすう)という。ホントは素数でないくせにあくまでシラをきりつづける強力なニセ素数である。素数に生まれたかったのであろう......。強擬素数は、フェルマーテストは余裕で合格してしまう。ミラーテストはフェルマーテストの強化版なので当然のことだ。同様に、強力な素数候補は、フェルマーテストによっても素数候補となる。強擬素数は擬素数でもあるが、もちろん逆にすべての擬素数が強擬素数であるわけではない。素数ではないがフェルマーテストによって素数候補となる擬素数である。ミラーテストは通過できない。相当し、フェルマーテストにあたる。確かに剰余1を返し、素数候補だ。いう「変な」値になっているのでミラーテストで、はねられてしまう。対するミラーテストを試してみよう。