# Linear equation using modulo

The question is: If $3X \equiv 2 \pmod 7$, what is $x$?

I used this article to solve, but I can't really get it. It's quite complicated.... I need guidance please

• What do you know about modulo? – Don Larynx Dec 23 '13 at 14:04
• try this: you are attending an intensive summer school for a week on the subject of modular arithmetic. there are twelve classes per day. each day the first class starts at 10.00 a.m. each class lasts exactly 30 minutes, but 5 minutes are allowed for switchover, so each class begins exactly 35 minutes after the previous one. at what time(s) of day will the class start at precisely quarter past an hour? – David Holden Dec 23 '13 at 14:31
• 11.10..........? – ALI Dec 23 '13 at 14:52
• What specifically don't you get about modular arithmetic? It is difficult to give a good answer without any clue as to where you are having difficulties. – Bill Dubuque Dec 23 '13 at 15:21

Hint: Use the Euclidean algorithm to find numbers $m$ and $n$ such that $3m+7n=1$. Then $3m\equiv 1\pmod 7$ (why?). The answer is then $X=2m$ (why?).

• Would the down voter care to help me improve my answer by giving some feedback? – user1729 Dec 23 '13 at 14:25
• Your answer is correct, i.e. $\rm\,mod\ 7\!:\ 3x\equiv 2\iff x\equiv 2\cdot 3^{-1},$ so the downvote is a bit puzzling. Perhaps the voter thought that using the Euclidean algorithm is overkill since e.g. $\,2/3 \equiv 9/3\equiv 3\,$ or $\,1/3 \equiv -6/3 \equiv -2.\$ – Bill Dubuque Dec 23 '13 at 15:33
• @Bill Yes, it is overkill. But when you get the question "what is $5x\equiv 8\pmod{169}$" in your exam you begin to realise that overkill is sometimes much easier than guessing...(also, giving a hint which says "just guess which numbers you multiply $3$ by to get something nice which you can multiply by to get $2\pmod7$" is less precise and is something which I would downvote...) – user1729 Dec 23 '13 at 15:48
• I agree that the algorithm is necessary for large inversions. My comment was primarily meant to assure readers that your answer was correct. I can only guess about the downvote, since I did not cast it (I rarely downvote these days, maybe a couple times a month, primarily when a user refuses to correct an error). – Bill Dubuque Dec 23 '13 at 16:02
• @Bill I figured that, but I thought I would also explain why the readers should care about overkill! – user1729 Dec 23 '13 at 16:03

Here is a grubby but easy to understand way. Consider this table.

x: 0  1  2  3  4  5  6
2x:0  2  4  6  1  3  5
3x:0  3  6  9  5  1  4


We see that 3*5 = 1 in this form of arithmetic, so 3 has multiplicative inverse 5. You have $3x = 2$ so $5\cdot 3 x = 3$, hence $x = 3$.

Basically mod 7 means you are operating on numbers in the ring $\Bbb{Z}_7$. This is the set $\{0, 1, 2, 3, 4, 5, 6\}$, composed of seven numbers. It's called a ring because you go "around in circles", as shown below.

We are given a number times 3 equals two. Basically, if it results in a number that doesn't appear in the set $\Bbb{Z}_7$, for example $9$, then we have $$9 \mod 7 = 9 + 7i = 2 + 7 + 7i = 2 + 7(1 + i) = 2 + 0 = 2.$$ We then say that $9$ is contained in the congruence class of $_7$.

Thus, $2$ would equal $9$ in $\Bbb{Z}_7$. The equation then becomes $$3X = 9 \mod 7.$$ Does this help?

• I am slightly uncomfortable with your use of rings here. I really think you should say "if it results in a number outside the set" as it is dubious as to whether $9$ is contained in the ring or not (it depends how you are viewing the ring...). Also, going round in circles? Is this really why rings are called rings?!? (The same holds for groups...) – user1729 Dec 23 '13 at 14:14
• @user1729?!?!??!!?!? math.stackexchange.com/questions/61497/… see here?!??!??!!??! and also, $9$ is contained in the congruence class of $_7$....!??!?!?!?! – Don Larynx Dec 23 '13 at 14:17
• Yes, exactly, $9$ is contained in the congruence class of $2$, and so usually the ring $\mathbb{Z}_7$ would be defined as the quotient of $\mathbb{Z}$ under the ideal $7\mathbb{Z}$. Then the elements are the congruence classes, and just writing $\{0, 1, \ldots, 6\}$ is a convenience. So "$9$" is contained in the ring, it just so happens to equal $"2"$. My point is, that when you start talking about rings you have to start worrying about things like this. However, simply saying that "$9$ is not contained in the set..." sidesteps the issue. Does that make sense? – user1729 Dec 23 '13 at 14:25
• @user1729: I have edited my post. – Don Larynx Dec 23 '13 at 14:52
• Hmm. Still not right. The elements of $\Bbb{Z}_7$ are (in your notation) $_7,_7,_7,\ldots,_7$. Your list only contains representatives. True, we often blur the distinction for ease of calculation. I also share the criticism of user 1729. "Going around in circles" is not the reason why it is called a ring. Look up the definition of a ring in case you are not familiar with it. – Jyrki Lahtonen Dec 30 '13 at 10:04