高校数学の質問スレPart408

高校数学の質問スレPart408at MATH

高校数学の質問スレPart408 - 暇つぶし2ch996:ﾈ意味でいってるとすれば一筋縄ではないかない問題だろうそもそも桁区切りで倍数の判定をすることは必ずしも計算量を小さくするのだろうかしかしながら単に「桁くぎりで倍数判定できる」という意味なら 10と互いに素な任意の自然数は必ずそのような判定を持つ : Mを10と互いに素な整数M＞1としようある正の整数nが存在して 10^n≡1 (mod M)となるこのとき Mの倍数判定法はn桁区切りで可能である以下は具体例である要望どおり合成数であり,ゾロ目でないものだけ 4桁区切り → 303, 909 5桁区切り → 123, 369, 813, 2439 6桁区切り → 21, 39, 63, 91, ... (たくさんあるので略) 7桁区切り → 717, 2151, 13947, 41841 ... 一般には 10^n-1(n＞1)の形の数を素因数分解することで条件を満たすn桁区切りで判定できる新しい数を必ず選ぶことができる (もし合成数とかゾロ目とかいうこだわりがないなら約数全部取ってくれば十分)

次ページ

続きを表示

1を表示