同余方程问题,数论高手请进
同余方程问题,数论高手请进
证明5X²+11Y²≡1(mod m)对任何正整数m都有解
首先考虑m为素数的情形
若5或11中有一个modm的二次剩余,不妨设为5
I={r1,r2,...r[(m+1)/2]}为modm的所有二次剩余
由勒让德符号定义的运算(或二次剩余的欧拉判别法)知,r1为二次剩余时5*r1亦为二次剩余
且5*ri不同余于5*rj,如果ri不等于rj
I1={5r1,5r2,...5r[(m+1)/2]}为modm的所有二次剩余
即5x^可以取I1中任意值
易知1属于I
则方程5X²≡1(mod m)有解,再取y=0即可
若5或11都不是modm的二次剩余
r1为二次剩余(r1非0)时5*r1和11*r1为二次非剩余
即I2={5r1,5r2,...5r[(m+1)/2]}为modm的所有二次非剩余和{0}的并集
下面应用反证法,若原方程无解
则I2/{0}中任意两元素和不为m+1
考虑下列(m-1)/2个集合
{2,m-1}{3,m-2}{(m-1)/2,(m+3)/2}和{(m+1)/2}
I2/{0}中(m-1)/2个元素皆取自此(m-1)/2个集合
若有一个集合中同时含有两个I2/{0}中元素
则方程5X²≡i(mod m)11Y²≡m+1-i(mod m)皆有解
原方程亦有解
若任一集合中不同时含有两个I2/{0}中元素
则(m+1)/2为I2/{0}中元素
方程5X²≡(m+1)/2(mod m)11Y²≡(m+1)/2(mod m)皆有解
原方程亦有解
以上证明了m为质数时方程有解
下面证明m为质数幂时方程有解
m=p^n,对指数n归纳(不考虑p=2,5,11时情形,这些情形的证明很容易)
n=k时成立,n=k+1时
5X²≡i+t*p^k(mod m)
计x1=x,x2=x+p^n,x3=x+2*p^n.xp=x+(p-1)p^n
以上p个数代入方程左端modm两两不同余,
必有一j使xj满足5xj^≡i(mod m)
对于11同理,则n=k+1时亦得证
对于一般的m,对m进行质因数分解,
m=p1^a1*p2^n2*...
计m1=p1^a1
m2=...
(xi,yi)为5xi^+11yi^≡1(mod mi)的解
考虑一次同余方程组
x=x1(modm1)
x=x2(modm2)
...(此处=为同余号)
由中国剩余定理
x有解
对y同理
于是(x,y)即为满足条件的解
初涉数论,如有漏洞请指出,欢迎切磋探讨.这道题真的很难,不知楼主是在哪里看到的?