a2a=a(a1)a^2-a=a(a-1)なので、a=ka=kは条件を満たす。よって、解が存在しないことはありえない。しかし、a=2,3,ka=2, 3, \cdots kと全て順番に調べると、計算量が最大でO(k)O(k)になってしまうので、他の解法を考える。\\

k2k\geq2より、kkは最低でも1つの素因数を持つ。そのうちの1つをppとし、kkは素因数ppnn個持つとする。ユークリッドの互除法により、gcd(a,a1)=gcd(a1,1)=1{\rm gcd}(a,a-1)={\rm gcd}(a-1,1)=1 なので、aaa1a-1が両方とも素因数ppを持つことはない。よって、aaa1a-1のうちどちらか一方のみが素因数ppnn個持つ、すなわちpnp^nの倍数である。 kkの持つ他の素因数についても同様のことが成り立つので、kkの持つ素因数の種類数をmmとすると、kkの持つ全ての素因数をaaa1a-1に割り当てる方法は2m2^m通りとなる。\\

それぞれの割り当て方について、a,a1a,a-1に割り当てられた素因数の積をそれぞれM,NM,Nとすると、a=Mx,a1=Ny(x,ya=Mx,a-1=Ny(x,yは整数))と書ける。2式からaaを消去するとMxNy=1Mx-Ny=1となるので、Mx1(mod N)Mx\equiv1({\rm mod}\ N) よって、MMmod N{\rm mod}\ Nにおける逆元をx0(0x0<N)x_0(0\leq x_0<N)とすると、xx0(mod N)x\equiv x_0({\rm mod}\ N) なのでa=Mx=kl+Mx0(la=Mx=kl+Mx_0(lは整数))と書ける。a2a\geq 2であるから、aaの最小値は、Mx02Mx_0\geq 2ならばMx0,Mx_0, そうでないならk+Mx0k+Mx_0となる。(M(MNNには共通素因数がないので、MMmod N{\rm mod}\ Nにおける逆元は常に存在する。逆元についてはこちらを参照。))\\

kkに対する素数判定はO(k)O(\sqrt{k})で行える。また、小さい方からnn番目までの全素数の積をPnP_nとおくと、P12>1012P_{12}>10^{12}なので、この問題の制約ではm11m\leq11となる。よって、O(2m)O(2^m)でもTLEの心配はない。

(参考)本問は、東京大学2005年度学部入試の理系数学第4問を一般化したものである。

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378