とっておきの手土産を教えて

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

「1の100乗、2の100乗、~100の1」の質問画像

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

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

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

A 回答 (9件)

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


x を 4 で割った余りが b になる ⇔ x = 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 が互いに素であること。
    • good
    • 2
この回答へのお礼

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

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

No1です


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

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

> 一般性持たせられますか?
 今回のように3と4が互いに素なら、可能ということ
    • good
    • 0

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


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

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

証明はよく知らんです。
    • good
    • 0

> 一般性持たせられますか?



No.4 に書いたよん。
    • good
    • 0

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 の取り得る全ての値の数ということになります。
    • good
    • 0
この回答へのお礼

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

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

画像の通り

「1の100乗、2の100乗、~100の1」の回答画像5
    • good
    • 0

きちんとやるなら


Chinese Remainder Theorem
かな.

ちなみにだけど, こういう工夫をしないでベタにやればできる?
    • good
    • 0
この回答へのお礼

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

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

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

    • good
    • 0
この回答へのお礼

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

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

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


「12でわったあまり0から11」を、「3でわったあまり」と「4でわったあまり」で分類してみればわかるのでは?
例えば、
 あまり11 は4で割ったあまり3なので、ありえない
 あまり8  は3で割ったあまり2なので、ありえない
といった具合。
結果、12で割ったあまりは0,1,4,9 の4通りになるということ
    • good
    • 2

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


おすすめ情報

このQ&Aを見た人がよく見るQ&A