Using Fermat's little theorem to find Multiplicative Inverse

Question

I am new to number theory, and I was reading about using fermat's theroem to find the modular multiplicative inverse on Wikipedia here.

They wrote that by Fermat's theorem, if $m$ is prime, $a^{m-1} \equiv 1\text{ (mod } m)$. Then, they wrote $a^{m-2} \equiv a^{-1}\text{ (mod } m)$ to find the modular inverse. It seems as if they muliplied $a^{-1}$ to both sides. I thought $a^{-1}$ is just a notation to represent a number $x$ such that $a \cdot x \equiv 1 \text{ (mod } m)$. How can this be multipied like that if it's just notation? It says $a^{m-2} \text{ (mod } m) $ can hence be calculated by methods like binary exponentiation.

Answer 1

They didn't "multiply" by anything. The equality $a^{m-1}\equiv1$ can be written as $a\cdot a^{m-2}\equiv1$. So, exactly as you said, $a^{m-2} $ is a number that multiplied by $a $ gives $1$.

Answer 2

The following steps give $a^{m-2}\ modulo\ m$ :

Determine the binary expansion of $m-2$

Begin with x=a

for the second till the last digit do

square x

if the current bit is $1$ multiply with $a$

reduce modulo $m$

Result : the desired residue.

Answer 3

Yes, I suppose that they did multiply by $a^{-1}$ on both sides. We are working on the set$$\mathbb{Z}_m^*=\bigl\{n\in\{1,2,\ldots,m-1\}\,|\,\gcd(n,m)=1\bigr\}$$here, which forms a group with respect to multiplication modulo $m$. So, if $\gcd(a,m)=1$, $a\equiv a'\pmod m$ for some $a'\in\mathbb{Z}_m$ and $a'$ has an inverse in $\mathbb{Z}_m^*$.

Answer 4

You're right in a sense that $a^{-1}$ is a kind of notation. Now here's the thing which should clear your doubt.

By Fermat's Little Theorem,

$a^{m-1}\equiv 1\pmod{m}\\$ $\Leftrightarrow a^{m-2}.a\equiv 1\pmod{m}$. Now just multiply both sides by $a^{-1}$ to get:

$\Rightarrow a^{m-2}.a.a^{-1}\equiv a^{-1}\pmod{m}\Leftrightarrow a^{m-2}\equiv a^{-1}\pmod{m}$

NOTE: It is a bit difficult to find the multiplicative inverse using FLT. You should probably try using Bezout's Identity and then Euclidean Algorithm to find the inverse as it's a bit more easier.

Answer 5

Inverses are defined as you said. However, you can see that we can multiply inverses (as long as they are relatively prime to $m$) freely. Just substitute $x=a^{m-2}$ in your definition. You would receive the statement of Fermat's Little Theorem again. You can multiply and divide inverses just like you deal with other values, since you can freely multiply in modulo congruences.

Answer 6

If you multiply $a$ multiplied by itself $m-1$ times by the inverse of $a$, you get.... $a$ multiplied by itself $m-2$ times and then $1$ more time and then by the inverse of $a$,... which is $a$ multiplied by itself $m-2$ times and then multiplied by $a$ times the inverse of $a$... which is $a$ multiplied by itself $m-2$ times and then multiplied by $1$ .... which is $a$ multiplied by itself $m-2$ times.

Yes, it is notation but because of the identity nature of of $1$, the associativity of multiplication, and the meaning of the inverse, those are all legitimate results.

$a^{m-1} \equiv 1 \pmod m$

$a^{m-1}*a^{-1} \equiv a^{-1} \pmod m$

$\underbrace{a*a*a*...*a*a}_{m-1\text{ times}}*a^{-1} \equiv a^{-1} \pmod m$

$\underbrace{a*a*a*...*a}_{m-2\text{ times}}*\underbrace{a}_{1\text {time}}*a^{-1} \equiv a^{-1} \pmod m$

$\underbrace{a*a*a*...*a}_{m-2\text{ times}}*\underbrace{a*a^{-1}} \equiv a^{-1} \pmod m$

$\underbrace{a*a*a*...*a}_{m-2\text{ times}}*\underbrace 1 \equiv a^{-1} \pmod m$

$\underbrace{a*a*a*...*a}_{m-2\text{ times}} \equiv a^{-1} \pmod m$

$a^{m-2} \equiv a^{-1} \pmod m$.

====

Claim 1: $a^k*a^{-1} = a^{k-1}$ for any algebraic structure where $a^{-1}$ exists.

Pf: The same as above.

Claim 2: $(a^m)^{-1} = (a^{-1})^m$ and therefore we can define the natation $a^{-m} := (a^m)^{-1} = (a^{-1})^m$.

Pf: $(a^m)^{-1}$ is the element $k$ where $(a^m)*k = 1$.

And $(a^m)*(a^{-1})^m = \underbrace{a*\underbrace{a*\underbrace{a ...*\underbrace{a*a^{-1}}*... *a^{-1}}*a^{-1}}*a^{-1}}=$

$\underbrace{a*\underbrace{a*\underbrace{a ...*1*... *a^{-1}}*a^{-1}}*a^{-1}}=$

$...$

$\underbrace{a*\underbrace{a*\underbrace{a*a^{-1}}*a^{-1}}*a^{-1}}=$

$\underbrace{a*\underbrace{a*1*a^{-1}}*a^{-1}}=$

$\underbrace{a*\underbrace{a*a^{-1}}*a^{-1}}=$

$\underbrace{a*1*a^{-1}}=$

$\underbrace{a*a^{-1}}=1$

So $(a^m)^{-1} = (a^{-1})^m$.

Claim 3:

$a^ma^{-k} = a^{m-k}$.

Pf: Too similar to the above to bear repeating.