Find all solutions of the linear congruence $3x-7y \equiv 11$ (mod $13$)

Question

Find all solutions of the linear congruence $3x-7y \equiv 11$ (mod $13$)

This is a problem from Burton's Elementary Number Theory. The answer says $x \equiv 11+ t, y \equiv 5+6t$ (mod 13).

I don't understand how once can come up with this answer.

The way I solved it was solve $3x \equiv 11+7y$ (mod 13) for each $y = 0,1, \dots, 12$.

Then since $gcd(3,13)=1$, we get a unique solution for each $y$, and inductively I got the relation $x_i=x_0-2i, y_i=y_0+i, i=0,1, \dots, 12$, where $x_0=8, y_0=0$.

Is this method incorrect? How can I get the answer as in the book?

I would appreciate any help.

Answer 1

Doing arithmetic modulo $\;13\;$ all along:

$$3x-7y=11\implies 3x=7y+11\;\stackrel{\div\,3}\implies x=11y+8$$

because $\;3^{-1}=9\;,\;\;and\;\;9\cdot7=11\;,\;\;9\cdot11=8\;$

So the set of all solutions is

$$\left\{\;\binom{11y+8}y\;\;:\;\;\;y\in\Bbb F_{13}\right\}=\left\{\;\binom 80+\binom{11t}t\;\;:\;\;t\in\Bbb F_{13}\;\right\}$$

Now just prove the result in the book is just the above one

Answer 2

You got

$$\binom x y = \binom 8 0 + \binom{11i}{i}$$

I don't have that book, so I can't know what methods they were trying to teach you. But it's not hard to derive their answer from yours. Notice that their $y$ is equal to $5 + 6t$. So , if you let $ i = 5 + 6t$, I bet that you will get their answer.

You should be wondering if it is OK to let $i = 5 + 6t$. Substitutions like this are fine as long as you can reverse the substitution. In other words, as long as you can solve for $t$ in terms of $i$. \begin{align*} i &= 5 + 6t \mod{13}\cr 6t &= i - 5 \mod{13}\cr t &= -2i + 10 \mod{13} \end{align*}

So make the substitution and you get

\begin{align*} \binom x y &= \binom 8 0 + \binom{11(5 + 6t)}{5 + 6t}\cr &= \binom 8 0 + \binom{55}{5} + \binom{66t}{6t}\cr &= \binom{63}{5} + \binom{66t}{6t}\cr &= \binom{11}{5} + \binom{t}{6t} \end{align*}

Which is their answer.