kt3k 日記

スポンサーサイト

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

食事

hiroseクンと佐藤君と久しぶりに食事に行った。

2047 = 23 * 89 (= 2^11 - 1)

という素因数分解の素晴らしさを教えてもらった。あと、

10001 = 73 * 137

という素因数分解は数論を使って速く出来ることを教えてもらった。

関連:メルセンヌ数

-----

10001 の 素因数を p とすると、p は 8 で割って 1 余る。

理由:
  p は 10001 を割り切るので、10000(=10^4) を割ると p - 1 余る。合同式で書くと、

  10^4 ≡ -1 mod p

  両辺2乗して、

  10^8 ≡ 1 mod p

  このとき 10 の位数は 1 2 4 8 のどれかになるが、10^4 ≡ -1 なので、
  位数 1 2 4 は無理なので、位数は 8。

  フェルマーの小定理から、

  10^(p-1) ≡ 1

  なので、これと、10 の位数が 8 であることより、p-1 は 8 の倍数。
  したがって、p は 8 で割って 1 余る。

この事実を知っていれば、10001 を因数分解するとき、8 で割って 1 余る素数について
だけ割れるかどうか調べればいいので、

  9 素数じゃない 17 割れない 25 33 素数じゃない 41 割れない
  49 57 65 素数じゃない 73 割れた!

という手続きで素因数分解できる。(これを知らないと、13 19 23 29 31 ... と、
いろんな素数で割り算を試すことになる。)

コメント


管理者にだけ表示を許可する
 

 

トラックバック

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