知らなくても特段不都合なことはないが、知っていれば大変重宝するのが「合同式」だろう。
中学入試でも暗に合同式を意識した問題が多数出題されている。高校入試や大学入試でも
合同式が活躍する場面は多い。合同式は、整数論的な思考をとても見通しよくしてくれる魔
法の道具である。
合同式 整数 ａ、ｂ に対して、その差 ａ−ｂ が、自然数 ｍ で割り切れるとき、
ａ と ｂ は ｍ を法として合同である
といい、記号 ａ≡ｂ （mod ｍ） で表す。
つまり、ｍ で割った余りが同じ数は、同じ（様な）数とみなそうということである。
合同式については、次の性質が成り立つ。
（反射律） ａ≡ａ （mod ｍ）
（対称律） ａ≡ｂ （mod ｍ） ならば、 ｂ≡ａ （mod ｍ）
（推移律） ａ≡ｂ （mod ｍ）、ｂ≡ｃ （mod ｍ） ならば、 ａ≡ｃ （mod ｍ）
このことから、整数を類別して考えることが可能となる。
合同式について、次のような演算が基本であろう。
ａ≡ｂ （mod ｍ）、ｃ≡ｄ （mod ｍ） ならば、
ａ＋ｃ≡ｂ＋ｄ （mod ｍ） 、ａ−ｃ≡ｂ−ｄ （mod ｍ） 、ａｃ≡ｂｄ （mod ｍ）
ａ≡ｂ （mod ｍ） ならば、 ａk≡ｂk （mod ｍ）
例 １５10を４で割った余りを求めよ。
（解） １５≡−１ （ｍｏｄ ４） より、 １５10≡１ （ｍｏｄ ４） なので、
求める余りは、１ （終）
問題をもう少し難しくしてみた。
問題 ２０２２2022 を１３で割った余りを求めよ。
（解） ２０２２≡７ （ｍｏｄ １３） で、
７2＝４９≡１０ （ｍｏｄ １３）
７3≡７０≡５ （ｍｏｄ １３）
７4≡３５≡９ （ｍｏｄ １３）
７5≡６３≡１１ （ｍｏｄ １３）
７6≡７７≡−１ （ｍｏｄ １３） なので、 ７12≡１ （ｍｏｄ １３）
ここで、 ２０２２＝１２×１６８＋６ なので、
２０２２2022＝（７12）168・７6≡−１≡１２ （ｍｏｄ １３）
以上から、 ２０２２2022 を１３で割った余りは、１２である。 （終）
問題 整数 ａ、ｂ、ｃ について、 ａ2＋ｂ2＝ｃ2 のとき、ａ、ｂ のどちらか一方は偶数であ
ることを示せ。
（解） ａ、ｂ の両方が奇数と仮定すると、 ａ2≡１ （ｍｏｄ ４） 、ｂ2≡１ （ｍｏｄ ４） より、
ｃ2＝ａ2＋ｂ2≡２ （ｍｏｄ ４）
しかるに、 ｃ≡０ （ｍｏｄ ４） のとき、 ｃ2≡０ （ｍｏｄ ４）
ｃ≡１ （ｍｏｄ ４） のとき、 ｃ2≡１ （ｍｏｄ ４）
ｃ≡２ （ｍｏｄ ４） のとき、 ｃ2≡０ （ｍｏｄ ４）
ｃ≡３ （ｍｏｄ ４） のとき、 ｃ2≡１ （ｍｏｄ ４）
なので、 ｃ2≡２ （ｍｏｄ ４） は起こりえない。
よって、ａ、ｂ のどちらか一方は偶数である。 （終）
（コメント） 上記と同様の議論から、 ｃ2≡０ または １ （ｍｏｄ ３） であることが分かる。
合同式を用いた方程式の解法については、次の性質が重要である。
定理 ａｃ≡ｂｃ （mod ｍ）で、（ｃ，ｍ）＝１ のとき、ａ≡ｂ （mod ｍ）
定理 ａＸ≡ｂ （mod ｍ）は、（ａ，ｍ）＝１のとき、（ｍを法として）ただ一つの解をもつ。
例 ８≡２ （ｍｏｄ ３） のとき、 両辺を２で割って、 ４≡１ （ｍｏｄ ３）
例 ７ｘ≡２ （ｍｏｄ ４） は、４を法として、ただ一つの解を持つ。
実際に、 ７≡−１ （ｍｏｄ ４） なので、 −ｘ≡２ （ｍｏｄ ４） より、
ｘ≡−２≡２ （ｍｏｄ ４）
（別解） ７ｘ≡２ （ｍｏｄ ４） より、 ７ｘ＝４ｋ＋２ （ｋは整数） と書ける。
このとき、 ７・（−２）＝４・（−４）＋２ より、 ７（ｘ＋２）＝４（ｋ＋４）
７と４は互いに素なので、 ｘ＋２＝４ｍ （ｍは整数） と書ける。
このとき、 ｘ＝４ｍ−２＝４（ｍ−１）＋２≡２ （ｍｏｄ ４） （終）
例 １０≡１ （mod ９） なので、１００≡１ （mod ９）、１０００≡１ （mod ９）、・・・
一般に、 １０＾ｎ≡１ （mod ９） が成り立つ。
この事実を用いれば、６５４３２１を９で割った余りを求めることは、とても易しい。
実際に、 ６５４３２１≡６＋５＋４＋３＋２＋１≡２１≡２＋１≡３ より、余りは３となる。
この性質を用いる問題が、開成中学入試（２０２２年）で出題された。
問題 次の計算結果を９で割ったときの余りを求めよ。
１２３４５６７＋２３４５６７１＋３４５６７１２＋４５６７１２３＋５６７１２３４
５個の７桁の数を全部足して、その結果を９で割ってもよいのだが、次のようにすれば暗
算で求められる。
（解） ５個の７桁の数はすべて、１、２、３、４、５、６、７ で出来ている。
ここで、１＋２＋３＋４＋５＋６＋７＝２８≡１ （mod ９） なので、求める余りは、５ （終）
また、次のような問題も有名である。
問題 ４桁の数Ａとその逆順の数Ｂがある。Ａ、Ｂで、大きい方から小さい方を引き、その
数字のうち０でない数を一つ隠匿し、それ以外の数を言ってもらうと、秘匿した数が
何かを言い当てることができる。これは何故か？
例をあげて考察しよう。
Ａ＝３８５２ とすると、Ｂ＝２５８３ なので、 Ａ−Ｂ＝１２６９
このとき、 １＋２＋６＋９＝１８≡０ （mod ９） となっている。
したがって、秘匿した数以外の数を聞いて、９で割り切れるように秘匿した数を答えれば
よい。
例えば、 「２、６、９」 と聞けば、和が１７なので、秘匿した数は、１と分かる。
（追記） 令和４年６月１２日付け
次の問題も合同式を用いれば容易に解決することが出来る。
問題 ３７37＋１３13 は、１０で割り切れることを示せ。
（解） ３７4≡１ （ｍｏｄ １０） より、 ３７37≡（３７4）9・３７≡７ （ｍｏｄ １０）
同様に、 １３4≡１ （ｍｏｄ １０） より、 １３13≡（１３4）3・１３≡３ （ｍｏｄ １０）
よって、 ３７37＋１３13≡７＋３≡０ （ｍｏｄ １０） より、１０で割り切れる。 （終）
（追記） 「数の性質」と題して、ＧＡＩ さんからのご投稿です。（令和４年６月１３日付け）
問題 N=11^100＋22^100＋33^100＋44^100＋55^100＋66^100＋77^100＋88^100＋99^100
を10で割った余りは？
（解） 11^100≡１ （ｍｏｄ 10）
22^100≡2^100 （ｍｏｄ 10） において、ｍｏｄ 10 で、2、4、8、6、2、4、8、6、・・・ と
「2、4、8、6」が繰り返すので、 22^100≡6 （ｍｏｄ 10）
33^100≡3^100 （ｍｏｄ 10） において、3^2≡-1 （ｍｏｄ 10） より、
3^4≡1 （ｍｏｄ 10） なので、 33^100≡１ （ｍｏｄ 10）
44^100≡4^100=2^200 （ｍｏｄ 10） において、44^100≡6 （ｍｏｄ 10）
55^100≡5^100≡5 （ｍｏｄ 10）
66^100≡6^100≡6 （ｍｏｄ 10）
77^100≡7^100 （ｍｏｄ 10） において、ｍｏｄ 10 で、7、9、3、1、7、9、3、1、・・・ と
「7、9、3、1」が繰り返すので、 77^100≡1 （ｍｏｄ 10）
88^100≡8^100 （ｍｏｄ 10） において、ｍｏｄ 10 で、8、4、2、6、8、4、2、6、・・・ と
「8、4、2、6」が繰り返すので、 88^100≡6 （ｍｏｄ 10）
99^100≡9^100 （ｍｏｄ 10） において、9≡-1 （ｍｏｄ 10） より、9^2≡1 （ｍｏｄ 10）
なので、 99^100≡１ （ｍｏｄ 10）
以上から、
N≡1＋6＋1＋6＋5＋6＋1＋6＋1=33≡3 （ｍｏｄ 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 （ｍｏｄ １０）
と計算を返してきた。
私と同じ発想の解をらすかるさんよりいただいた。（令和４年６月１３日付け）
以下、合同式はすべて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++ さんからのコメントです。（令和４年６月１３日付け）
与式≡1+0+1+0+1+0+1+0+1≡1 (mod 2)
また、p=5 について、フェルマーの小定理（（ａ，5）＝１のとき、ａ4≡１（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=5ｋ＋2≡0 (mod 2)
よって、ｋ≡0 (mod 2) となり、 ｋ＝2ｋ’ とおける。
このとき、 N-1=10ｋ’＋2≡2 (mod 10) から、 N≡3 (mod 10) である。
ＧＡＩ さんからのコメントです。（令和４年６月１４日付け）
らすかるさん、DD++ さん、お二人とも性質を熟知されていることがビンビン伝わってきます。
ひょんなことから、５乗においては、
a=1、2、3、･･･、9 で、 a^5≡a (mod 10)
が成立していることに気付いて、これを活用できる問題として作成しておりました。
特に、DD++ さんの最も簡潔な近道に感激しました。なお、これが mod 100 となった場合は
どの様に対処できるのですか？
らすかるさんからのコメントです。（令和４年６月１４日付け）
なお、これが mod 100 となった場合はどの様に対処できるのですか？
以下、合同式はすべて mod 100。
n^2≡n の解は、0、1、25、76 (つまり、この４つは何乗しても 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++ さんからのコメントです。（令和４年６月１４日付け）
オイラーのトーシェント関数を使います。
オイラーの定理より、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＝25ｋ+7 で、 25ｋ+7≡0 (mod 4) 即ち、 ｋ+3≡0 (mod 4)
そこで、ｋ=4ｋ’+1 とおけるので、N-1＝100ｋ’+32 より、 N=100ｋ’+33≡33 (mod 100)
同様にして、
N≡8 (mod 125) 、N≡5 (mod 8) より、
N-5≡3 (mod 125) 、N-5≡0 (mod 8)
このとき、 N-5＝125ｋ+3 で、 125ｋ+3≡0 (mod 8) 即ち、 ｋ≡1 (mod 8)
そこで、ｋ=8ｋ’+1 とおけるので、N-5＝1000ｋ’+125+3=1000ｋ’+128 より、
N=1000ｋ’+133≡133 (mod 1000)
ＧＡＩ さんからのコメントです。（令和４年６月１６日付け）
a=1、2、3、･･･、9 で、 a^5≡a (mod 10)
から、５乗は元に戻す力が特別と感じた。では、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,
確かに、５乗は、mod 10 に限らず、他の mod 10^n での世界でも元の数に引き戻すこと
が出来る役割を担い続けることが出来そうです。(各1〜9に続く系統が存在する。)
ＧＡＩ さんからのコメントです。（令和４年６月１７日付け）
最も集客を集めるべき乗は何だろう？
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と一致することに
驚いた。
この２つの関係はどうなっているんだろう？
DD++ さんからのコメントです。（令和４年６月１７日付け）
この列がA075821に載る。(内容的には他の視点で集まった数列）
コメントを読む限り、まさしく 21 乗の下 2 桁として作られた列のようですが。
不思議なことに k は他の k=41,61,81,101,････ でも同じ a が並んだ。
また、mod 1000 では、k=101,201,301,････
えっと、先日の問題の流れを受ければ、この結果はごく自然なものに思えますが、どこを
不思議と思っておられるのでしょうか？
ＧＡＩ さんからのコメントです。（令和４年６月１７日付け）
a41=a21*a20≡a*a20=a21≡a （mod 100)
そうか、不思議でもなんでもないですね。
A122987での説明がよくわからないのですが、これが、a^101≡a (mod 1000) で集める a
と同じになるのはどうしてなのかな？という意味で問いかけておりました。
DD++ さんからのコメントです。（令和４年６月１７日付け）
なるほど、確かに立方数の下 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 の倍数です。
ＧＡＩ さんからのコメントです。（令和４年６月１８日付け）
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)
上２つの広がりは起こりませんでした。
DD++ さんからのコメントです。（令和４年６月１８日付け）
おそらくですが、
mod100 の場合は、a^n の n として「2 以上かつ 20 と互いに素」であることが要求されるの
で n=3 が最小
mod1000 の場合は、a^n の n として「3 以上かつ 100 と互いに素」であることが要求される
ので n=3 が最小
mod10000 の場合は、a^n の n として「4 以上かつ 500 と互いに素」であることが要求され
るので n=7 が最小
となるのではないでしょうかね？
ＧＡＩ さんからのコメントです。（令和４年６月１９日付け）
{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 の２つの集合内容が全く同一を示す。）
の結果となり、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
の対応で、２つの集合は同一を見ました。(#S=#T=42517)
（追記） 令和５年２月１４日付け
次の九州大学前期理系（２０１６）の問題は、合同式の適当な練習問題になるだろう。
問題 自然数ｎに対して、１０ｎ を１３で割った余りを ａｎ とおく。以下の問いに答えよ。
（１） ａｎ+1 は、１０ａｎ を１３で割った余りに等しいことを示せ。
（２） ａ1 、ａ2 、・・・、ａ6 を求めよ。
（３） 以下の３条件を満たす自然数Ｎをすべて求めよ。
(i) Ｎを十進法で表示したとき、６桁となる。
(ii) Ｎを十進法で表示して、最初と最後の桁の数字を取り除くと、２０１６となる。
(iii) Ｎは１３で割り切れる。
（解）（１） １０ｎ≡ａｎ （ｍｏｄ １３） 、１０ｎ+1≡ａｎ+1 （ｍｏｄ １３） より、
ａｎ+1≡１０・ａｎ （ｍｏｄ １３） なので、ａｎ+1 は、１０ａｎ を１３で割った余りに等しい。
（２） １０1≡１０ （ｍｏｄ １３） より、ａ1＝１０
ａ2≡１００≡９ （ｍｏｄ １３） より、ａ2＝９
ａ3≡９０≡１２ （ｍｏｄ １３） より、ａ3＝１２
ａ4≡１２０≡３ （ｍｏｄ １３） より、ａ4＝３
ａ5≡３０≡４ （ｍｏｄ １３） より、ａ5＝４
ａ6≡４０≡１ （ｍｏｄ １３） より、ａ6＝１
（３） 題意より、 Ｎ＝ｍ・１０5＋ｎ＋２０１６０ と書ける。
１０5≡４ （ｍｏｄ １３） 、２０１６０≡１０ （ｍｏｄ １３） なので、
Ｎ≡４ｍ＋ｎ＋１０≡０ （ｍｏｄ １３） であるためには、
（ｍ，ｎ）＝（２，８）、（３，４）、（４，０）、（５，９）、（６，５）、（７，１）、（９，６）
以上から、求めるＮは、
２２０１６８、３２０１６４、４２０１６０、５２０１６９、６２０１６５、７２０１６１、９２０１６６ （終）
以下、工事中！