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

Question

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.

Answer 1

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}$.

Answer 2

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}$.

Answer 3

$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}$$

Answer 4

${\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}$