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.

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.

share|improve this question

4 Answers 4

up vote 1 down vote accepted

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.

share|improve this answer

$$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}$$

share|improve this answer
1  
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.

share|improve this answer

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.

share|improve this answer

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.