最も集客を集めるべき乗は？
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
と一致することに驚いた。
この２つの関係はどうなっているんだろう？
> この列がA075821に載る。(内容的には他の視点で集まった数列）
コメントを読む限り、まさしく 21 乗の下 2 桁として作られた列のようですが。
> 不思議なことにkは他のも
k=41,61,81,101,････
でも同じaが並んだ。
> またmod 1000
ではk=101,201,301,････
えっと、先日の問題の流れを受ければこの結果はごく自然なものに思えますが、どこを不思議と思っておられるのでしょうか？
a41=a21*a20≡a*a^20=a21≡a （mod 100)
そうか不思議でもなんでもないですね。
A122987での説明がよくわからないのですが、これが
a^101≡a (mod 1000)
で集めるaと同じになるのはどうしてなのかな？
という意味で問いかけておりました。
なるほど確かに立方数の下 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)
上２つの広がりは起こりませんでした。
おそらくですが、
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)
