Show $52$ has an inverse in the multiplicative group modulo $109$ 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$?
 A: 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}$.
A: 
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}$
