高校数学、整数問題

（問題）
６０以下の自然数で、６０と互いに素なものの個数をｎとする。
（１）ｎを求めよ。
（２）１７＾（ｎ）を６０で割った余りを求めよ。
（疑問）
自分は（１）は１から６０のうち２の倍数または３の倍数または５の倍数を除いた個数をもとめて、ｎ＝１６
（２）は１７＾（１６）を合同式で考えていってあまり１を求められ、正解でした。
しかし、大学への数学の解答を読むと、解説の部分でよくわからない部分がありました。まだ初心者なので、教えて下さい。
（解説）
（１）同様に解いています。
（２）（１）の１６個の数
１，７，１１，１３，１７，１９，２３，２９，３１，３７，４１，４３，４７，４９，５３，５９を順にa(1),a(2),a(3),,,a(16)とする。a(5)=17である。
いま、これら１６個の数にそれぞれ１７(a(5))をかけた数a(1)a(5),a(2)a(5),,,a(16)a(5)を考える。
これら１６個の数を６０で割った余りはすべて異なる。
（もし同じものがあるとき、a(k)a(5),a(l)a(5)（ｋ＜ｌ）とすると、（a(l)-a(k))a5=60nとなり、６０とa5は互いに疎だから（a(l)-a(k))が６０で割り切れることになり、この数が６０よりも小さいという事実に反する）
また、a(1)a(5),,,a(16)a(5)まではすべて６０と互いに素だからこれら１６個を６０で割った余りはa(1),a(2),,,a(16)全体に一致する（順番は異なる）
以上より、a(1)a(5)×a(2)a(5)×、、、×a(16)a(5)-a(1)a(2),,,a(16)=a(1)a(2),,,a(16)(a(5)^16-1)は６０で割り切れるが、a(1)a(2),,,a(16)は６０と互いに素なので、a(5)^16-1は６０で割り切れる。
よって余りは１．
（疑問点）a(1)a(5),,,a(16)a(5)まではすべて６０と互いに素だからこれら１６個を６０で割った余りはa(1),a(2),,,a(16)全体に一致する（順番は異なる）という部分の理由がよくわかりません。
教えて下さい。（きちんとした証明と感覚的な説明どちらもいただけると嬉しいです。なければ、きちんとした証明だけでもお願いします。）

質問者からの補足コメント

• 

  a(1)a(5),,,a(16)a(5)まではすべて６０と互いに素だからこれら１６個を６０で割った余りはa(1),a(2),,,a(16)全体に一致する（順番は異なる）という部分
  は実際に計算すると、確かに全体として、a(1)a(2),,,a(16)のそれぞれの余りを網羅するのが確認できたのですが、
  どうしてこのようなことが成り立つのかが全く分かりません。

  No.1の回答に寄せられた補足コメントです。 補足日時：2015/09/21 01:03

• 

  一般に 2つの整数 a と b が互いに素なら
  ax + by = 1
  となるような整数 x, y が存在する (これはユークリッドの互除法から示せる). 今の場合だと
  17x + 60y = 1 であるような x, y が存在する
  ということになる.（ここまではわかったのですがここからなぜ次の文が言えるのかがわかりません教えて下さい。） これから
  a(i)a(5) = a(j)a(5) なら a(i) = a(j)

  No.2の回答に寄せられた補足コメントです。 補足日時：2015/09/21 04:36

• １週間以上間が空いてしまって申し訳ございません。
  ＮＯ３さんの回答を読んでも腑に落ちない部分がありました。それはある事項が頭の中にあり、それとの関連が気になったからでした。自分が考えたことを書きたいので、どなたか誤りである点があればご教授いただけると幸いです。
  ★（事項）一般に、ｐ、ｑが互いに素なとき、
  ｐ×１、ｐ×２、、、、ｐ×ｑ（全部でｑ個）は全てｑで割った余りが異なります。そして、その全体は｛０，１、、、ｑ－１｝と全体として一致します。
  ★について、ｐ＝１７、ｑ＝６０とすると、
  Ｐ＝｛１７×１、１７×２、、、、１７×６０｝を６０で割った余りは全体とて、Ｑ＝｛０，１、、、５９｝と一致します。
  このＰの６０個のうち、６０と互いに素なもの同士をかけたＲ＝｛１７×１、１７×７、、、１７×５９｝（１６個）は全体として、Ｓ＝｛１，７、、、５９｝（１６個）と一致するのはなぜか？（続）

    補足日時：2015/09/30 07:10

