Question

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

Answer 1

以下(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