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.
Best Answer
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.