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.

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

  • $\begingroup$ I can't understand the second step, could you explain it better ? $\endgroup$ – Hedwig May 8 '14 at 16:56
  • $\begingroup$ @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). $\endgroup$ – user1337 May 8 '14 at 16:58
  • $\begingroup$ can you do that with congruence ? $\endgroup$ – Hedwig May 8 '14 at 17:01
  • $\begingroup$ @Antaraz $n \equiv 0 \pmod{292}$. $\endgroup$ – user1337 May 8 '14 at 17:02
  • $\begingroup$ Ha, that's the result i mean the whole work ? $\endgroup$ – 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}$$

  • $\begingroup$ $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 ? $\endgroup$ – 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}$

  • $\begingroup$ Did you mean $2j\color{blue}{+}1$? $\endgroup$ – Anant May 9 '14 at 7:03
  • $\begingroup$ @Anant I'm not sure what you mean. $\endgroup$ – Bill Dubuque May 10 '14 at 2:00
  • $\begingroup$ 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$? $\endgroup$ – Anant May 10 '14 at 8:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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