How to find all solutions of ## 3x-7y\equiv 11\pmod {13} ##?

[Math100]

Homework Statement

Find all solutions of the linear congruence $3x-7y\equiv 11\pmod {13}$.

Relevant Equations

None.

Consider the linear congruence $3x-7y\equiv 11\pmod {13}$.
Then $3x\equiv 11+7y\pmod {13}$.
Note that $gcd(3, 13)=1$ and $1\mid 11$.
This means $y\in\ {0, 1,..., 12}$.

And now I'm stuck. The book's answer shows $x\equiv 11+t\pmod {13}, y\equiv 5+6t\pmod {13}$. But based on my previous work shown above, how should I get to the correct answer for this problem?

 

[topsquark]

I'm not sure why they would write the answer in that manner. I'd start with (you can fill in some blanks)
$3x - 7y \equiv 11$

$3x \equiv 11 + 7y$

Multiply both sides by $3^{-1}$ to get x. Then you have
$x \equiv 8 + 11y$

Personally I'd leave it there, but if you like set $x \equiv t$. Then solve $t \equiv 8 + 11y$ for y and you get $y \equiv 6 t+ 2$.

I'll leave it to you to figure out how to get $x = 11 + t$ and $y \equiv 5 + 6t$ from there.

If you need more help, show us what you've got and we'll take it from there.

-Dan

 

[fresh_42]

Let's forget about the theorems for a moment.

We have $3x-7y\equiv 11\pmod{13}$ and all numbers here are coprime, so they all have inverses modulo $13.$ However, we have two variables but only one equation. It is now the same calculation which you use to solve linear equation systems. Only that we do not have rational numbers, but $\{0,1,2,\ldots,12\}$ instead.

Let's solve $3a\equiv 1\pmod{13}.$ We have $3\cdot (-4)\equiv -12 \equiv 1 \pmod{13}$ so $a=3^{-1}\equiv -4\equiv 9\pmod{13}.$ From that we get
\begin{align*}
3x-7y\equiv 11\pmod{13} &\Longrightarrow 9\cdot 3x-9\cdot 7y=99\pmod{13} \\
&\Longrightarrow 27x-63y\equiv 99\pmod{13}\\
&\Longrightarrow x-11y\equiv 8 \pmod{13} \\&\Longrightarrow x=11y+8
\end{align*}
$y$ is arbitrary, a free parameter. So you could either choose any $y$ and calculate $x$ from it or the other way around.

 

[Math100]

Let's forget about the theorems for a moment.

We have $3x-7y\equiv 11\pmod{13}$ and all numbers here are coprime, so they all have inverses modulo $13.$ However, we have two variables but only one equation. It is now the same calculation which you use to solve linear equation systems. Only that we do not have rational numbers, but $\{0,1,2,\ldots,12\}$ instead.

Let's solve $3a\equiv 1\pmod{13}.$ We have $3\cdot (-4)\equiv -12 \equiv 1 \pmod{13}$ so $a=3^{-1}\equiv -4\equiv 9\pmod{13}.$ From that we get
\begin{align*}
3x-7y\equiv 11\pmod{13} &\Longrightarrow 9\cdot 3x-9\cdot 7y=99\pmod{13} \\
&\Longrightarrow 27x-63y\equiv 99\pmod{13}\\
&\Longrightarrow x-11y\equiv 8 \pmod{13} \\&\Longrightarrow x=11y+8
\end{align*}
$y$ is arbitrary, a free parameter. So you could either choose any $y$ and calculate $x$ from it or the other way around.

Since $y\in {0, 1,..., 12}$, it follows that $x=11(0)+8=0+8=8$. So $x=8, y=0$. Then what should be the answer?

 

[fresh_42]

Since $y\in {0, 1,..., 12}$, it follows that $x=11(0)+8=0+8=8$. So $x=8, y=0$. Then what should be the answer?

The answer is a set that has as many elements as there are solutions. Since $y$ can freely be chosen, there will be thirteen answers, for every value of $y$ one. You have noted $(x,y)=(8,0).$ The solution is either $\{(x,y)=(11y+8,y)\pmod{13}\,|\,0\leq y \leq 12\}$ or you list all thirteen: $\{(8,0),(6,1),(4,2),\ldots\}.$

 

[Math100]

The answer is a set that has as many elements as there are solutions. Since $y$ can freely be chosen, there will be thirteen answers, for every value of $y$ one. You have noted $(x,y)=(8,0).$ The solution is either $\{(x,y)=(11y+8,y)\pmod{13}\,|\,0\leq y \leq 12\}$ or you list all thirteen: $\{(8,0),(6,1),(4,2),\ldots\}.$

I do not think listing all thirteen pairs of sets is a good idea, but I do prefer the first solution you've provided.

 

[fresh_42]

I do not think listing all thirteen pairs of sets is a good idea, but I do prefer the first solution you've provided.

The point that you should get here is, that the remainders of primes, here $13,$ form a field. Fields are structures where we can add, subtract, multiply and divide. We normally only consider the rational numbers, or the reals, maybe even the complex numbers. But $\{0,1,2,\ldots,12\}$ is a field, too. It has only thirteen elements, but it provides all calculation rules. Therefore $3x-7y=11\pmod{13}$ is the equation of a straight in a plane. The plane has only $13^2=169$ points, but who cares? The straight has $13$ points.