◆愛知県 Kernighan さんからの解答。
【問題１】
a≡1 (mod m) より a=km+1 (k≧0 は整数）とかける。
al
=(km+1)l
=(km)l+l(km)l-1+...+l(km)+1
≡1 (mod m)より
an-1+an-2+...+1≡1+1+...+1≡n (mod m)
【問題２】
al=(km+1)l≡l(km)+1 (mod m2) より
am-1+am-2+...+1
≡{(m-1)(km)+1}+{(m-2)(km)+1}+...+1
≡{((m-1)+(m-2)+...+1)(km)}+{1+...+1}
≡(m(m-1)/2)(km)+m
m は奇数だから 2 | (m-1)
従って
≡m (mod m2)
【問題３】
m,n,b が (1) 2n=bm+1 を満たすとする。
b は奇数だから b≡±1 (mod 4) であるが
b≡1 とすると (1)から 0≡2 (mod 4) で矛盾。
b≡-1とすると (1)から
0≡(-1)m+1 (mod 4)なので m は奇数。
bm+1=(b+1)(bm-1-bm-2±...-1) で
(bm-1-bm-2±...-1)＞1 だから (1)より偶数であるが、奇数の奇数個の和と差は奇数だから矛盾。
【問題４】
まず a≧3 として、m,n,a,p が
(2) am-pn=1 を満たすとする。
(2)より
pn=am-1=(a-1)(am-1+...+1)
a-1＞1,am-1+...+1＞1 だから
(3) a-1=pn1
(4) am-1+...+1=pn2
n1+n2=n, n1＞0, n2＞0 とかける.
(3)と問題１より
am-1+...+1≡m (mod p) だから
(4) より m≡0 (mod p)
つまり m=kp とかける。
(2)より
pn
=akp-1
=(ap-1)((ap)k-1+...+1) だから
(ap-1)＞1なので
(5) pn3=ap-1=(a-1)(ap-1+...+1) とかける。
a-1＞1,ap-1+...+1＞p なので (5)より
(6) a-1=pn4
(7) ap-1+...+1=pn5
n5≧2
(6)と問題２よりpが奇数ならば
ap-1+...+1≡p (mod p2)だから
(7)よりp≡0 (mod p2) で矛盾。
p=2 とすると、(5)は
2n3=(a-1)(a+1) であるから
(8) a-1=2s
(9) a+1=2t
(9)-(8) から
(10) 2=2t-2s=2s(2t-s-1)
(10)をみたす(s,t)は(1,2)のみなので
(m,n,a,p)=(2,3,3,2)
次にa=2の場合は問題３よりp≧3ならば条件をみたすm,n,a,pは存在しない。
p=2の場合は条件は
2m-2n=1 で、0≡1 (mod 2) で矛盾。
素数という条件は強力ですね。