昨天,有一个小学生问了我一道小学奥数题,就是同余问题,引发我如下思考:
X^2+1=0我们认为它在(mod 5)里有两个解:2和3。因为2^2+1=0(mod 5),3^2+1=0(mod 5)是很明显的。
但X^2+1=0在(mod 7)里无解。
这一点不是很奇怪么?因为X^2+1=0在实数和复数里面的解的个数是比较明显的,但是在(mod n)的时候好像就不明显了。
我们不妨取一个质数p,考虑(mod p)的情形,当p变化时我们来列出解的个数的变化:
p=2,1个
p=3,0个
p=5,2个
p=7,0个
p=11,0个
p=13,2个
p=17,2个
p=19,0个
p=23,0个
……
小学奥数题是要求我们答出上述的规律。
由于X^2+1=0这个方程是个二次方程,上述的规律就比较简单,我就不多说了。
现在,我们看一下更复杂的情况,对于X^3-X-1=0(mod p)进行同样的操作:
p=2,0个
p=3,0个
p=5,1个
p=7,1个
p=11,1个
p=13,0个
p=17,1个
p=19,1个
p=23,2个
……
p=59,3个
……
你是不是突然发现这个规律就一点也看不出了?
X^2+1=0我们认为它在(mod 5)里有两个解:2和3。因为2^2+1=0(mod 5),3^2+1=0(mod 5)是很明显的。
但X^2+1=0在(mod 7)里无解。
这一点不是很奇怪么?因为X^2+1=0在实数和复数里面的解的个数是比较明显的,但是在(mod n)的时候好像就不明显了。
我们不妨取一个质数p,考虑(mod p)的情形,当p变化时我们来列出解的个数的变化:
p=2,1个
p=3,0个
p=5,2个
p=7,0个
p=11,0个
p=13,2个
p=17,2个
p=19,0个
p=23,0个
……
小学奥数题是要求我们答出上述的规律。
由于X^2+1=0这个方程是个二次方程,上述的规律就比较简单,我就不多说了。
现在,我们看一下更复杂的情况,对于X^3-X-1=0(mod p)进行同样的操作:
p=2,0个
p=3,0个
p=5,1个
p=7,1个
p=11,1个
p=13,0个
p=17,1个
p=19,1个
p=23,2个
……
p=59,3个
……
你是不是突然发现这个规律就一点也看不出了?