合同式                                    戻る

 知らなくても特段不都合なことはないが、知っていれば大変重宝するのが「合同式」だろう。
中学入試でも暗に合同式を意識した問題が多数出題されている。高校入試や大学入試でも
合同式が活躍する場面は多い。合同式は、整数論的な思考をとても見通しよくしてくれる魔
法の道具である。

合同式  整数 a、b に対して、その差 a−b が、自然数 m で割り切れるとき、

     a と b は m を法として合同である

といい、記号 a≡b (mod m) で表す。

 つまり、m で割った余りが同じ数は、同じ(様な)数とみなそうということである。

 合同式については、次の性質が成り立つ。

(反射律)  a≡a (mod m)
(対称律)  a≡b (mod m) ならば、 b≡a (mod m)
(推移律)  a≡b (mod m)、b≡c (mod m) ならば、 a≡c (mod m)

 このことから、整数を類別して考えることが可能となる。

 合同式について、次のような演算が基本であろう。

 a≡b (mod m)、c≡d (mod m) ならば、

  a+c≡b+d (mod m) 、a−c≡b−d (mod m) 、ac≡bd (mod m)

 a≡b (mod m) ならば、 ak≡bk (mod m)


例 1510を4で割った余りを求めよ。

(解) 15≡−1 (mod 4) より、 1510≡1 (mod 4) なので、

   求める余りは、1  (終)


 問題をもう少し難しくしてみた。

問題  20222022 を13で割った余りを求めよ。

