8
$\begingroup$

Assume we are given the problem of say finding all squares modulo $3^4$. Is there any efficient way to compute this without having to check a ton of cases? For just a prime we can use quadratic reciprocity, but that doesn't do any good here.

A problem like this was asked on an oral exam in my program (the number was $4000$, so one had to apply the Chinese remainder theorem first and then solve two questions like this), so I guess the professor thought that this is something that one should be able to work out on the black board pretty quickly.

The only approach I know is to first find all squares modulo say $9$, which would give $0,1,4,7$, then look at the numbers:

$0,0+9,0+18,1,1+9,1+18,4,4+9,4+18,...$

and figure out which of these liftings are squares mod $27$. This quickly gets extremely annoying. Especially when having to lift these squares to $3^4$.

  • 2
    I don't know how to add a comment, so I'll post this as an answer. See [here](http://en.wikipedia.org/wiki/Quadratic_residue#Prime_power_modulus).2011-08-30
  • 6
    http://en.wikipedia.org/wiki/Hensel's_lemma2011-08-30
  • 0
    Did the oral exam ask for *all* squares mod 4000 or only for those that are coprime to 4000?2011-08-30
  • 1
    Hensel is the standard tool for finding roots of a fixed polynomial. The problem here is that the number of polynomials $X^2-a$ grows for the higher powers.2011-08-30
  • 0
    @Bill: All squares.2011-08-30

2 Answers 2