約数

質問

2^2010－1の約数で小さいものから4番目 6番目の約数は何ですか？

回答No.3

alice_44

素朴に、ひとつひとつやってみよう。

まず、2^2010 - 1 は奇数だから、偶数は約数にならない。

1 は、もちろん約数。１番目

3 が約数かというと…　2 のベキを mod 3 で考える。
順に 2 倍していくと 1 → 2 → 4 ≡ 1 だから、
1,2,1,2,… と周期 2 で繰り返す。よって、2^2010 = 2^(2・1005) ≡ 1。
2^2010 - 1 ≡ 0 であり、3 で割りきれる。２番目

5 が約数かというと…　2 のベキを mod 5 で考える。
順に 2 倍していくと 1 → 2 → 4 ≡ -1 だから、
1,2,-1,-2,1,2,-1,-2,… と周期 4 で繰り返す。よって、2^2010 = 2^(4・502+2) ≡ -1。
2^2010 - 1 ≡ -2 であり、5 では割りきれない。

7 が約数かというと…　2 のベキを mod 7 で考える。
順に 2 倍していくと 1 → 2 → 4 → 8 ≡ 1 だから、
1,2,4,1,2,4,… と周期 3 で繰り返す。よって、2^2010 = 2^(3・670) ≡ 1。
2^2010 - 1 ≡ 0 であり、7 で割りきれる。３番目

9 が約数かというと…　2 のベキを mod 9 で考える。
順に 2 倍していくと 1 → 2 → 4 → 8 ≡ -1 だから、
1,2,4,-1,-2,-4,… と周期 6 で繰り返す。よって、2^2010 = 2^(6・335) ≡ 1。
2^2010 - 1 ≡ 0 であり、9 で割りきれる。４番目！

11 が約数かというと…　2 のベキを mod 11 で考える。
順に 2 倍していくと 1 → 2 → 4 → 8 → 16 ≡ 5 → 10 ≡ -1 だから、
1,2,4,8,5,-1,-2,-4,-8,-5,… と周期 10 で繰り返す。よって、2^2010 = 2^(10・201) ≡ 1。
2^2010 - 1 ≡ 0 であり、11 で割りきれる。５番目

13 が約数かというと…　2 のベキを mod 13 で考える。
順に 2 倍していくと 1 → 2 → 4 → 8 → 16 ≡ 3 → 6 → 12 ≡ -1 だから、
1,2,4,8,3,6,-1,-2,-4,-8,-3,-6,… と周期 12 で繰り返す。よって、2^2010 = 2^(12・167+6) ≡ -1。
2^2010 - 1 ≡ -2 であり、13 では割りきれない。

15 が約数かというと…　5 が約数でないからダメ。

17 が約数かというと…　2 のベキを mod 17 で考える。
順に 2 倍していくと 1 → 2 → 4 → 8 → 16 ≡ -1 だから、
1,2,4,8,-1,-2,-4,-8,… と周期 8 で繰り返す。よって、2^2010 = 2^(8・251+2) ≡ 4。
2^2010 - 1 ≡ 3 であり、17 では割りきれない。

19 が約数かというと…　2 のベキを mod 19 で考える。
順に 2 倍していくと
1 → 2 → 4 → 8 → 16 → 32 ≡ 13 → 26 ≡ 7 → 14 → 28 ≡ 9 → 18 ≡ -1 だから、
周期 18 となる。よって、2^2010 = 2^(18・111+12) ≡ -8。
2^2010 - 1 ≡ -9 であり、19 では割りきれない。

21 が約数かというと…　3 と 7 が約数だからｏｋ。６番目！

回答No.2

tmpname

この問題では、約数を小さい方から見つけていくのも必要ですが、
それ以外の数が確かに「約数でない」こともきちんと証明して
いかないと答えになりません。

準備として、今、明らかに1は2^2010-1の約数です。
そして2^2010-1は明らかに奇数なので、残りの約数も
全部奇数のはずです。よって、小さい奇数から順に
2^2010-1を割り切るか調べて行けばいいです
（約数と同時に「約数以外の数」も調べる必要があります）

そこでEulerの定理の助けを借ります。
「a, nを互いに素な正整数とした時、
　a^(φ(n)) ≡ 1 (mod n), ただしφ(n)は、Euler関数で
　n以下でnと互いに素な正整数の数」
nが奇数ならば2とnとは互いに素な事にも注目して
起きます。

例 11は2^2010-1の約数か
φ(11) = 10で 2010 ≡ 0 (mod 10)
よって 2^2010 ≡ 2^0 = 1 (mod 11)であり、 2^2010 - 1は
11 で割りきれる
例 13は2^2010-1の約数か
φ(13) = 12で、2010 ≡ 6 (mod 12)
よって 2^2010 ≡ 2^6 = 64 ≡ 12 (mod 13)より
2^2010 -1 を13で割ると11余る

といった感じで順にやって行きましょう。

答えは書きませんが、結果として6番目の約数は25以下の奇数
なので（25かどうかは書きません）そんなに大変では
ありません。

回答No.1

Yodo-gawa

どこをどう考えたのかを書きましょう。
考え無しに丸投げしても身につきません。

少なくとも自力でどこまでやったかを記載するべきです。
アホでも分かるのは、奇数だから最小の約数は1ということです。

(2^2010)-1=(2^1005+1)(2^1005-1)

また、a^（n）+b^（n）でnが奇数の場合、(a+b)を因数に持つ。
即ち、2^(奇数)+1は、3を約数に持ちます。

次に、連続する奇数の積が3の倍数である場合は・・・

こんな感じで考えていきましょう。ヒントはここまでです。