(解) 2022≡7 (mod 13) で、

 72=49≡10 (mod 13)

 73≡70≡5 (mod 13)

 74≡35≡9 (mod 13)

 75≡63≡11 (mod 13)

 76≡77≡−1 (mod 13) なので、 712≡1 (mod 13)

 ここで、 2022=12×168+6 なので、

 20222022=(712168・76≡−1≡12 (mod 13)

 以上から、 20222022 を13で割った余りは、12である。  (終)


問題  整数 a、b、c について、 a2+b2=c2 のとき、a、b のどちらか一方は偶数であ
    ることを示せ。

(解) a、b の両方が奇数と仮定すると、 a2≡1 (mod 4) 、b2≡1 (mod 4) より、

   c2=a2+b2≡2 (mod 4)

  しかるに、 c≡0 (mod 4) のとき、 c2≡0 (mod 4)

         c≡1 (mod 4) のとき、 c2≡1 (mod 4)

         c≡2 (mod 4) のとき、 c2≡0 (mod 4)

         c≡3 (mod 4) のとき、 c2≡1 (mod 4)

なので、 c2≡2 (mod 4) は起こりえない。

 よって、a、b のどちらか一方は偶数である。  (終)


(コメント) 上記と同様の議論から、 c2≡0 または 1 (mod 3) であることが分かる。


 合同式を用いた方程式の解法については、次の性質が重要である。

定理  ac≡bc (mod m)で、(c,m)=1 のとき、a≡b (mod m)

定理  aX≡b (mod m)は、(a,m)=1のとき、(mを法として)ただ一つの解をもつ。

例 8≡2 (mod 3) のとき、 両辺を2で割って、 4≡1 (mod 3)

例 7x≡2 (mod 4) は、4を法として、ただ一つの解を持つ。

  実際に、 7≡−1 (mod 4) なので、 −x≡2 (mod 4) より、

     x≡−2≡2 (mod 4)

(別解) 7x≡2 (mod 4) より、 7x=4k+2 (kは整数) と書ける。

   このとき、 7・(−2)=4・(−4)+2 より、 7(x+2)=4(k+4)

   7と4は互いに素なので、 x+2=4m (mは整数) と書ける。

   このとき、 x=4m−2=4(m−1)+2≡2 (mod 4)  (終)


例 10≡1 (mod 9) なので、100≡1 (mod 9)、1000≡1 (mod 9)、・・・

  一般に、 10^n≡1 (mod 9) が成り立つ。

 この事実を用いれば、654321を9で割った余りを求めることは、とても易しい。

実際に、 654321≡6+5+4+3+2+1≡21≡2+1≡3 より、余りは3となる。


 この性質を用いる問題が、開成中学入試(2022年)で出題された。

問題  次の計算結果を9で割ったときの余りを求めよ。

 1234567+2345671+3456712+4567123+5671234

 5個の7桁の数を全部足して、その結果を9で割ってもよいのだが、次のようにすれば暗
算で求められる。

(解) 5個の7桁の数はすべて、1、2、3、4、5、6、7 で出来ている。

ここで、1+2+3+4+5+6+7=28≡1 (mod 9) なので、求める余りは、5  (終)


 また、次のような問題も有名である。

問題  4桁の数Aとその逆順の数Bがある。A、Bで、大きい方から小さい方を引き、その
    数字のうち0でない数を一つ隠匿し、それ以外の数を言ってもらうと、秘匿した数が
    何かを言い当てることができる。これは何故か?

 例をあげて考察しよう。

 A=3852 とすると、B=2583 なので、 A−B=1269

 このとき、 1+2+6+9=18≡0 (mod 9) となっている。

 したがって、秘匿した数以外の数を聞いて、9で割り切れるように秘匿した数を答えれば
よい。

例えば、 「2、6、9」 と聞けば、和が17なので、秘匿した数は、1と分かる。


(追記) 令和4年6月12日付け

 次の問題も合同式を用いれば容易に解決することが出来る。

問題  3737+1313 は、10で割り切れることを示せ。

(解) 374≡1 (mod 10) より、 3737≡(3749・37≡7 (mod 10)

  同様に、 134≡1 (mod 10) より、 1313≡(1343・13≡3 (mod 10)

 よって、 3737+1313≡7+3≡0 (mod 10) より、10で割り切れる。  (終)


(追記) 「数の性質」と題して、GAI さんからのご投稿です。(令和4年6月13日付け)

問題 N=11^100+22^100+33^100+44^100+55^100+66^100+77^100+88^100+99^100
    を10で割った余りは?

(解) 11^100≡1 (mod 10)

   22^100≡2^100 (mod 10) において、mod 10 で、2、4、8、6、2、4、8、6、・・・ と
  「2、4、8、6」が繰り返すので、 22^100≡6 (mod 10)

   33^100≡3^100 (mod 10) において、3^2≡-1 (mod 10) より、
  3^4≡1 (mod 10) なので、 33^100≡1 (mod 10)

   44^100≡4^100=2^200 (mod 10) において、44^100≡6 (mod 10)

   55^100≡5^100≡5 (mod 10)

   66^100≡6^100≡6 (mod 10)

   77^100≡7^100 (mod 10) において、mod 10 で、7、9、3、1、7、9、3、1、・・・ と
  「7、9、3、1」が繰り返すので、 77^100≡1 (mod 10)

   88^100≡8^100 (mod 10) において、mod 10 で、8、4、2、6、8、4、2、6、・・・ と
  「8、4、2、6」が繰り返すので、 88^100≡6 (mod 10)

   99^100≡9^100 (mod 10) において、9≡-1 (mod 10) より、9^2≡1 (mod 10)
  なので、 99^100≡1 (mod 10)

 以上から、

 N≡1+6+1+6+5+6+1+6+1=33≡3 (mod 10) なので、Nを10で割った余りは、3

である。  (終)


(コメント) WolframAlpha 先生に計算をお願いしたところ、

  N≡1^4+2^4+3^4+4^4+5^4+6^4+7^4+8^4+9^4=15333≡3 (mod 10)

と計算を返してきた。


 私と同じ発想の解をらすかるさんよりいただいた。(令和4年6月13日付け)

 以下、合同式はすべてmod10

2^4=16≡6 、3^4=81≡1 、4^2=16≡6 、5^n≡5 、6^n≡6 、7^4=2401≡1 、8^4=4096≡6

9^2=81≡1

から、

N≡1^100+2^100+3^100+4^100+5^100+6^100+7^100+8^100+9^100

 =1+(2^4)^25+(3^4)^25+(4^2)^50+5^100+6^100+(7^4)^25+(8^4)^25+(9^2)^50

 ≡1+6+1+6+5+6+1+6+1=33≡3

なので、3。


 DD++ さんからのコメントです。(令和4年6月13日付け)

 与式≡1+0+1+0+1+0+1+0+1≡1 (mod 2)

また、p=5 について、フェルマーの小定理((a,5)=1のとき、a4≡1(mod 5))を用いると、

 与式≡1+1+1+1+0+1+1+1+1≡3 (mod 5)

よって、 与式≡3 (mod 10)


(コメント) N-1≡0 (mod 2) かつ、 N-1≡2 (mod 5) なので、

      N-1=5k+2≡0 (mod 2)

     よって、k≡0 (mod 2) となり、 k=2k’ とおける。

     このとき、 N-1=10k’+2≡2 (mod 10) から、 N≡3 (mod 10)  である。


 GAI さんからのコメントです。(令和4年6月14日付け)

 らすかるさん、DD++ さん、お二人とも性質を熟知されていることがビンビン伝わってきます。
ひょんなことから、5乗においては、

  a=1、2、3、・・・、9 で、 a^5≡a (mod 10)

が成立していることに気付いて、これを活用できる問題として作成しておりました。

 特に、DD++ さんの最も簡潔な近道に感激しました。なお、これが mod 100 となった場合は
どの様に対処できるのですか?


 らすかるさんからのコメントです。(令和4年6月14日付け)

 なお、これが mod 100 となった場合はどの様に対処できるのですか?

 以下、合同式はすべて mod 100。

 n^2≡n の解は、0、1、25、76  (つまり、この4つは何乗しても mod 100 で不変)

2^20=1048576≡76 、3^20=3486784401≡1 、4^10=1048576≡76 、5^2=25≡25

6^5=7776≡76 、7^4=2401≡1 、8^20=1152921504606846976≡76 、9^10=3486784401≡1

 ここで、 11^10=25937424601≡1 なので、

N=11^100+22^100+33^100+44^100+55^100+66^100+77^100+88^100+99^100

 =11^100(1^100+2^100+3^100+4^100+5^100+6^100+7^100+8^100+9^100)

 ={(11^10)^10}{1+(2^20)^5+(3^20)^5+(4^10)^10+(5^2)^50+(6^5)^20+(7^4)^25+(8^20)^5+(9^10)^10}

 ≡1・(1+76+1+76+25+76+1+76+1)=333≡33

となり、100で割った余りは、33。


 DD++ さんからのコメントです。(令和4年6月14日付け)

 オイラーのトーシェント関数を使います。

 オイラーの定理より、a が 5 の倍数でないとき、 a^φ(25)=a^20≡1 (mod 25) なので、

 与式≡1+1+1+1+0+1+1+1+1≡8 (mod 25)

また、 与式≡1+0+1+0+1+0+1+0+1≡1 (mod 4)

よって、 与式≡33 (mod 100)

 ついでに 1000 で割る場合も。

 オイラーの定理より、a が 5 の倍数でないとき、a^φ(125)=a^100≡1 (mod125) なので、

 与式≡1+1+1+1+0+1+1+1+1≡8 (mod 125)

また、 与式≡1+0+1+0+1+0+1+0+1≡5 (mod 8)

よって、 与式≡133 (mod 1000)

#10000 で割るとなると、手を変えないといけませんね。


(コメント) N≡8 (mod 25) 、N≡1 (mod 4) より、

      N-1≡7 (mod 25) 、N-1≡0 (mod 4)

 このとき、 N-1=25k+7 で、 25k+7≡0 (mod 4) 即ち、 k+3≡0 (mod 4)

 そこで、k=4k’+1 とおけるので、N-1=100k’+32 より、 N=100k’+33≡33 (mod 100)

同様にして、

 N≡8 (mod 125) 、N≡5 (mod 8) より、

      N-5≡3 (mod 125) 、N-5≡0 (mod 8)

 このとき、 N-5=125k+3 で、 125k+3≡0 (mod 8) 即ち、 k≡1 (mod 8)

 そこで、k=8k’+1 とおけるので、N-5=1000k’+125+3=1000k’+128 より、

 N=1000k’+133≡133 (mod 1000)


 GAI さんからのコメントです。(令和4年6月16日付け)

  a=1、2、3、・・・、9 で、 a^5≡a (mod 10)

から、5乗は元に戻す力が特別と感じた。では、mod 100、mod 1000、・・・、mod 10^n では
どんな数字が対応できるか、調べてみることにした。

 a^5≡a (mod 100) を満たす整数 a は、{1,7,24,25,32,43,49,51,57,68,75,76,93,99}

 a^5≡a (mod 1000) を満たす整数 a は、

{1,57,125,193,249,251,307,375,376,432,443,499,501,557,568,624,625,693,749,751,807,875,943,999}

 そこで、これを系統別に、

1->51->251
・ ・・・・ ->751
・ ->01->501

2->32->432

3->43->443
・ ・・・・->943
・ ->93->193
・ ・・・・->693

4->24->624

5->25->125
・ ・・・・->625
・ ->75->375
・ ・・・・->875

6->76->376

7->57->557
・ ->07->307
・ ・・・・->807

8->68->568

9->49->249
・ ・・・・->749
・ ->99->499
・ ・・・・->999

という風に、前に満足している整数の頭に、新たな数字を付け加えることで繋げていけるも
のを探してみることにする。

 次の候補は、

{1,443,624,625,807,1249,1251,1693,1875,2057,2499,2501,2943, 3125,3307,3568,3749,3751,
 4193,4375,4557,4999,5001,5443,5625,5807, 6249,6251,6432,6693,6875,7057,7499,7501,
 7943,8125,8307,8749,8751, 9193,9375,9376,9557,9999}

となるので、これにつなげていく。

 こうして次々と繋がっていける列で、次のものが見つかった。あとは、これをOEISで検索し
ヒットしたものの掲載分を参考につけています。

A063006(A224474)より、

 M1=[1, 5, 7, 8, 1, 2, 4, 7, 5, 3, 6, 1, 0, 8, 4, 7, 8, 4, 5, 1,・・・];

 1,51,751,8751,18751,218751,4218751,74218751,574218751,3574218751,

つまり、

[51^5≡51(mod 10^2)、751^5≡751(mod 10^3)、8751^5≡8751(mod 10^4)、・・・ が成立する。]

A120817より、

 M2=[2, 3, 4, 6, 8, 1, 9, 7, 8, 9, 9, 4, 3, 6, 2, 3, 0, 1, 4, 0,・・・];

 2,32,432,6432,86432,186432,9186432,79186432,879186432,9879186432,

A290373より、

 M31=[3, 4, 9, 2, 2, 9, 7, 0, 9, 1, 8, 5, 6, 7, 4, 0, 4, 6, 3, 0,・・・];

 3,43,943,2943,22943,922943,7922943,7922943,907922943,1907922943,

A290375より、

 M32=[3, 9, 1, 4, 0, 7, 3, 3, 3, 8, 1, 4, 6, 9, 9, 2, 5, 1, 8, 8,・・・];
 3,93,193,4193,4193,704193,3704193,33704193,333704193,8333704193,

A091664(A216092)より、

 M4=[4, 2, 6, 0, 9, 8, 2, 1, 2, 8, 1, 9, 9, 5, 2, 6, 5, 2, 2, 9,・・・];

 4,24,624,624,90624,890624,2890624,12890624,212890624,8212890624,

A091663(A216093)より、

 M51=[5, 7, 3, 9, 0, 1, 7, 8, 7, 1, 8, 0, 0, 4, 7, 3, 4, 7, 7, 0,・・・];

 5,75,375,9375,9375,109375,7109375,87109375,787109375,1787109375,

A018247(A007185)より、

 M52=[5, 2, 6, 0, 9, 8, 2, 1, 2, 8, 1, 9, 9, 5, 2, 6, 5, 2, 2, 9,・・・];

 5,25,625,625,90625,890625,2890625,12890625,212890625,8212890625,
(ただしこれは5乗に限らず、何乗でも成立していく。)

A018248(A016090)より、

 M6=[6, 7, 3, 9, 0, 1, 7, 8, 7, 1, 8, 0, 0, 4, 7, 3, 4, 7, 7, 0,・・・];

 6,76,376,9376,9376,109376,7109376,87109376,787109376,1787109376,
(ただしこれは5乗に限らず、何乗でも成立していく。)

A290372より、

 M71=[7, 0, 8, 5, 9, 2, 6, 6, 6, 1, 8, 5, 3, 0, 0, 7, 4, 8, 1, 1,・・・];

 7,7,807,5807,95807,295807,6295807,66295807,666295807,1666295807,

A290374より、

 M72=[7, 5, 0, 7, 7, 0, 2, 9, 0, 8, 1, 4, 3, 2, 5, 9, 5, 3, 6, 9,・・・];

 7,57,57,7057,77057,77057,2077057,92077057,92077057,8092077057,

A120818より、

 M8=[8, 6, 5, 3, 1, 8, 0, 2, 1, 0, 0, 5, 6, 3, 7, 6, 9, 8, 5, 9,・・・];

 8,68,568,3568,13568,813568,813568,20813568,120813568,120813568,

A091661(A224473)より、

 M9=[9, 4, 2, 1, 8, 7, 5, 2, 4, 6, 3, 8, 9, 1, 5, 2, 1, 5, 4, 8,・・・];

 9,49,249,1249,81249,781249,5781249,25781249,425781249,6425781249,

 確かに、5乗は、mod 10 に限らず、他の mod 10^n での世界でも元の数に引き戻すこと
が出来る役割を担い続けることが出来そうです。(各1〜9に続く系統が存在する。)


 GAI さんからのコメントです。(令和4年6月17日付け)

 最も集客を集めるべき乗は何だろう?

 mod 10 では、a^5≡a を満たすaは、{1,2,3,4,5,6,7,8,9} とフル数字でよかった。

 これを mod 100 にすると、{1,7,24,25,32,43,49,51,57,68,75,76,93,99} であり、チョット物足り
ない。

 そこで、a^k≡a (mod 100) が多くの a を集められる k は如何に?で調査してみると、何
と、

gp > for(a=1,99,if(lift(Mod(a^21,100))==a,print1(a",")))
1,3,4,7,8,9,11,12,13,16,17,19,21,23,24,25,27,28,29,31,32,33,36,37,39,41,43,44,47,48,49,51,52,53,
56,57,59,61,63,64,67,68,69,71,72,73,75,76,77,79,81,83,84,87,88,89,91,92,93,96,97,99,

 この列がA075821に載る。(内容的には他の視点で集まった数列)

 62/99(約62.6%)ものものが採用可能となり、ダントツであった。

 不思議なことに k は他の k=41,61,81,101,・・・・ でも同じ a が並んだ。

 また、mod 1000 では、k=101,201,301,・・・・

 これで集まる a の割合が、504/999=56/111(約50.5%)でダントツでした。

 ここで採用される a の値が、これとは全くかけ離れた内容でのA122987と一致することに
驚いた。

 この2つの関係はどうなっているんだろう?


 DD++ さんからのコメントです。(令和4年6月17日付け)

 この列がA075821に載る。(内容的には他の視点で集まった数列)

 コメントを読む限り、まさしく 21 乗の下 2 桁として作られた列のようですが。

 不思議なことに k は他の k=41,61,81,101,・・・・ でも同じ a が並んだ。

 また、mod 1000 では、k=101,201,301,・・・・


 えっと、先日の問題の流れを受ければ、この結果はごく自然なものに思えますが、どこを
不思議と思っておられるのでしょうか?


 GAI さんからのコメントです。(令和4年6月17日付け)

 a41=a21*a20≡a*a20=a21≡a (mod 100)

 そうか、不思議でもなんでもないですね。

 A122987での説明がよくわからないのですが、これが、a^101≡a (mod 1000) で集める a
と同じになるのはどうしてなのかな?という意味で問いかけておりました。


 DD++ さんからのコメントです。(令和4年6月17日付け)

 なるほど、確かに立方数の下 3 桁との一致は少し考えないといけませんね。以下でどうで
しょう。

以下、合同式は断りがない限り mod1000 とします。

 101 乗の下 3 桁が元の数に戻る数は、必ずある立方数の下 3 桁に出現します。

 なぜならば、a^101≡a であれば、b≡a^67 とすると、b^3≡a^201≡a^101≡a だからです。

 立方数の下3桁に出現する数は、その101乗の下3桁が元の数に一致します。

 なぜなら、以下の 2 つから、立方数と下 3 桁が一致する a について a^101-a は 1000 の
倍数だからです。

(1) 立方数は 5 と互いに素である、またはそれ自体 125 の倍数です。

 よって、a も同じく 5 と互いに素である、またはそれ自体 125 の倍数です。

つまり、a^φ(125)-1 すなわち a^100-1 または a のいずれかが 125 の倍数です。

したがって、a(a^100-1) は 125 の倍数です。

(2) 立方数は奇数である、またはそれ自体 8 の倍数です。

 よって 、a も同じく奇数である、またはそれ自体 8 の倍数です。

つまり、a^2-1 または a のいずれかが 8 の倍数です。

したがって、a(a^100-1)=a(a^2-1)(a^98+a^96+……+a^2+1) は 8 の倍数です。


 GAI さんからのコメントです。(令和4年6月18日付け)

 a^21≡a (mod 100) が最も a の相当数が見つかるが、これを満たす a の集合は、
Mod(a^3,100)での余りが取り得る数に対応し、a^101≡a (mod 1000) が最も a の相当数
が見つかるが、これを満たす a の集合は、Mod(a^3,1000)での余りが取り得る数に対応し
ている。

<プログラムでの確認>
gp > {S=[];}for(a=1,99,r=lift(Mod(a^3,10^2));S=concat(S,[r]));S=vecsort(Set(S))
%41 = [0, 1, 3, 4, 7, 8, 9, 11, 12, 13, 16, 17, 19, 21, 23, 24, 25, 27, 28, 29, 31, 32, 33, 36, 37,
    39, 41, 43, 44, 47, 48, 49, 51, 52, 53, 56, 57, 59, 61, 63, 64, 67, 68, 69, 71, 72, 73, 75,
    76, 77, 79, 81, 83, 84, 87, 88, 89, 91, 92, 93, 96, 97, 99]
gp > {T=[];}for(a=0,99,if(lift(Mod(a^21,10^2))==a,T=concat(T,[a])));T
%42 = [0, 1, 3, 4, 7, 8, 9, 11, 12, 13, 16, 17, 19, 21, 23, 24, 25, 27, 28, 29, 31, 32, 33, 36, 37,
    39, 41, 43, 44, 47, 48, 49, 51, 52, 53, 56, 57, 59, 61, 63, 64, 67, 68, 69, 71, 72, 73, 75,
    76, 77, 79, 81, 83, 84, 87, 88, 89, 91, 92, 93, 96, 97, 99]

 結果は長くなるので省略していますが、結果は同じになりました。

gp > {S=[];}for(a=1,999,r=lift(Mod(a^3,10^3));S=concat(S,[r]));S=vecsort(Set(S))
gp > {T=[];}for(a=0,999,if(lift(Mod(a^101,10^3))==a,T=concat(T,[a])));T

 そこで、mod 10000 を調べてみたら、a^501≡a (mod 10000) が最も a の相当数が見つ
かり、4509個ある。(ダントツの多さ)

({T=[];}for(a=0,9999,if(lift(Mod(a^501,10^4))==a,T=concat(T,[a])));T で求まる集合Tの要素数
 #Tが#T=4509)

 ところが、a^3を10000で割ったときの余りが取り得る総数は5050個となり、
({S=[];}for(a=1,9999,r=lift(Mod(a^3,10^4));S=concat(S,[r]));S=vecsort(Set(S)) で求まる集合
 Sでの#S=5050)

 上2つの広がりは起こりませんでした。


 DD++ さんからのコメントです。(令和4年6月18日付け)

 おそらくですが、

mod100 の場合は、a^n の n として「2 以上かつ 20 と互いに素」であることが要求されるの
で n=3 が最小

mod1000 の場合は、a^n の n として「3 以上かつ 100 と互いに素」であることが要求される
ので n=3 が最小

mod10000 の場合は、a^n の n として「4 以上かつ 500 と互いに素」であることが要求され
るので n=7 が最小

となるのではないでしょうかね?


 GAI さんからのコメントです。(令和4年6月19日付け)

{S=[];}for(n=1,9999,r=lift(Mod(n^7,10^4));S=concat(S,[r]));S=vecsort(Set(S))
{T=[];}for(n=0,9999,if(lift(Mod(n^501,10^4))==n,T=concat(T,[n])));T

に対して、 #S=#T=4509

しかも、

gp > S==T
% = 1 (S、T の2つの集合内容が全く同一を示す。)

の結果となり、DD++さんの推測は見事に実証できました。

ちなみに、mod 100000では、

{S=[];}for(n=1,99999,r=lift(Mod(n^7,10^5));S=concat(S,[r]));S=vecsort(Set(S))
{T=[];}for(n=0,99999,if(lift(Mod(n^5001,10^5))==n,T=concat(T,[n])));T

の対応で、2つの集合は同一を見ました。(#S=#T=42517)



  以下、工事中!