Finding other solutions to diophantine equations

50 Views Asked by At

I understand how to find the first solution to these equations but can't grasp how the other solutions are found.

E.g. $102x\equiv 12 \pmod{174}$

So I can find the $gcd(174,102)=6$ (showing that there are 6 solutions in the range) then work back to get the equation $6=12\times102 - 7\times174$

After this I know to multiple by $2$ as it is congruent to $12$ then rearrange to get $102\times24\equiv12 \pmod{174}$ so $x=24$ is a solution, now how would i find the other solutions in $x\in{0,1,2,....,172,173}$

1

There are 1 best solutions below

2
On BEST ANSWER

We know that $102*24 \equiv 12 \pmod{174}$. Now, we want to find $102x \equiv 0 \pmod{174}$ so we can add it to the first equation.

Thus, we want to find the LCM of $102$ and $174$. This is the same as the product of $102$ and $174$ divided by the GCD of $102$ and $174$, or $\frac{102*174}{6}=2958$. Now, we want to find $102x=2958$. Dividing both sides by $102$ gives us $29$, so $102*29 \equiv 0 \pmod{174}$.

Adding this to our original equation gives us $102*(24+29) \equiv 12 \pmod{174}$, which gives us another solution of $24+29=53$. Thus, we can just keep adding $29$ to each solution we get to get the other solutions: $53+29=82$, $82+29=111$, $111+29=140$, $111+29=169$, $168+29=198 \equiv 24 \pmod{174}$. Now, we've looped back to our original solution of $24$ and found all six solutions.

Thus, $102x \equiv 12 \pmod{174}$ if and only if $x \in \{24, 53, 82, 111, 140, 169\} \pmod{174}$.