• ということの理由をかんがえたいのですが、その理由は
  互いに素な２数a,bについて、ab=60k+rとあらわした時に、ｒがもし、６０と１以外の公約数を持てば、両辺の素因数が一致しないからだと考えました。（もっとわかりやすい理由があれば教えてください。）

    補足日時：2015/09/30 07:22

No.7 ベストアンサー 回答者： guunagoona2015 回答日時： 2015/10/01 16:06

Ｐ＝｛１７×１、１７×２、、、、１７×６０｝を６０で割った余りは全体とて、Ｑ＝｛０，１、、、５９｝と一致します。

このＰの６０個のうち、６０と互いに素なもの同士をかけたＲ＝｛１７×１、１７×７、、、１７×５９｝（１６個）は全体として、
Ｓ＝｛１，７、、、５９｝（１６個）と一致するのはなぜか？
ということの理由をかんがえたいのですが、その理由は
互いに素な２数a,bについて、ab=60k+rとあらわした時に、ｒがもし、６０と１以外の公約数を持てば、両辺の素因数が一致しないからだと考えました。
　↑↑↑
この部分の説明を　Ｎｏ．６　の方が書かれています。
考え方は、合っていると思います。　（ａ，ｂ　は、１，７，１１、・・・・・５３，５９　ですね？）



１，７，１１，１３，１７，１９，２３，２９，３１，３７，４１，４３，４７，４９，５３，５９　に　１７　をかけた数

１７×１、１７×７、・・・・・、１７×５９　の　【　１６個の数　】　は　【　６０　と互いに素　】　です。


だから、これらの数を６０で割ると、余りは
１，７，１１，１３，１７，１９，２３，２９，３１，３７，４１，４３，４７，４９，５３，５９　のいずれかになるわけですが、


もし、　『　１７×１、１７×７、・・・・・、１７×５９　の中で、余りが等しくなるものがある　』　とすれば、
それを、
ａ×１７　と　ｂ×１７　(ａ＜ｂ)　とすると、　（⇦　本当は、　ａ≠ｂ　ですが、 ａ＜ｂ　として考えてもいいですね）
ａ×１７＝６０ｓ＋ｒ
ｂ×１７＝６０ｔ＋ｒ
と、おくことができます。
これより、
(ｂ×１７)－(ａ×１７)＝(６０ｔ＋ｒ)－(６０ｓ＋ｒ)＝６０ｔ－６０ｓ＝６０(ｔ－ｓ)
であり、また、
(ｂ×１７)－(ａ×１７)＝１７(ｂ－ａ)
であるから、
１７(ｂ－ａ)＝６０(ｔ－ｓ)　・・・・・（☆）
になります。

ここで、　１７　と　６０　は　互いに素　であるから、
ｂ－ａ　は　６０の倍数　になります。
ａ　と　ｂ　は、
１，７，１１，１３，１７，１９，２３，２９，３１，３７，４１，４３，４７，４９，５３，５９　のいずれかの数だから、
ｂ－ａ　が　６０以上の数になることはあり得ません。

ということは、
６０未満の数で、 （☆） が成り立つような　ｂ－ａ　は、
ｂ－ａ＝０
だけになります。
これより、
ａ＝ｂ　になりますが、これは、　ａ＜ｂ　に矛盾します。

よって、
１７×１、１７×７、・・・・・、１７×５９　の中で、余りが等しくなるものは　ない　ことになります。

このことから、
１７×１、１７×７、・・・・・、１７×５９　は、

１６個あり、
すべて６０と互いに素で、
余りがすべて異なるので、

１，７，１１，１３，１７，１９，２３，２９，３１，３７，４１，４３，４７，４９，５３，５９　に一致することになります。

この回答へのお礼

ありがとうございました。
一般的な場合も含めて復習します。

お礼日時：2015/10/02 02:01

No.6 回答者： スチールウール 回答日時： 2015/09/27 22:30

まず、60と互いに素な数は全部で16個しかないです

これは(1)で求めています

