コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

利用者:3236kk/sandbox

このページは完全に個人的に使用しています。かなりお見苦しいところが多いとは思いますが、ご容赦ください。

したいこと

[編集]
  • 本のページ作成
  • ユーザーボックスをメインに入れる
  • その他

リンク

[編集]

以下書き途中の項目

1001チェック(せんいちチェック)は、試し割り法で暗算で素数判定、または素因数分解するときに使うテクニックの1つである。1001の素因数分解が7 × 11 × 13であることを用いて、これら3つの素数で割ることができるかを通常より速く確認することができる。

方法

[編集]

自然数Nを素因数分解するとする。

  1. 2, 3, 5までは通常通り割れないか確認する。
  2. 以下の操作をNが3桁の整数になるまで繰り返す。
    • Nから1001の倍数を引く。
    • Nを7, 11, 13のいずれの倍数でもない数で割る。(実際は10で割ることが多い。)
  3. 得られた数に対して、7, 11, 13で割ることができるか確認する。割ることができたなら、Nもその数で割ることができることになる。

例えば、35581という数を素因数分解する場合、2, 3, 5で割れないことを確認したのち、1001の倍数である31031を引く。得られた4550を10(7, 11, 13のいずれの倍数でもない)で割り、455を得る。これは7, 13で割れる。つまり、35581は7及び13の倍数であることがわかる。その後は通常通り素因数分解していくと、35581 = 7 × 13 × 17 × 23という素因数分解を得る。

原理

[編集]

この方法は、 整数の合同の性質を利用している。具体的には、

  • N ≡ N - ab (mod b) (N, a, bは自然数)
  • N ≡ N / a (mod b) (N. bは自然数、aはbの約数でない自然数)

という性質を利用している。