Modular algebra with an non-integer solution

Suppose I was asked to solve:

$$5x+6=10 \mod 17$$

I would get this far with normal algebra:

$$x = \frac{4}{5} \mod 17$$

But now I have a non integer expression ($4/5$) where it does not belong.

What am I missing here? I think I have made a fundamental misconception.

-

When you divide by 5, remember that you're in fact multiplying by 5's inverse. Here, however, the inverse of 5 mod 17 is 7. That is because 5*7 = 35 and 35 = 1 mod 17 (similar to the more familiar 5 * 1/5 = 1).

So what you get is x = 4 * (5's inverse) mod 17 = 4 * 7 mod 17. That is x = 28 mod 17 = 11 mod 17. There are methods to determine the inverse when it exists (because sometimes it doesn't) such as Euclide's algorithm to find the GCD.

-

$$5x+6 \equiv 10 \pmod{17}$$ means $5x+6 = 17k+10$, where $k \in \mathbb{Z}$. Hence, we have $5x = 17k+4$, where $x,k \in \mathbb{Z}$. Note that $x$ and $k$ are not arbitrary real numbers but integers. This enforces a constraint on the values taken by $x$ and $k$. Further $$5x = 17k+4 = 17(k-3) + 17 \times 3 + 4 = 17(k-3) + 55$$ Hence, we get that $$x = \dfrac{17(k-3)}5 + 11$$ Since $x \in \mathbb{Z}$, we have that $\dfrac{17(k-3)}5 \in \mathbb{Z}$. Hence, $5 \vert 17(k-3)$. But since $\gcd(5,17) = 1$, we have that $5 \vert k-3$. (Recall that if $a \vert (bc)$ and $\gcd(a,b) = 1$, then $a \vert c$).

Hence, $k = 5m + 3$. This gives us that $$x = 17m + 11 \,\,\,\,\, \text{i.e.} \,\,\,\, x \equiv 11 \pmod{17}$$

-
Better answer then mine, for the general case tridecth12 look up Bezout's identity. –  Ethan Dec 16 '12 at 4:23
Thanks for the answer.. I just need a sec to get my head around it as I am new to modular arithmetic. What is the significance of the vertical bar in $a \vert b$ –  trideceth12 Dec 16 '12 at 4:23
@trideceth12 $a \vert b$ means $a$ divides $b$ i.e. $b$ is a multiple of $a$ i.e. $b = am$ where $m \in \mathbb{Z}$. –  user17762 Dec 16 '12 at 4:24
@Ethan ahh, yes I've seen that in my notes but not with that name assigned to it, Bezout's identity, great. –  trideceth12 Dec 16 '12 at 4:25

You shouldn't have divided both sides by 5, to create that quotient, I think thats an abuse of notation, anyway what you end up with is $5x\equiv 4$ mod 17, which can be re-written as a linear diophantine equation, and solved useing the generalized euclidean algorithm.

The diophantine equation would look like:

$5x-17y=4$, but you really only need a solution in x, ie you don't care about the value/values of y that makes that solution true.

-

The deterministic way to find $x,y$ for $Ax+By=1$ where $A,B$ are known and$(A,B)=1$ is to utilize the property of the successive convergents of a continued fraction.

$$\frac{17}5=3+\frac25=3+\frac1{\frac52}=3+\frac1{2+\frac12}$$

So, the previous convergent of $\frac{17}5$ is $3+\frac12=\frac72$ $\implies 17\cdot2-5\cdot7=-1$

We have $5x+6=10+17y$ for some integers $x,y$

or ,$5x-17y=4=4(5\cdot7-17\cdot2)$

or, $5(x-28)=17(y-8)$

or, $\frac{5(x-28)}{17}=y-8$ which is an integer.

$\implies 17\mid5(x-28)\implies17\mid(x-28)$ as $(5,17)=1$

$\implies x=17z+28$ where $z$ is any integer.

or, $x=17(z+1)+11=17w+1$ where $w=z+1$ is also some integer.

Alternatively, $$\frac{17}5=3+\frac25=3+\frac1{\frac52}=3+\frac1{2+\frac12}=3+\frac1{2+\frac1{1+\frac11}}$$

So, the next convergent of $\frac{17}5$ is $3+\frac1{2+1}=\frac{10}3$ $\implies 17\cdot 3-5\cdot10=1$

$5x-17y=4=4(17\cdot3-5\cdot10)$

or, $5(x+40)=17(y+12)$

or, $\frac{5(x+40)}{17}=y+12$ which is an integer.

So, $17\mid5(x+40)\implies 17\mid(x+40)$ as $(5,17)=1$

$\implies x+40=17u$ where $u$ is any integer.

or, $x=17u-40=17(u-2)-6=17v-6$ or $x=17(u-3)+11=17t+11$ where $v=u-2,t=u-3$ are integers.

-