じゃあ、この互いに素な数を掛けて(例えば17と29)を掛けたものを考えましょう
もちろんこれは60では割れません。ですので、a(i)*a(k) = 60x+y (1≦y≦59)とおきましょう
この場合yも60と素になります。なぜなら、何か公約数を持っている(例えばy = 2zと表せる)なら右辺がその数でくくれる (2(30x+z))ようになり、左辺がその倍数になってしまうからです
ですので、60と互いに素な物通しを掛けたものを割ると、余りも60と互いに素となります。

では、次にa(i)*a(k) = 60x + yとしたので、a(j)*a(k)=60s+t(j≠i, t略)として考えてみましょうか
この時y=tと成り得るかどうかが問題です
なるとしたら、２つの式を引き算しましょう。
(a(i)-a(j))*a(k) = 60(x-s)
でも、a(i)もa(j)も60以下なんだから、60の倍数になるのは0位外にありえません
ですので、a(i) = a(j)となり、元の仮定に反します
つまり、a(i)*a(k)の余り(y)とa(j)*a(k)の余り(t)はどのようにi,jを取っても必ず異なります

じゃあ、aは16個あるので、余りも16種類出て来てこれは全て60と互いに素なはずですね？
で、冒頭に戻りますが60と互いに素な数は幾つあってどんな数でしたか？
あまりの数は16個で、それをa(1)～a(16)としたはずです
ですので、余りも最終的にこのa(1)～a(16)にならざるを得ないのです

この回答へのお礼

ありがとうございました。
一般的な場合も含めて復習します。

お礼日時：2015/10/02 02:02

No.5 回答者： tknakamuri 回答日時： 2015/09/22 10:49

面白い問題ですね。

>１６個を６０で割った余りはa(1),a(2),,,a(16)全体に一致する
>（順番は異なる）という部分の理由がよくわかりません。

説明の中でa(1)a(5)、～a(16)a(5)の余りが全て異なることが証明
されています。

また a(1)a(5)、～a(16)a(5)は60と互いに素なので、その余りも
60と互いに素です。


そして、a(1)a(5)、～a(16)a(5)の余りは60の余りなので60以下です。


まとめると、 a(1)a(5)、～a(16)a(5)の余りは
・全て異なる
・全て60と互いに素である。
・60以下である。

これは(1)の条件そのもので個数も同じですから
同じ数の集まりでなければならないのです。

この回答へのお礼

ありがとうございました。
一般的な場合も含めて復習します。

お礼日時：2015/10/02 02:02

No.4 回答者： Tacosan 回答日時： 2015/09/21 23:22

面倒なので a(5) と書かずに 17 にしちゃう.

とりあえず 17x + 60y = 1 となる整数 x, y の存在は仮定する. ここで
17a(i) = 17a(j)
とすると, この両辺に x を掛けて
(17x)a(i) = (17x)a(j)
となる. 60 で割った余りはどうなっていると思う?

この回答へのお礼

ありがとうございました。
一般的な場合も含めて復習します。

お礼日時：2015/10/02 02:02

No.3 回答者： guunagoona2015 回答日時： 2015/09/21 11:43

６０以下の自然数で、６０と互いに素なものは、

１，７，１１，１３，１７，１９，２３，２９，３１，３７，４１，４３，４７，４９，５３，５９
の　１６個です。

　　　　　↑↑↑

別の言い方をすると、この　１６個　の数は、
自然数を　６０　で割ったときの余りのうち　６０と互いに素　である数
になると思います。

上の１６個の数に　１７　をかけると、
１×１７，７×１７，１１×１７，１９×１７，２３×１７，２９×１７，３１×１７，３７×１７，
４１×１７，４３×１７，４７×１７，４９×１７，５３×１７，５９×１７
となりますが、これらの数も当然　６０と互いに素　です。
つまり、　６０　で割ると必ず余りが出ることになります。
この　余り　が　６０と互いに素　になります。　・・・・・（ア）

そして、これらの数を、　６０で割った余りがすべて異なる　・・・・・（イ）
ことの証明ができたわけです。

１×１７，７×１７，１１×１７，１３×１７，１７×１７，１９×１７，２３×１７，２９×１７，３１×１７，３７×１７，
４１×１７，４３×１７，４７×１７，４９×１７，５３×１７，５９×１７
は、全部で　１６個　です。　・・・・・（ウ）

