Finding all numbers smaller than $2040$ so that $51 | 71n-24$

Question

This is a Number Theory problem about the extended Euclidean Algorithm I found:

Use the extended Euclidean Algorithm to find all numbers smaller than $2040$ so that $51 | 71n-24$.

As the eEA always involves two variables so that $ax+by=gcd(a,b)$, I am not entirely sure how it is applicable in any way to this problem. Can someone point me to a general solution to this kind of problem by using the extended Euclidean Algorithm? Also, is there maybe any other more efficient way to solve this than using the eEA?

(Warning: I'm afraid I'm fundamentally not getting something about the eEA, because that section of the worksheet features a number of similiar one variable problems, which I am not able to solve at all.)

I was thinking about using $71n-24=51x$, rearranging that into $$71n-51x=24.$$ It now looks more like the eEA with $an+bx=gcd(a,b)$, but $24$ isn‘t the $gcd$ of $71$ and $51$...

Answer 1

You are looking for numbers such that $71n\equiv24\bmod51$.

The extended Euclidean algorithm gives the Bezout relation $23\times71-32\times51=1$,

so $23\times71\equiv1\bmod51$. Therefore, you are looking for $n\equiv23\times24\bmod51$.

---

Alternatively, you could say $20n\equiv24\bmod51$, so $5n\equiv6\bmod 51$,

and $5\times10=50\equiv-1\bmod51$, so $n\equiv6(-10)=-60\bmod51$.

Answer 2

This is asking you to find solutions to $71n-24\equiv 0 \bmod 51$, which equivalently is $20n\equiv 24\bmod 51$.

To do this you can proceed by finding the modular multiplicative inverse of $20 \bmod 51$ using the extended Euclidean algorithm , as you say.

So:
$\begin {array}{rrc} a&b&51a+20b\\ \hline 1 & 0 & 51\\ 0 & 1 & 20\\ 1 & -2 & 11\\ -1 & 3 & 9\\ 2 & -5 & 2\\ -9 & 23 & 1 \\ \end{array}$

So the last line says: $-9\cdot 51 + 23\cdot 20 = 1$ (check this if nervous), so $23\cdot 20 \equiv 1\bmod 51$ and $23$ is the inverse of $20\bmod 51$.

So then $23\cdot 20n\equiv 23\cdot 24\bmod 51$ giving $n\equiv 42\bmod 51$ and we have solutions $n\in\{42,93,144,\ldots\}$ up to the upper limit given.

Answer 3

Other way

$$71n\equiv 24\pmod {51}\iff$$ $$20n\equiv 24\pmod {51}\iff$$ $$5n\equiv 6\pmod {51}\iff$$ $$5n\equiv -45\pmod {51}\iff$$ $$n\equiv -9 \pmod {51}$$