サラリーマンのすらすらIT日記

IT関連を中心とした日々を綴ります。
--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
2014/02/27

1729はカーマイケル数でもある

与えられた整数nが素数であるかどうかは、nを超えない素数でnを割ってみればよい。いずれの素数でも割り切れなかった時に、nは素数であるといえます。ただこれはnが非常に大きな整数の場合、莫大な計算量を必要とします。そこで素数判定法なるものがあります。それほど計算量が多くない方法で計算してみて、それに合格すれば高い確率で素数であると判断するもの。有名なのが「フェルマー・テスト」。フェルマーの小定理「nが素数であれば、nと互いに素である整数aに対して、an-1 ≡ 1 mod nが成り立つ」という性質を使って、逆にこの合同式が成り立てば、高い確率でnは素数であろうと推定できるというものです。

厄介なのは、フェルマーの小定理の逆が一般に成り立たないこと。つまりnが素数でなくてもこの合同式が成り立つことがあります。例えば、91は素数ではありませんが(=7×13)、

390 ≡ 1 mod 91

となるから。もっとも

290 ≡ 64 mod 91

なので、素数でないことがわかります(91くらいの小さい数なら、上記の合同式の計算の方が大変だが)。

さらに厄介なのが、nが素数でないにもかかわらず、nと互いに素なすべてのaに対して、an-1 ≡ 1 mod nが成り立つケースがあること。これではこの素数判定法は使えません。このような整数をカーマイケル数といいます。カーマイケル数は無数に存在することがわかっており、小さいものから列挙すると561,1105,1729,2465,...となります。

ここで気が付くのが「1729」タクシーと2つの3乗数の和で紹介した1729です。1729は2つの整数の3乗数の和として2通りに表すことができる最小の数であると同時に、カーマイケル数でもあるわけです。これは面白い。

スポンサーサイト

コメント

コメントの投稿

  • URL
  • コメント
  • パスワード
  • 秘密
  • 管理者にだけ表示を許可する

トラックバック

トラックバックURL:http://sookibizviz.blog81.fc2.com/tb.php/1849-da2b139e

■  カレンダー

07 | 2017/08 | 09
- - 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 - -

■  プロフィール

sookibizviz

Author:sookibizviz
仕事の内容やソフトの紹介を交えながら、日々の悪戦苦闘を綴っていきます。

■  最新記事

■  最新コメント

■  最新トラックバック

■  月別アーカイブ

■  カテゴリ

未分類 (64)
BizViz (24)
IT (1119)
計量 (76)
環境 (26)
数学 (181)
ニュース (46)
本 (187)
音楽 (113)
囲碁 (5)
将棋 (26)
ブログ (14)
日記 (19)

■  FC2カウンター

■  検索フォーム

■  RSSリンクの表示

■  QRコード

QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。