1の100乗、2の100乗、～100の100乗をそれぞれ12で割った余りのうちことなるものは何通りか

1の100乗、2の100乗、～100の100乗をそれぞれ12で割った余りのうちことなるものは何通りか。　という問題でしたのような解答がありました。質問、なぜ12で割った余りを考えるとき3でわったあまりと4でわったあまりだけで考えれるのでしょうか。これだけでほんとに12でわったあまり0から11を表せてるのか疑問です。

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

• どういう発想で、12でわったあまりを4でわったあまりと3でわったあまりを考えることによって考えよう、となるのでしょうか

    補足日時：2024/10/17 00:22

No.4 ベストアンサー 回答者： ありものがたり 回答日時： 2024/10/17 10:13

ｘ を 3 で割った余りが a になる　⇔　ｘ = 3m + a となる整数 m がある。

ｘ を 4 で割った余りが b になる　⇔　ｘ = 4n + b となる整数 n がある。
これが同時に成り立つなら、 3m + a = 4n + b となる整数 m,n があることになる。
一次不定方程式ってやつだよね？

一次不定方程式の解法は確立されていて、本だのネットだのに解説がある。
結論を言うと、係数 3, 4 が互いに素な場合には解があって、
解の一例 m = m₀, n = n₀ を見つければ
全ての解は m = m₀ + 4k, n = n₀ + 3k (kは任意の整数) と表される。

これを代入すると、 x = 3m₀ + a + 12k (kは任意の整数) となって、
つまり、 x を 3 で割った余りと 4 で割った余りが決まれば
x を 12 で割った余りも決まることを示している。

ポイントは、 3・4 = 12 であることと、 3,4 が互いに素であること。

この回答へのお礼

わかりやすいです！！返信遅くなりましたありがとうございます！

お礼日時：2024/10/17 19:03

No.9 回答者： usa3usa 回答日時： 2024/10/17 14:48

Ｎｏ１です

Ｎo.４さん回答で十分と思いますが、直感的に説明すると次のような感じかしら。

＞これだけでほんとに12でわったあまり0から11を表せてるのか疑問です。
　12でわったあまりは１２通りです
一方、
　４でわったあまりは４通りです
　3でわったあまりは３通りです
従って
　「４でわったあまり」と「３でわったあまり」の組み合わせは１２通りですよね

＞ 一般性持たせられますか？
　今回のように３と４が互いに素なら、可能ということ

No.8 回答者： tknakamuri 回答日時： 2024/10/17 12:18

>たとえばこの方法だと210を13と17で分けて

>考えれるのかどうか判別できなくないですか

互いに素な正の整数 a, b が有ると
n mod a と n mod b の組み合わせは n mod (ab) に
一対一に対応させられます。

証明はよく知らんです。

No.7 回答者： ありものがたり 回答日時： 2024/10/17 11:22

＞ 一般性持たせられますか？

Ｎo.４ に書いたよん。

No.6 回答者： tknakamuri 回答日時： 2024/10/17 11:14

n mod 12 = 0 ～ 11 に対する n mod 3, n mod 4 の組み合わせは

0:(0, 0), 1:(1, 1), 2:(2, 2), 3: (0, 3), 4:(1, 0), 5:(2, 1)
6:(0, 2), 7:(1, 3), 8:(2, 0), 9: (0, 1), 10:(1, 2), 11:(2, 3)

なので、n mod 3, n mod 4 の組み合わせを n mod 12に 1:1 に
対応させることができます。つまり n mod 3, n mod 4 がわかれば
n mod 12 もわかります。

これは k^100 mod 3, k^100 mod 4 から k^100 mod 12 を求められることになり、k^100 mod 3, k^100 mod 4 の取り得る全ての組み合わせ数が k^100 mod 12 の取り得る全ての値の数ということになります。

この回答へのお礼

これ一般性持たせられますか？。たとえばこの方法だと210を13と17で分けて考えれるのかどうか判別できなくないですか

お礼日時：2024/10/17 11:16

No.5 回答者： mtrajcp 回答日時： 2024/10/17 10:38

画像の通り

No.3 回答者： Tacosan 回答日時： 2024/10/17 01:57

きちんとやるなら

Chinese Remainder Theorem
かな.

ちなみにだけど, こういう工夫をしないでベタにやればできる?

この回答へのお礼

12を1周期とすればmodでいけたんですけど、こっち(模範解答)のほうがはるかに楽そうだったので理解したいです。
その英語は中国剰余定理ですか？きちんと説明していただけるとありがたいです

お礼日時：2024/10/17 07:47

No.2 回答者： seiji91 回答日時： 2024/10/17 01:20

12＝2ｘ2ｘ3だから、2の倍数と3の倍数で場合分けすれば絞れてくる。

この回答へのお礼

そうやって分けて考えても良い理由が知りたいです

お礼日時：2024/10/17 07:48

No.1 回答者： usa3usa 回答日時： 2024/10/16 23:55

＞これだけでほんとに12でわったあまり0から11を表せてるのか疑問です。

「12でわったあまり0から11」を、「3でわったあまり」と「4でわったあまり」で分類してみればわかるのでは？
例えば、
　あまり１１　は４で割ったあまり３なので、ありえない
　あまり８　　は３で割ったあまり２なので、ありえない
といった具合。
結果、１２で割ったあまりは０，１，４，９　の４通りになるということ