1
$\begingroup$

Let $m ≥ 1$, and let $a$ be an integer. Prove that $a^ 2 \equiv 4\mod 3^m$ if and only if $a \equiv 2\mod 3^m$ or $a \equiv −2\mod 3^m$.

I know that i'm supposed to find $m$ factors $3$ in $a^ 2 − 4 = (a − 2)(a + 2)$, but I don't even know how to get started.

Anyone with tips to prove this?

$\endgroup$

marked as duplicate by Bill Dubuque modular-arithmetic Feb 22 at 14:33

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

I guess that the "if direction" in your statement should not be a problem, if else let me know. For the converse, you know that $3^m$ divides $a^2-4$ as $a^2 \equiv 4 \, \text{mod} \, 3^m$. As you already said, you can factor $a^2-4 = (a-2)(a+2)$ so you know that $3^m \mid (a-2)(a+2)$. Now think about what it would mean, if $3$ would divide both $a-2$ and $a+2$ and show that this is not possible. Then conclude that $3^m$ divides either $a-2$ or $a+2$ and your claim follows.

$\endgroup$
  • $\begingroup$ So what you're saying is, find some example for $a$ that divides either $a-2$ or $a+2$, but not both (like $a=11$). But you can also find values for $a$ that do not work (like $a=12$) right? $\endgroup$ – Flint Feb 22 at 13:58
  • $\begingroup$ No what I meant is the following: By the assumptions you get that $3^m \mid (a-2)(a+2)$, so in particular you get $3 \mid (a-2)$ or $3 \mid (a+2)$, since $3$ is a prime number. Lets assume w.l.o.g. that $3 \mid (a-2)$. Now you have to conclude that $3$ does not divide $a+2$. But now, as $3^m$ divides $(a-2)(a+2)$, you get that $3^m$ divides $a-2$ (in the prime factorization of the product, no power of $3$ appears in the prime factorization of $a+2$, so $3^m$ has to appear in the prime factorization of $a-2$). $\endgroup$ – Wos07573 Feb 22 at 16:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.