Solve $5x+11y=4\pmod{13}$

Question

Now, I know if $ax+by=c$ and $\gcd(a,b)=1$, then first try $au+bv=1$ and hence from $ax+by=acu+bcv$ we get $\frac{x-cu}{-b}=\frac{y-cv}{a}$ and as both are integers, the solutions are, $$x=-bn+cu,\, y=an+cv.$$ Now, in this equation, I need to use $\bmod 13$, which I don't know how to? Please help me, thanks in advance.

Answer 1

Hint:

You have the equation of a line in the (finite) plane $\mathbf F_{13}^2$, so I think all you have to obtain is the list of the thirteen points on this line.

To this end, you have to express $y$ in function of $x$ or the converse: $$y=11^{-1}(4-5x)\quad\text{ or }\quad x=5^{-1}(4-11y),$$ and therefore to determine the inverse of $11$ or of $5\bmod 13$ using Bézout's relation.

Answer 2

Your equations for x any y must give following solutions:

$$5x+11y≡4 \ mod (13)=13 n+4$$

$n=1, 2, 3, 4, ....$

$13n+4=17, 30, 43, 56, 49, 62, 75, 88, 101, 114, 147, 160, 173, . . .$

which gives(from 43):

$(x, y)=(2, 3), (9, 1),(1, 4), (8, 2), (4, 5), (11, 3), (7, 6), (3, 9), (14, 7), (10, 10), (17, 8)$

Therefore solutions are:

$x ≡2 \ mod (13)$, $y ≡3 \ mod (13)$

Such that:

$5x+11y≡43 \ mod (13) ≡ 4 \ mod (13)$

$x ≡ 9 \mod (13)$, $y ≡ 1 \mod (13)$

$x ≡14 \mod(13)≡ 1 \mod(13)$, $y≡7 \mod(13)$

$x≡17 \mod(13)≡4 \mod (13)$, $y ≡ 8 \mod (13)$

And so on.