证明：k>2时,同余式x^2≡1(mod2^k)恰好有四个不同余的解,它们是x≡±1或者±(1+2^(k-1))(mod2^k),k>2;k=1时,该同余式有一个解；k=2时,该同余式有两个不同的解.

Question

证明：k>2时,同余式x^2≡1(mod 2^k)恰好有四个不同余的解,它们是x≡±1或者±(1+2^(k-1))(mod 2^k),k>2;k=1时,该同余式有一个解；k=2时,该同余式有两个不同的解.

Answer 1

x^2≡1(mod 2^k)
∴x^2=n·2^k+1①
当n=0时,
x^2=1
x=±1
当n≠0时,
设x=±（2^p）+q
（此处能做到的原因是用任意整数x总能去掉2的最大次数,差为q,比2^q小,同时考虑到x可能为负数,因而减数2^p加上±号.）
则代入①
2^(2p)+2q·2^p+q^2=n·2^k+1
∴q=±1
2^(2p)±2·2^p+1=n·2^k+1
2^(2p)±2^(p+1)=n·2^k
2^(p+1)·(2^(p-1)±1)=n·2^k
∴p+1=k
p=k-1
∴x=±（2^p）±1=±2^(k-1)±1
得证!
【经济数学团队为你解答!】