# Number Theory and Congruency

I have the following problem: $$2x+7=3 \pmod{17}$$

I know HOW to do this problem. It's as follows:

$$2x=3-7\\ x=-2\equiv 15\pmod{17}$$

But I have no idea WHY I'm doing that. I don't really even understand what the problem is asking, I'm just doing what the book says to do. Can someone explain what this problem is asking and what I'm finding? Thanks

-
I know that x=6.5 isn't a solution, but why? Is it just understood that we don't accept fractional solutions? I read this problem as "I took a number x, multiplied it by 2, added 7, and got a number y. I then divided y by 17, and found the remainder to be 3". How does the restriction on x having to be an integer enter into the problem? –  barrycarter Jan 16 '13 at 18:58

Starting with the simpler question: I took a number, multiplied it by 2, added 7, and got 3. What is the number?

The answer, as you point out, is -2.

How is the actual question different?: I took an INTEGER x (fractions not allowed), multiplied it by 2, added 7 and got a number y. When I divide y by 17, the remainder is 3. What is x?

Does the original answer still work? If we take x=-2, divide it by 17 and take the remainder, we get 15. Now, we multiply by 2 to get 30, and add 7 to get y=37. Is this a valid solution? When we divide y by 17, the remainder is 3. So, yes y=37 is a solution. So the answer is x=-2.

Are there other solutions? Let's try x=35. If we multiply x by 2 and add 7, we get 77. Then, if we divide by 17, and take the remainder, we get 9. So, x=35 is not a solution.

If we try many integers for x, we'll find that x must be one of the following:

...., -36, -19, -2, 15, 32, 49, ....

In other words, any multiple of 17 plus 15 will work for x, and ONLY those numbers will work. Of course, fractions like 13/2 (ie 6.5) will also work, but we don't include those in modulo problems.

So the "solution set" (not just a single solution) is:

{x = 15 + 17n, any integer n}

Another way of saying the above is: "x=15 (mod 17)" [with 3 lines in the equal sign, standing for "congruence"].

Of course, you don't have to use trial and error to find x. As you noted, you actually only need to solve for one value of x, and the others will differ by multiples of 17.

-

You are essentially finding the value of the congruence class of $17$ to which $x$ belongs. The congruence classes for $\mod{17}$ are all integers $k$ such that $0 \le k \lt 17$: $k\in \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16\}$.

You have found that $x$ belongs to the equivalence class of $k = 15 = [15]_{\mod 17}$. This equivalence class has an infinite number of integers: $[15]_{\mod 17} = \{..., -19, -2, 15, 32, 49, ...\}:\;$ $x$ can be any number that when divided by 17 leaves gives a integer quotient and a remainder of $15$, but we typically use its equivalence class representative as the solution to identify the class it belongs to.

The congruence classes of, say 17 are defined so that for each class represented by $k$, the class consists all integers $n, \;n = 17m + k$, where $m$ is the quotient when divided by $17$, and $k$ is the remainder left over when divided by $17$.

You're looking for the remainder $k$ when $x$ is divided by $17$. $x$ can actually be any number that has a remainder of $15$ when divided by $17$.

In your problem you are solving to find the value $x = k$ for which it is true that $$2x + 7 \equiv 3 \pmod {17} \implies x\equiv 15 \pmod {17}$$ $$\implies (x - 15) \equiv 0 \pmod {17} \implies x = k = 15$$ so that $x = k = 15 \implies x - k$ has no remainder when divided by 17.

-

You are just solving a linear equation in one variable, except that you are doing it modulo $17$, that is, in the field $\mathbf{Z} / 17 \mathbf{Z}$.

-
And maybe it is worth noting 17 is prime? –  Pedro Tamaroff Jan 16 '13 at 20:06

The $\bmod{17}$ congruence classes are represented by $0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16$. You're trying to find out which of those classes $x$ belongs to. That's why you're doing that.

-
So if x=-2...what exactly does that tell me? –  Charlie Yabben Jan 16 '13 at 17:17
It tells you which of the $17$ congruence classes $x$ belongs to. –  Michael Hardy Jan 16 '13 at 18:56

The first two lines are solving a linear equation as you are used to. I suspect the problem is the conversion $-2 \equiv 15 \pmod {17}$ In modular arithmetic we regard numbers that differ by the modulus as equivalent. If you plug you solution in, you get $2\cdot 15 +7=37$ Now we subtract off all the multiples of $17$ we can and get $2 \cdot 15+7=37 \equiv 3 \pmod {17}$

-

Your original question is entirely equivalent (for $x,y\in \mathbb Z$) to: $$2x+7=3+17y$$ with the perspective that you want to know the value of $x$ and are not particularly interested in the value of $y$. Note that if you have found a solution $(x,y)$ and you set $x'=x+17k$ then:$$2x'+7=2x+34+7=3+17y+34=3+17(y+2)=3+17y'$$

where $y'=y+2$. So you can always find a solution with $0 \leq x \leq 16$.

Now we start on your solution, noting that $y$ must be even, so that we can put $y=2z$:$$2x+7=3+34z$$$$2x=-4+34z$$$$x=-2+17z$$

And we choose $z$ to give us the least nonnegative value of $x$, though this equation gives us the whole family of solutions.

Basically the notation of modular arithmetic enables the distinct roles of $x$ and $y$ to be formalised in such a way that these calculations can be done more efficiently and presented more economically, without attention to detail which turns out to be irrelevant.

-