（ア）、（イ）、（ウ）　から、
これら　１６個　の数は、６０で割った余りがすべて異なり、６０と互いに素であるから、
まさしく、
１，７，１１，１３，１７，１９，２３，２９，３１，３７，４１，４３，４７，４９，５３，５９
のいずれかの値になります。　

実際に、　１７　を掛けて確認されたのですね？

例えば、他の数　２９　で試してみると、
１×２９＝２９　　　　　　　２９÷６０＝０・・・２９
７×２９＝２０３　　　　　２０３÷６０＝３・・・２３
１１×２９＝３１９　　　　３１９÷６０＝５・・・１９
１３×２９＝３７７　　　　３７７÷６０＝６・・・１７
１７×２９＝４９３　　　　４９３÷６０＝８・・・１３
１９×２９＝５５１　　　　５５１÷６０＝９・・・１１
２３×２９＝６６７　　　　６６７÷６０＝１１・・・７
２９×２９＝８４１　　　　８４１÷６０＝１４・・・１
３１×２９＝８９９　　　　８９９÷６０＝１４・・・５９
３７×２９＝１０７３　　１０７３÷６０＝１７・・・５３
４１×２９＝１１８９　　１１８９÷６０＝１９・・・４９
４３×２９＝１２４７　　１２４７÷６０＝２０・・・４７
４７×２９＝１３６３　　１３６３÷６０＝２２・・・４３
４９×２９＝１４２１　　１４２１÷６０＝２３・・・４１
５３×２９＝１５３７　　１５３７÷６０＝２５・・・３７
５９×２９＝１７１１　　１７１１÷６０＝２８・・・３１

４３　で試してみると、

１×４３＝４３　　　　　　　４３÷６０＝０・・・４３
７×４３＝３０１　　　　　３０１÷６０＝５・・・１
１１×４３＝４７３　　　　４７３÷６０＝７・・・５３
１３×４３＝５５９　　　　５５９÷６０＝９・・・１９
１７×４３＝７３１　　　　７３１÷６０＝１２・・・１１
１９×４３＝８１７　　　　８１７÷６０＝１３・・・３７
２３×４３＝９８９　　　　９８９÷６０＝１６・・・２９
２９×４３＝１２４７　　１２４７÷６０＝２０・・・４７
３１×４３＝１３３３　　１３３３÷６０＝２２・・・１３
３７×４３＝１５９１　　１５９１÷６０＝２６・・・３１
４１×４３＝１７６３　　１７６３÷６０＝２９・・・２３
４３×４３＝１８４９　　１８４９÷６０＝３０・・・４９
４７×４３＝２０２１　　２０２１÷６０＝３３・・・４１
４９×４３＝２１０７　　２１０７÷６０＝３５・・・７
５３×４３＝２２７９　　２２７９÷６０＝３７・・・５９
５９×４３＝２５３７　　２５３７÷６０＝４２・・・１７

のように、やはり、　６０　で割った余りは、
１，７，１１，１３，１７，１９，２３，２９，３１，３７，４１，４３，４７，４９，５３，５９
のいずれかの値になります。

この回答へのお礼

ありがとうございました。
一般的な場合も含めて復習します。

お礼日時：2015/10/02 02:03

No.2 回答者： Tacosan 回答日時： 2015/09/21 02:05

端的にいってしまえば

a(5) = 17 が 60 と互いに素だから
で終わりなんだが, それで終われるならそもそも質問していないだろうからもうちょっと書く.

一般に 2つの整数 a と b が互いに素なら
ax + by = 1
となるような整数 x, y が存在する (これはユークリッドの互除法から示せる). 今の場合だと
17x + 60y = 1 であるような x, y が存在する
ということになる. これから
a(i)a(5) = a(j)a(5) なら a(i) = a(j)
といえるので「a(1)a(5),,,a(16)a(5)まではすべて６０と互いに素だからこれら１６個を６０で割った余りはa(1),a(2),,,a(16)全体に一致する（順番は異なる）」となる.

ちなみにこの問題の元ネタはオイラーの定理
https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4 …
だろう.

この回答へのお礼

ありがとうございました。
一般的な場合も含めて復習します。

お礼日時：2015/10/02 02:03

No.1 回答者： Tacosan 回答日時： 2015/09/20 23:06

どこまでわかっていてどこでわからなくなっているのでしょうか?

この回答へのお礼

ありがとうございました。
一般的な場合も含めて復習します。

お礼日時：2015/10/02 02:03