If I'm calculating $a^{-1} \equiv 1 \pmod n$ where $a$ is negative. Do I simply add $kn$ to $a'$ until $0\lt a' \lt n$?
I'm currently using the extended euclidean algorithm to calculate my modular multiplicative inverses since I already have to make sure that $a$ and $n$ are coprime. From what little number theory I understand $a'=a+kn$ is going to give me the same result as $a \pmod n$. So that should mean that $a' \equiv 1 \pmod n$ is the same as $a \equiv 1 \pmod n$
I've confirmed this with a few values below but don't know if I'm understanding this properly.
$a=-36 \;\; a'=14$
$9 = -36^{-1} \pmod{25}$
$9 = 14^{-1} \pmod {25}$
$a=-11\;\; a'=15$
$7 = -11^{-1} \pmod{26}$
$7 = 15^{-1} \pmod{26}$
Here's a link to my python code.
https://paste.debian.net/1117624/
Best Answer
Hint: $ $ like sums & products, inverses too are preserved on replacing argument(s) by a congruent one
Congruence Inverse Law $\ \color{#c00}{\bar a\equiv a}\,\Rightarrow\,{\bar a}^{-1}\equiv a^{-1}\,$ if $\ a\,$ is invertible, i.e. $\, ab\equiv 1\,$ for some $b$.
Proof $\ $ Notice $\,\ \color{c00}ab\equiv 1\ \Rightarrow\ \color{#c00}{\bar a} b\equiv \color{#c00}ab\equiv 1\,$ by applying the Congruence Product Rule. Therefore we conclude that $\, {\bar a}^{-1}\!\equiv b\equiv a^{-1}\,$ by Uniqueness of Inverses.