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.

For example 151x - 294 is congruent to 44 (mod 7). How would I go about solving that?

The answer says to simplify it into the ax = b (mod c) form first, but I have no clue on how to get rid of the 294... help?

share|improve this question
1  
possible duplicate of How to find solutions of linear Diophantine ax + by = c ? –  Arturo Magidin Apr 2 '11 at 4:54
    
Note that solving $ax\equiv b\pmod{d}$ is equivalent to solving $ax+dy = b$ with $x$ and $y$ integers. –  Arturo Magidin Apr 2 '11 at 4:54
2  
The first thing you should do is simplify all the coefficients modulo $7$; $151\equiv 4\pmod{7}$, $294\equiv 0 \pmod{7}$, and $44\equiv 2\pmod{7}$. So your problem is exactly the same as $4x\equiv 2\pmod{7}$. But if you had not been lucky enough to get that constant term to mod out to $0$, to go from $ax-c\equiv b\pmod{d}$, just add $c$ to both sides of the congruence! –  Arturo Magidin Apr 2 '11 at 5:01
1  
@meiryo: There's certain rules (you cannot cancel factors unless they are relatively prime to the modulus; you can only add/multiple congruences modulo the same modulus), but yes. Didn't you see the basic properties before you tried to solve a congruence? –  Arturo Magidin Apr 2 '11 at 5:03
1  
@meiryo: I would say they are pretty darn lousy if you have to solve a congruence and you don't know that you can add and subtract the same thing from both sides of the congruence. –  Arturo Magidin Apr 2 '11 at 5:11
show 4 more comments

2 Answers

up vote 1 down vote accepted

"a congruent to b mod m" is also written $a \equiv b \pmod m$ and I define it to mean that $a + (m) = b + (m)$ where $(m) = \{ k m \in \mathbb Z | k \in \mathbb Z \}$ is the set of all multiples of $m$ also called the ideal generated by $m$.

What this means, for example, is that $9 \equiv 23 \pmod 7$ since $9 + (7) = \{\cdots,-12,-5,2,9,16,23,30,\cdots\} = 23 + (7).$ In general if number $x = mk+r$ then $x \equiv r \pmod m.$

A general result about relations is that if $R$ is an equivalence relation on $X$ and $f : Y \mapsto X$ is a function then the relation defined by $aSb :\iff f(a) R f(b)$ is also an equivalence relation (on $Y$). This proves that equivalence mod m is an equivalence relation since the relation $R$ is $=$ (which we know to be an equivalence) and the function $f$ is just $+ (m)$.

Since we have an equivalence relation we can do equational reasoning with it. For example:

If $$151x - 294 \equiv 44 \pmod 7$$ then since $$44 \equiv 2 \pmod 7$$ we have $$151x - 294 \equiv 2 \pmod 7,$$ furthermore $$151 \equiv 4 \pmod 7$$ and $$294 \equiv 0 \pmod 7$$ so we have $$4x \equiv 2 \pmod 7.$$ Cancelling out $2$ from both sides gives $$2 x \equiv 1 \pmod 7.$$ To solve this we can just try $x = 1$, $x = 2$, ... until we find a solution.

share|improve this answer
    
Thanks! This goes to prove from what Arturo taught me I've solved this correctly :D –  meiryo Apr 2 '11 at 6:22
add comment

to solve $151x - 294 \equiv 44 \pmod{7}$, first add 294 on both sides to obtain $151x \equiv 338 \pmod{7}$. now before solving for x, let's first check if an integer solution exists. $(151,7) = 1$, and $1|338$, so x is solvable. so now we are solving for x in $151x + 7m = 338$

now use extended eculid algorithm to solve for x. precisely, set up 2 columns and and try to get the column under "e" to become 338 by row addition, subtraction and multiplication. the third column "m" is not necessary, but I listed it anyway for clarity.

e | x(coeff. of 151) | m(coeff. of 7)

151 | 1 | 0

7 | 0 | 1

147 | 0 (2nd row* 21, and we ignore the m column from now on)

4 | 1 (row1 - row3)

3 | -1 (row2-row4)

1 | 2 (from previous two rows)

338 | 676

so x = 676, but x can be any element in $[676]_{7}$

hope this helps, and sorry about the format. \tabular doesn't seem to work here and I don't know what else to do...

share|improve this answer
    
I got x = 4 using something similar to quanta's method, what's [676]sub7? –  meiryo Apr 2 '11 at 6:20
1  
4 works too, since $[676]_{7} = [4]_{7}$. $[676]_{7}$ is a congruence class. in this case, it's the set of all integers of the form $676 + 7m$ for any integer $m$. now you can see $[676]_{7} = [4]_{7}$ because 676 + 7(-96) = 4. so x can be $4+7m$ for any integer m. –  mathcat Apr 2 '11 at 6:40
add comment

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.