We know that the congruence x^2 1 mod 8 holds for any odd x. Show that, if a is

Question

We know that the congruence x^2 1 mod 8 holds for any odd x.

Show that, if a is odd and the congruence x^2 a mod 2^k has exactly the solutions x ±t mod 2^(k1) ,

then the congruence x^2 a mod 2^(k+1) has either x ±t mod 2k or else x ±(2^(k1) + t) mod 2^k as its only solutions.

Hint: Show first that one of these pairs must be a solution.

Remark: By Bressoud’s remark that c^2 1 mod 8 when c is odd, we may assume that k 2. That remark, together with this problem, shows that we will have 4 distinct solutions modulo 2^k of the congruence x^2 a mod 2^k for every k when a 1 mod 8 and otherwise no solutions for odd a for any k > 0 at all.

Explanation / Answer

Existence is easy:

The solutions are {1,2k11,2k1+1,2k1}{1,2k11,2k1+1,2k1}.

Squaring them gives {1,22k22k+1,22k2+2k+1,22k2k+1+1}{1,22k22k+1,22k2+2k+1,22k2k+1+1}.

Reducing (mod2k)(mod2k) gives 1 in each case (given that 2k2>k+12k2>k+1, which forces k3k3).

For uniqueness you could use the fact that the units group of Z/2kZZ/2kZ is C2×C2k2C2×C2k2 on the other hand that also gives existence..

Existence is easy:

The solutions are {1,2k11,2k1+1,2k1}{1,2k11,2k1+1,2k1}.

Squaring them gives {1,22k22k+1,22k2+2k+1,22k2k+1+1}{1,22k22k+1,22k2+2k+1,22k2k+1+1}.

Reducing (mod2k)(mod2k) gives 1 in each case (given that 2k2>k+12k2>k+1, which forces k3k3).

For uniqueness you could use the fact that the units group of Z/2kZZ/2kZ is C2×C2k2C2×C2k2 on the other hand that also gives existence..

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.