4
$\begingroup$

To solve the simultaneous congruences $2n + 6m\equiv 2 \pmod{10}$ and $n + m\equiv -2 \pmod{10}$

I tried to add the two congruences together so I got: $3n + 7m\equiv 0 \pmod{10}$ But I am not sure if that's right and if it is, what to do next to calculate the two separate variables. If the question is like $n\equiv x \pmod y$ then it's simple enough to calculate

  • 0
    Welcome to the site, Jason. I took the liberty of editing your post---hope it's okay. If you're going to stick around (and we hope you do), it would be a good idea to learn some LaTeX typesetting conventions for mathematics. An easy way to do this is to find a post that has something like you want to say, clicking on "edit" below the post and then looking at the "source" document in edit mode. The window in which you post your question or answer has help options just above and to the right.2012-07-06

4 Answers 4

2

What you did can easily be justified by $ -2n - 6m \equiv -2 \pmod{10}, $ which gets you to $n + m \equiv -2n -6m \pmod{10}$, which is what you got. So $3n \equiv -7m \equiv 3m \pmod{10}$ and since $3$ is coprime to $10$, $3$ has a multiplicative inverse mod $10$ and so we can multiply out the $3$ on both sides. So $n \equiv m \pmod{10}$. Can you solve it now?

In case you are interested the multiplicative inverse of $3$ in this case is $7$.

1

Clearly, 2n+6m=10a+2 and n+m=10b-2 where a,b are some integers.

So,n=10b-2-m

Substituting, the value of m in the 1st, 2(10b-2-m)+6m=10a+2

Or, 4m=10a-20b+6

Or, 2m=5a-10b+3

Clearly, a must be odd=2c+1(say)

So,2m=5(2c+1)-10b+3 =>m=5(c-b)+4≡4(mod 5)

n=10b-2-(5(c-b)+4)=5(3b-c)-6≡-1(mod 5)≡4(mod 5)

0

You solve modular systems of equations mostly just like normal systems of equations -- the main difference is that you have to be careful about things like division and square roots.

Guessing* at how you would solve the system normally, I'm going to say that you solved the second equation for $m$ and plugged it into the first equation. So, you have

$ m \equiv -2 - n \pmod{10}$

and so

$ 2n + 6m \equiv 2n + 6(-2 - n) = 2n - 12 - 6n = -4n - 12 \pmod{10}$

and thus

$-4n - 12 \equiv 2 \pmod{10}$

or

$-4n \equiv 14 \pmod{10}$

You would normally like to divide by $-4$ here. I'm going to assume you're familiar with the algorithm to find modular inverses of numbers -- e.g. if you want to divide by $3$, you could solve for its inverse and find $3 \cdot 7 \equiv 1 \pmod{10}$ so that multiplication by $7$ has the effect of dividing by $3$.

The problem here is that $4$ is not relatively prime to $10$ -- both are divisible by 2. You've probably seen the method to deal with this fact but have just forgotten, so I'll restate it here. If you can divide everything by the gcd, then you do that, and get

$-2n \equiv 7 \pmod 5$

If we were unable to divide everything by the gcd (e.g. if the right hand side was 13 instead of 14), then the equation has no solutions.

Anyways, you should now be able to solve $-2n \equiv 7 \pmod 5$, and thus finish solving the problem.

*: It's usually a good idea to explain how you think about going about a problem, so that the answers you get can be tailored to the way you think. This can often give better results than someone answering with a method geared towards how they think.

  • 0
    Depending on the context, it would be fine to just say $n \equiv -7/2 \pmod 5$ -- specifically when the speaker and audience is expected to be very familiar with modular arithmetic. However, as you're presumably a student learning the topic, writing $n = -7/2 \pmod 5$ probably wouldn't be accepted.2012-07-06
0

Sometimes a "naive" approach can give some nice insights: $\,\,(1)\,\,2n+6m=2\pmod {10}\Longrightarrow 2n+6m=2+10k\,\,,\,k\in\mathbb Z\Longrightarrow n+3m=1+5k\Longrightarrow$ $\Longrightarrow n=1-3m+5k\Longrightarrow n+m=-2\pmod {10}\Longrightarrow \,(2)\,\,n+m=-2+10x\,\,,\,x\in\mathbb Z$ and substituing we get $1-3m+5k+m=-2+10x\Longrightarrow5k-2m=-3+10x\Longrightarrow 2m=3+5(k-2x)$ and since $\,2^{-1}=3\pmod 5\,$ , we have $\,2m=3\pmod 5\Longrightarrow m=4\pmod 5\Longrightarrow n=1-3\cdot 4\pmod 5=4\pmod 5$ Thus, $\,n,m\in\{4,9\}\pmod {10}\,$ . Any choice here will satisfy equation (1), yet equation (2) requires that both $\,n,m\,$ hare the same modulo 10 ,so the solution to the system is $\,\{\,(n,m)\;\;:\;\;n=m=4\pmod {10}\,\,or\,\,n=m=9\pmod {10}\,\}$