第５話 リュカテスト
リュカテストとは、
数列
を
で定義するとき、
が
で割り切れるとき、は素数であるというものです。何言ってるか分からない？
ですよね。
具体例がないと分かりませんよね。
は
で割り切れます。このとき、
＝７は素数だという判定方法です。さらに、
は
では割り切れませんから
＝１５は素数でないというわけです。次も見てみましょう。
は
でわりきれますから、
＝３１が素数というわけです。尚、実際のリュカテストの運用は、
を使います。
２番目の式は、
をで割ったときの余りを
の値とするという意味です。これは
という整数の性質を使っています。
ａとｂの両者をｐで割ったときの余りが等しいとき、
ａとｂはｐを法として合同であるといい、
と表記します。この表記法を使うと先の性質は、
と表すことが出来ます。
ａｂをｐで割ったときの余りを計算するには、
をｐで割ったときの余りを計算する方が楽です。例えば、
１７÷３＝５・・・２
５２÷３＝１７・・・１
１７×５２を３で割ったときの余りを計算するには
２×１＝２を３で割った余りを計算すればよく、
それは２です。
実際に、
１７×５２＝８８４
８８４÷３＝３９４・・・２
ですね。
８８４を３で割った余りを計算するより、
２×１＝２を３で割った余りを計算する方が遙かに楽です。
を使って、
＝３１が素数であることを確認するには、
でよいことになります。
３１で割り切れるということは、
余りが０であるということでしたね。
では、このリュカテストを利用して完全数を求めるプログラムを
作りましょう。
では、リュカテストを利用して
を実現するマクロを作って下さい。
