5
$\begingroup$

How many squares are there modulo $2^n$?

If we would deal with $p^n$, where p an odd prime, then we could use Hensel's Lemma, which clearly doesn't work with $2^n$.

$\endgroup$

2 Answers 2

4
$\begingroup$

Starting from 8, the odd residues are given by $(-1)^k3^m$, so clearly, the squares are exactly of the form $3^{2m}$ which is a quarter of them. The even residues are squares if they are divisible by 4 and the quotient is a square modulo $2^{n-2}$.

So, you get $squares(2^n)=2^{n-3} + squares(2^{n-2})$ which is easily solved.

$\endgroup$
3
  • $\begingroup$ I can't see your proof. $\endgroup$
    – L.Fetahu
    Apr 22, 2014 at 22:03
  • $\begingroup$ @L.Fetahu Is there a question somewhere in your comment? $\endgroup$
    – Phira
    Apr 24, 2014 at 10:43
  • $\begingroup$ It is not really obvious that the odd residues modulo $2^n$ are of the form $(-1)^k3^m$. (I was able to prove this using the Lifting The Exponent Lemma.) Also, it is not trivial that this implies that the squares have to be of the form $3^{2m}$. You have to know that these numbers $k$ and $m$ are unique (up to a multiple of $2$ and $\text{ord}_{2^n}(3)=2^{n-2}$, respectively). Besides from this, it was interesting to learn something new from your answer and it was a nice exercise to prove your claims ;-) $\endgroup$ Apr 24, 2014 at 18:25
2
$\begingroup$

We have $(\mathbb Z/2^n\mathbb Z)^{\times}\cong C_2\times C_{2^{n-2}}$ where $C_m$ denotes the cyclic group of order $m$, where an isomorphism is given by $(-1)^a3^b\leftarrow (a,b)$. (Proof: see Thm. 6.1, p. 25 here: http://web.mit.edu/~holden1/www/math/number-theory.pdf. Basically, show by induction that $3^{2^k}=2^{k+2}j+1$ where $j$ is odd.)

The elements in $C_2\times C_{2^{n-2}}$ that are divisible by 2 are exactly $0\times 2C_{2^{n-2}}$ which has cardinality $2^{n-3}$. We get the recurrence $\#\text{squares}(2^n)=2^{n−3}+\#\text{squares}(2^{n−2})$ as in Phira's answer.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .