Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have no clue how to do this exactly. Is there a systematic way of doing this or you just have to do it by trial and error?

$n^2 \equiv 9 \pmod {72}$

to $n \equiv a \pmod b$?

share|improve this question

6 Answers 6

up vote 1 down vote accepted

$n^2\equiv9\pmod{72}$ iff $72\mid n^2-9$, i.e., iff $n^2-9=72k$ for some integer $k$. Then $n^2=72k+9$ is divisible by $9$ and hence by $3$. Since $3$ is prime, this implies that $3\mid n$, and we can write $n=3m$ for some integer $m$. Now we have $9m^2=72k+9$, or $m^2=8k+1$, i.e., $m^2\equiv1\pmod 8$. It’s staightforward to verify that this congruence is satisfied precisely when $m$ is odd, say $m=2\ell+1$. Thus, the full set of solutions is given by $n=3m=3(2\ell+1)=6\ell+3$, which can be rewritten as the congruence $n\equiv3\pmod6$.

With more experience you would know that since $72=8\cdot9$, the congruence $n^2\equiv9\pmod{72}$ implies the congruences $n^2\equiv9\pmod8$ and $n^2\equiv9\pmod9$ and could start working with them immediately. (In fact $n^2\equiv9\pmod{72}$ is equivalent to the conjunction of $n^2\equiv9\pmod8$ and $n^2\equiv9\pmod9$, since $\gcd(8,9)=1$.)

share|improve this answer

The congruence forces $n$ to be divisible by $3$, so $n=3k$. Then $n^2\equiv 9\pmod{72}$ iff $9k^2\equiv 9\pmod{72}$ iff $k^2\equiv 1\pmod{8}$.

The solutions to this last congruence are $1$, $3$, $5$, $7$ (modulo $8$). This can be expressed more simply as $k\equiv 1\pmod{2}$. Then we get $n=3k\equiv 3\pmod{6}$.

share|improve this answer

In this case, since $\,9\,$ is a perfect integer square much smaller than $\,72\,$ , the beginning of the solution is pretty straightforward:

$$n^2=9\pmod{72}\Longrightarrow n=\pm 3\pmod {72}$$

But since $\,72\,$ is not a prime there may be other solutions, and in fact we also have, say

$$n^2=9\pmod{72}\Longrightarrow n=\pm 9\pmod{72}$$

share|improve this answer

Note that $72=8\cdot 9$ and that $n^2\equiv 9\pmod{72}$ implies (and is in fact equivalent to) $n^2\equiv 9\pmod 9$ and $n^2\equiv 9\pmod 8$. The first simplifies to $n^2\equiv 0\pmod 9$, i.e. $3^2|n^2$. This is equivalent to $3|n$. The other equation simplifieds to $n^2 \equiv 1\pmod 8$. You may try these few cass by hand, but one should know this special property of the prime $2$:

  • The square of an even number is always $\equiv 0\pmod 4$
  • The square of an odd number is always $\equiv 1\pmod 8$

Thus $n^2\equiv 9\pmod{72}$ is the same as $n\equiv 0\pmod 3$ and $n\equiv 1\pmod 2$, i.e. $$n\equiv 3\pmod 6.$$

Check: If $n=6k+3$, then $n^2=36 k^2+36 k + 9=36\cdot k(k+1)+9$. Since one od the numbers $k, k+1$ is even, $k(k+1)$ is even and $36k(k+1)$ is a multiple of $72$.

share|improve this answer

$n^2 = 72 M + 9 = 9(8M+1)$. Hence, $9 \vert n^2 \implies 3 \vert n$. Hence, $n = 3k$. This gives us that $k^2 = 8M+1 \implies k$ is odd (since any odd square is of the form $8k+1$ and even square is of the form $8k$ or $8k+4$). Hence, $$n = 3(2 \ell + 1) = 6 \ell + 3 \equiv 3 \pmod{6}$$

share|improve this answer

Note that $n^2\equiv 9 \pmod {72}$ is equivalent to $$ (n-3)(n+3)\equiv 0 \pmod {72} $$ So it is sufficient to solve the simultaneous congruences $$ (n-3)(n+3)=0\pmod 8 $$ and $$ (n-3)(n+3)\equiv 0 \pmod 9 $$ The second congruence is true iff $n$ is divisible by $3$, because then both $n-3$ and $n+3$ are divisible by $3$, so their product is divisible by $9$. If $n$ is not divisible by $3$, then neither $n-3$ nor $n+3$ is divisible by $3$, so their product isn't. Thus, $n\equiv 0 \mod 3$. In the first congruence, we similarly obtain that $n$ must be odd. We claim that this is also sufficient. Indeed, since clearly $n-3$ and $n+3$ are both even, assume that they are both $2 \pmod 4$. This is clearly impossible because they have a difference of $6$. Thus, one of $n-3$ and $n+3$ must be divisible by $4$, and the other is even, so their product is $0 \pmod 8$. Then $n\equiv 1 \pmod 2$. Then, the set of solutions is just all $n$ that satisfies $n\equiv 1\pmod 2$ and $n \equiv 0 \pmod 3$, which is equivalent to $n \equiv 3 \mod 6$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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