0
$\begingroup$

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.

4 Answers 4

1

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.

3

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

  • 0
    @Ethan ahh, yes I've seen that in my notes but not with that name assigned to it, Bezout's identity, great.2012-12-16
1

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.

1

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.