あまり

質問

10^n-1と表せる数(nは自然数）のうち１９で割り切れる最小の数は何かという問題で、
10^19-10を19でわったあまりは0ということから10^18-1は１９で割り切れるというところまでは出るのですが、これが最小であることの確認で、nが１８の約数の場合を確認することと教科書に書いてあるのですが、なぜ１８の約数なのでしょうか？

回答No.5

Tacosan · ベストアンサー

すみません, #4 の最後の部分はおかしいです. もうちょっというと, 書いてあることそのものは結果的に正しいんだけど説明としては不適切.

9 は素数ではないので, 法として使うときには指数を 8=9-1 としちゃダメで, 「互いに素な整数の個数」を表すオイラー関数 φ により φ(9) = 6 を指数に使う必要があります. で, 指数を 6 とすれば当然そのあとの 3 も (6 の約数だから) 不適格で, 4 または 5 としなければなりません. 言い訳をすると, もともとは 37 を使おうとしてたんですよ....

ちなみに
「互いに素であることが必要ってことですか」
とか
「ああ違いますね」
についてはあまりにも書いてあることが少なすぎ, 特に「何のために」がまったく書かれていないのでコメント不能.

回答No.4

Tacosan

微妙に怪しいところはあるけど, 基本的にはその通り.

とりあえず
・10^m-1 を 10^n-1 で割った余りは 10^r-1 の形になる
・このとき r は「m を n で割った余り」である
ということは確認しておいてください. これを使えば, #2 から
1. 10^18-1 は 19 で割り切れる
2. 10^d-1 は 19 で割り切れる (かつこのような形の数のうち最小であると仮定する)
3. よって「10^18-1 を 10^d-1 で割った余り」も 19 で割り切れる
4. 「10^18-1 を 10^d-1 で割った余り」は 10^r-1 (r は 18 を d で割った余り) である
5. 当然 10^r-1 は 19 で割り切れる
6. r は 0 じゃないと (r < d, つまり 10^r-1 < 10^d-1 で) 2 に反するので困る
7. だから d は 18 の約数
とできます.

最初に「微妙に怪しい」と書いたのは, 「最小」が重要だってことに気づいているかどうかが読めないからです. 19 では「最小」をつけなくても結果的には問題にならない (10^18-1 より小さいと 19 で割り切れないから) のですが, ほかの数では痛いことになります. わかりやすいのは 9 のときで,
・10^8-1 は 9 で割り切れる
・10^3-1 は 9 で割り切れる
・でも 3 は 8 の約数ではない
ということが起きます. この問題点はほぼ自明でしょう.

お礼

10^n-1と問題の数（ここでは１９）が互いに素であることが必要ってことですか？

補足

ああ違いますねｗ　ごめんなさい

回答No.3

Tacosan

「桁数が合わないとってことですか」というのはどういう意味でしょうか? 「桁数が合わないと」と「ってこと」の間におそらくあるであろう言葉を省略せず書いてもらえませんか?

お礼

すべての桁が９になるので、桁数が１８の約数でないと、（たとえば999 999 999 999 999 999 を　99999 など）でわるとどうやっても桁数が合わなくなってしまうので割り切ることができないということですよね？　感覚ではわかったのですがうまく言葉にできません。。。

回答No.2

Tacosan

10^n-1 という形の数で 19 で割り切れる最小のものを 10^d-1 (d≧1) として, これで 10^18-1 を割ればいい. d が 18 の約数でなければ余りが出ちゃうよね.

さあがんばれ.

お礼

普通に全桁９になるから桁数が合わないとってことですか？

回答No.1

Tacosan

その他は調べるだけ無駄だから.

お礼

なるほどー　なぜnが１８の約数のときにしか１９で割れる可能性がないか教えてもらえますか？