he*he=she的无穷个解的通项公式

优秀书籍

编程之美4.10拓展问题2

解方程：he*he=she

解：s*100=she-he=he*he-he=he(he-1)

因为（he,he-1）=1，100=4*25

所以4|he,25|he-1或者4|he-1,25|he

如果4|he,25|he-1，那么he=76，s=57，矛盾

如果4|he-1,25|he，那么he=25，s=6

综上，唯一解是25*25=625

推广：

在k进制下求解he*he=she

解：同上可得，s*k*k=he(he-1)

因为（he,he-1）=1

所以k=u*v,(u,v)=1,he=a*u*u,he-1=b*v*v,s=a*b

所以a*u*u=b*v*v+1即a是u*u mod v*v 的逆元

即a是（u mod v的逆元）的平方

注：这里我们得到一个有趣的小结论，he一定是完全平方数！

现在问题转化为，求u,v,b 使得u>1,v>1,（u,v）=1，取c是u mod v的逆元的话，有b*v*v=(c*u-1)(c*u+1)

且c*c*b<u*v（这个是因为s是k进制1位数，而he=c*c*u*u一定是k进制2位数，不需要限制条件）

设c*u-1=d*v那么b*v=d(d*v+2)

所以v|2*d

现在问题转化为，求正整数u,v,c,d,g,使得c*u=d*v+1且2*d=v*g且c*c*(g+d*d)<u*v

这样的五元组和方程he*he=she的解是一一对应的

u*v进制，he=c*c*u*u，s=c*c*(g+d*d)，很明显这样的he和she是满足he*he=she的，而上面的整个过程也说明了，he和s只能对应上述五元组，所以是一一对应的。

像这样的解有很多很多，最小的解是6进制下13*13=213，对应c=d=g=1,u=3,v=2

如果取g=1，那么c*u=2*d*d+1,v=2*d，不等式c*c*(g+d*d)<u*v恒成立

对于任意的d，都可以找到合适的c,u,v满足条件

比如c=1,u=2*d*d+1,v=2*d

所以对于任意d，取u=2*d*d+1,v=2*d，he=u*u，s=d*d+1，都有：

在u*v进制下he*he=she，这就得到了无穷个解，当然，并不是所有的解。

比如，d=1，6进制下13*13=213

d=2，36进制下29*29=529

d=1和d=2是仅有的不需要借助字母就可以表达的情况

实际上，h=d，e=u=2*d*d+1，s=d*d+1

这就是标题所说的无穷个解的通项公式，但是并不是所有解的通项公式。

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/53494507