题目

使得5的N次方+N能被31整除的最小正整数N为30,则下一个比30大的满足条件的正整数N的值为?

提问时间：2020-12-20

答案

以下(mod ..)之前的等号表示同余符号
5^0=1(mod 31)
5^1=5(mod 31)
5^2=25(mod 31)
5^3=125=1(mod 31)
所以5模31的阶为3
5^30+30=0(mod 31)
设下一个比30大的满足条件的正整数N=30+k,k>=1
5^(30+k)+30+k=5^k+k-1=0(mod 31)
当k=0(mod 3)时
5^k+k-1=1+k-1=k=0(mod 31)
k最小为3*31=93
当k=1(mod 3)时
5^k+k-1=5+k-1=k+4=0(mod 31)
k=27(mod31)
由中国剩余定理可求得k=58(mod 93)
所以k最小为58
当k=2(mod 3)时
5^k+k-1=25+k-1=k+24=0(mod 31)
k=7(mod31)
由中国剩余定理可求得k=38(mod 93)
所以k最小为38
综上所述k最小为38
所以下一个比30大的满足条件的正整数N=30+k=68