カーマイケル数

パッケージJava製品開発担当の大です。こんにちは。

前回、確率的素数判定法のひとつであるフェルマーテストの話を書きました。その中で、フェルマーテストを高い確率で騙す合成数「カーマイケル数」というものがある、という話が出てきました。
今回は、そのカーマイケル数について書きます。

カーマイケル数

カーマイケル数は、Wikipediaによると、

自身と互いに素である任意の底でフェルマーテストを通過する合成数

というものだそうです。

カーマイケル数のひとつ、561を例にとって、調べてみます。
まずは前回のプログラムを使用して、n = 561のときにan-1 ≢ 1 (mod n)となる（つまりnは合成数であると正しく判定する）a（2 <= a < n）を羅列してみます。

$ gs -dNODISPLAY -q is-prime.ps
GS>/x 561 def
GS>/witnesses [2 1 x 1 sub {dup x 1 sub x expmod 1 eq {pop} if} for] def
GS>witnesses ==
[3 6 9 11 12 15 17 18 21 22 24 27 30 33 34 36 39 42 44 45 48 51 54 55 57 
60 63 66 68 69 72 75 77 78 81 84 85 87 88 90 93 96 99 102 105 108 110 111 
114 117 119 120 121 123 126 129 132 135 136 138 141 143 144 147 150 153 
154 156 159 162 165 168 170 171 174 176 177 180 183 186 187 189 192 195 
198 201 204 207 209 210 213 216 219 220 221 222 225 228 231 234 237 238 
240 242 243 246 249 252 253 255 258 261 264 267 270 272 273 275 276 279 
282 285 286 288 289 291 294 297 300 303 306 308 309 312 315 318 319 321 
323 324 327 330 333 336 339 340 341 342 345 348 351 352 354 357 360 363 
366 369 372 374 375 378 381 384 385 387 390 391 393 396 399 402 405 407 
408 411 414 417 418 420 423 425 426 429 432 435 438 440 441 442 444 447 
450 451 453 456 459 462 465 468 471 473 474 476 477 480 483 484 486 489 
492 493 495 498 501 504 506 507 510 513 516 517 519 522 525 527 528 531 
534 537 539 540 543 544 546 549 550 552 555 558]

あれ、意外にたくさんあります。。

互いに素

あ、大事なことを忘れていました。561と互いに素でないaは省かなきゃならないですね。
というわけで、互いに素かどうかを判定するプログラムを追加します。

• are-coprime.ps

% m n gcd
% mとnの最大公約数を求めます
% （m >= n である必要があります）
/gcd {
    0 dict begin
        /n exch def
        /m exch def
        n 0 eq {
            m
        } {
            n m n mod gcd
        } ifelse
    end
} def


% m n are-coprime?
% mとnが互いに素であるかどうかを判定します
/are-coprime? {
    2 copy lt {exch} if gcd 1 eq
} def

オーソドックスにユークリッドの互除法を使用して、二つの数の最大公約数を求め、それが1なら互いに素である、と判定します。

さきほど求めたwitnessesから、561と互いに素でない値を排除してみます。

GS>(are-coprime.ps) run
GS>/witnesses [witnesses {dup x are-coprime? not {pop} if} forall] def
GS>witnesses ==
[]

witnessesは空になりました。つまり、カーマイケル数561が合成数であると正しく判定できる、561と互いに素なaは無いということなんですね。

試してみたところ、1105、1729、2465、2821、6601、8911（Wikipediaに載ってたカーマイケル数の例）もすべて同様の結果になりました。カーマイケル数の定義を見れば当然のことなんですが、面白いものです。