blog2011年7月31日日曜日カーマイケル数の列挙カーマイケル数を列挙してみる。カーマイケル数といえば、フェルマーテストの偽陽性を引き起こすクセモノ。カーマイケル数を列挙しておけば、フェルマーテストと併用することで、正確な素数判定ができる。返し二乗法など基本的な数学系処理の練習にいいかも。問題のカーマイケル数の部分だが、カーマイケル関数を使って、となる最小のmを求める。このmをλ(n)と表記する。ここで、aとnはcoprimeである。カーマイケル数は、となるnなので、(n-1)がλ(n)で割り切れるとき、nはカーマイケル数の候補となる。ここから素数を除く必要がある。n-1となるので、それを除けばいい。n-1となり、この除去で偽陰性となることはない。75361...と続く。拡張ユークリッド互除法について蟻本を見ていると、以下のような文章がでてくる。y)を求める問題に他ならない。自分にとっては明らかじゃなかったので、ちょっと考えてみた。y)が存在しないことを背理法で示す。d)であるため、矛盾。