# How to solve the equation $n^2 \equiv 0 \pmod{584}$?

Well, I've confused when trying to solve this equation can anybody help me :

$n^2 \equiv 0 \pmod{584}$

I tried to factorize the $584$ i got $584=2^3\times73$.

so $n^2$ has to be divisible by $2^3$ and $73$ in this same time.

here i get stuck.

• Do you know that if $p$ is a prime, then $p|n^{2} \iff p|n.$ – Indrayudh Roy May 8 '14 at 16:50
• Do you know about quadratic residues and non-quadratic residues? – Amy May 8 '14 at 16:51
• @Amy i don't think so, what are they ? – Hedwig May 8 '14 at 16:54
• $n$ has to be an integer? Because if not, then the solution is simply $n=\sqrt{584k}$ for every positive integer $k$. – barak manos May 8 '14 at 17:15

You're looking for integers $k$ such that

$$n^2=2^373^1k$$

However, a number is a square iff all of its prime exponents are even. Thus $k$ must be of the form $$k=2 \cdot73 \cdot l^2$$ where $l$ is an arbitrary integer.

By taking the square root you will find that

$$n=2^2 \cdot 73^1 \cdot l$$

where $l \in \mathbb{Z}$.

• I can't understand the second step, could you explain it better ? – Hedwig May 8 '14 at 16:56
• @Antaraz At the beginning, the exponent of $2$ in $n^2$ is odd. That's why $k$ must have an odd power of $2$ as well. The same goes for $73$. (Notice that $l^2$ can only have even prime powers). – user1337 May 8 '14 at 16:58
• can you do that with congruence ? – Hedwig May 8 '14 at 17:01
• @Antaraz $n \equiv 0 \pmod{292}$. – user1337 May 8 '14 at 17:02
• Ha, that's the result i mean the whole work ? – Hedwig May 8 '14 at 17:03

If $p^{2k+1} \vert n^2 \implies p^{k+1} \vert n$. Hence, $2^3 \vert n^2 \implies 2^2 \vert n$. Similarly, $73 \vert n^2 \implies 73 \vert n$. Since $\gcd(4,73) = 1$, we have $292 \vert n$.

Hence, $n = 292m$, where $m \in \mathbb{Z}$.

$n^2\equiv0\pmod{584}$ iff $n^2\equiv 0\pmod {73}$ and $n^2\equiv 0\pmod 8$.

As $73$ is a prime, $n^2\equiv 0$ iff $n\equiv 0\pmod {73}$.

To make a long story short, we could simply try all $n\pmod 8$ and check $n^2\pmod 8$. Unsurprisingly, we find that $n^2\equiv0\pmod 8$ iff $n\equiv 0\pmod 8$ or $n\equiv 4\pmod 8$. So $n^2\equiv0\pmod 8$ iff $n\equiv 0\pmod 4$.

(Actually, the general solution modulo prime powers $p^r$ with $r\ge1$ is that $n^2\equiv 0\pmod {p^r}$ iff $n\equiv 0\pmod{p^{\lceil r/2\rceil}}$, Can you see, why?)

By the chinese remainder theorem, $$n^2\equiv 0\pmod{584}\quad\iff\quad n\equiv 0\pmod{292}$$

• $n\equiv 0 \pmod{73}$ and $n\equiv 0 \pmod{4}$ $\implies$ $4n\equiv 0 \pmod{292}$ and $73n\equiv 0 \pmod{292}$ $\implies$ $77n\equiv 0 \pmod{292}$, is that work ? – Hedwig May 8 '14 at 17:51

${\bf Hint}\ \ {\rm If}\ \ p\ \ {\rm is\ prime,}\ \ n = p^{\large k} m,\,\ p\nmid m\ \ {\rm then}\ \ p^{\large 2j-1}\!\mid n^{\large 2}\!\iff\! \color{#0a0}{p^{\large 2j}\mid n^{\large 2}}\!\iff \color{#c00}{p^{\large j}\mid n},\$ since

$$\begin{eqnarray}\,\ p^{\large 2j-1}\!\mid n^{\large 2}\! = p^{\large 2k} m^{\large 2} \!\iff\! 2j\!-\!1\le 2k &\iff& \ \color{#0a0}{2j\le 2k} &\iff& \ \color{#c00}{j\le k}\\ &\overset{\phantom{I^I}}\iff& \color{#0a0}{p^{\large 2j}\mid \smash[b]{\underbrace{p^{\large 2k}m^2}_{\Large n^2}}}\!\! &\iff& \color{#c00}{p^{\large j}\mid \smash[b]{\underbrace{p^{\large k}m}_{\Large n}}} \\ \\ \end{eqnarray}$$

by the Fundamental Theorem of Arithmetic (existence and uniqueness of prime factorizations)

$\!\begin{eqnarray}{\rm Therefore}\ \ \ 2^3\cdot 73\mid n^2 &\iff& 2^3\mid n^2,\,\ 73\mid n^2 \ &&\text{by lcm = product for coprimes}\\ &\iff& \color{#c00}{2^2\mid n,\ \ \ 73\mid n}&&\text{by above Lemma}\\ &\iff& 2^2\cdot 73\mid n &&\text{by lcm = product for coprimes} \end{eqnarray}$

• Did you mean $2j\color{blue}{+}1$? – Anant May 9 '14 at 7:03
• @Anant I'm not sure what you mean. – Bill Dubuque May 10 '14 at 2:00
• I didn't understand how $2j-1 \le 2k \implies 2j \le 2k$ and thought that you probably meant $2j+1 \le 2k \implies 2j \le 2k$. That is, why does $p^{2j-1} \mid n^2 \implies p^{2j} \mid n^2$? – Anant May 10 '14 at 8:24