Show $52$ has an inverse in the multiplicative group modulo $109$

Question

I saw a problem online asking to show that $52$ has an inverse in the multiplicative group modulo $109$. I don't really know how to do this without using brute force.

The solution is "apply the Euclidean algorithm to find $c=65$." But I don't see what they're talking about. I used the Euclidean algorithm to show that $21\times 109-44\times 52=1$, but how does that help get the $65$?

Answer 1

You got $21\times\color{green}{109}\color{blue}{-44}\times52=1$.

Mod $\color{green}{109}$, this is $\color{blue}{-44}\times52\equiv 1$.

That is $\color{blue}{65}\times52\equiv1$, since $\color{blue}{-44}\equiv-\color{blue}{44}+\color{green}{109}=\color{blue}{65}\bmod \color{green}{109}$.

Answer 2

I used the Euclidean algorithm to show that 21∗109−44∗52=1, but how does that help get the 65?

You want $52x \equiv 1 \pmod{109}$.

That means there is an integer $k$ so that $52x = 1 + 109k$

That means $109(-k) + 52x = 1$.

Use Euclid algorithm to find that.

You got $21*109 -44*52 =1$. So if we let $x = -44$ and $k=-21$ we done:

$-44*52 = 1- 21*109$

So $-44*52 \equiv 1\pmod{109}$ and

$x \equiv -44$ is an multiplicative inverse of $52$.

To express $x$ and an equivalence class where $0\le x < 109$ we

just note that $x \equiv -44 \equiv -44 + 109 \equiv 65\pmod{109}$.

But we may express $x$ as any equivalence representation of $65$. We may have $x\equiv -44$ or $x \equiv 174$ or $x\equiv -153$ or ... whatever.

.....

Or if it helps:

$21*109 - 44*52 = 1$

$21*109 -44*52 + 109*52-109*52 = 1$

$(21-52)*109 + (-44 + 109)*52 =1$

$-31*109 + 65*52 = 1$.

So $1 = 65*52 - 31*109$

So $1 \equiv 65*52\pmod {109}$