Solving linear system of congruences

[lveenis]

Homework Statement

Solver for n and m in the following equations:
2n + 6m \equiv 2 (mod 10)
n + m \equiv -2 (mod 10)

Homework Equations

The Attempt at a Solution

I've worked through several of these problems prior, including ones in the book and most take the form:
2n + 3m = 3 (mod 10)
n + 3m = -2 (mod 10)
or something similar, where it is easy to subtract one equation from the other and solve for one variable, then plug back in and solve for the other. Or cases where it's easy to multiply and then subtract. In this case though, my textbook explicitly says you cannot multiply the equation by a number that's not relatively prime with the modulus, so I'm at a loss for how to cancel out a variable to solve these equations. This multiplying / subtracting or adding method is all we've been shown. I would greatly appreciate some advice on how to approach the problem!

 

[Mark44]

It's been many years since I took a number theory class, so I might be offbase here.
What about dividing the first equation by 2? That's the same as multiplying by 1/2, which would seem to be relatively prime to 10.

 

[lveenis]

We actually went over an example like that in class where we showed at if:
ac = bc (mod n) and the gcd(a,n) = 1, then a = b (= meaning congruent)
otherwise it's not valid.
Correct me if I'm wrong, but in this case c would be 2 and n would be 10, and since those are not relatively prime you can't divide it. I could be way out in left field here, this is just the first one of these questions I'm totally stumped on..

 

[Dick]

Well, I haven't done these for a while either, but 2n+6m=2 (mod 10) does mean that either n+3m=1 (mod 10) or n+3m=6 (mod 10). Doesn't it? How about splitting it into cases?

 

[lveenis]

I apologize if this is a dumb question, but how do you get the second case?
I'm still struggling with this, I know there obviously are solutions because just looking at at n = m = 4 is one possible solution.

 

[Dick]

I apologize if this is a dumb question, but how do you get the second case?
I'm still struggling with this, I know there obviously are solutions because just looking at at n = m = 4 is one possible solution.

That's ok. 2k=2 (mod 10) has two solutions. k=1 and k=6. 2*6=2 (mod 10). 2 doesn't have an inverse mod 10. But if you know 2k=2 (mod 10) you do know something about k.

 

[SammyS]

Homework Statement

Solver for n and m in the following equations:
2n + 6m \equiv 2 (mod 10)
n + m \equiv -2 (mod 10)

Homework Equations

The Attempt at a Solution

I've worked through several of these problems prior, including ones in the book and most take the form:
2n + 3m = 3 (mod 10)
n + 3m = -2 (mod 10)
or something similar, where it is easy to subtract one equation from the other and solve for one variable, then plug back in and solve for the other. Or cases where it's easy to multiply and then subtract. In this case though, my textbook explicitly says you cannot multiply the equation by a number that's not relatively prime with the modulus, so I'm at a loss for how to cancel out a variable to solve these equations. This multiplying / subtracting or adding method is all we've been shown. I would greatly appreciate some advice on how to approach the problem!

Try adding the equations together.

2n+6m\equiv2(\mod 10)

n+m\equiv-2(\mod 10)

Resulting congruence: 3n+7m\equiv-6(\mod 10)

Multiply that result by 3.

Add that and n+m\equiv-2(\mod 10)\ .

 

[lveenis]

Thanks for the replies everyone! SammyS, I wasn't sure if that was valid to do, but it seems to give me correct solutions. One note: adding the two gives 3n + 7m = 0 (mod 10). But solving using that equation as you proposed gave me the solutions n = m = 4 and n = m = 9, I'm not sure if you solved it and could tell me if that's all the solutions? Thank you everyone for your help!

 

[SammyS]

Thanks for the replies everyone! SammyS, I wasn't sure if that was valid to do, but it seems to give me correct solutions. One note: adding the two gives 3n + 7m = 0 (mod 10). But solving using that equation as you proposed gave me the solutions n = m = 4 and n = m = 9, I'm not sure if you solved it and could tell me if that's all the solutions? Thank you everyone for your help!

Of course it's valid. If 2n + 3m ≣ 3 (mod 10) and n + 3m ≣ -2 (mod 10), then 3n + 7m ≣ 0 (mod 10).

Take 3n + 7m ≣ 0 (mod 10). Either multiply it by 3 giving 9n + 21m ≣ 0 (mod 10) which is equivalent to -1n + 1m ≣ 0 (mod 10). That can be added to (or subtracted from) n + m ≡ -2 (mod 10)

Otherwise, multiply n + m ≡ -2 (mod 10) by -3 and add that to 3n + 7m ≣ 0 (mod 10) .

Yes, I get m, n = 4, or m, n = 9 .

 

[sapta]

You can also divide

2n + 6m \equiv 2( mod\ 10)

by 2 on both sides to get

n + 3m \equiv 1( mod\ 5)

n + m \equiv -2 (mod\ 10)
\implies n + m \equiv 8 (mod\ 10)
\implies n + m \equiv 3 (mod\ 5)

Now solving the mod 5 congruences, gives

m \equiv 4 (mod\ 5)
which means 2 solutions mod 10, 4 and 9.
similarly for n.