$\bmod p\!:\ b\not\equiv 0\,\Rightarrow\, b^{-1}\equiv b^{p-2}$ for $\,p\,$ prime

73 Views Asked by At

I have found something like this:

$(((a^{x}-1)mod\ p)* ( a-1) ^ {p-2})mod\ p = \frac{a^{x}-1}{a-1} mod \ p $

After taking some examples and considering the place I took this from this should be true.

If my reasoning is right, from the ecuation above we get that $(a-1)^{p-2}$ is the modular inverse of (a-1).

1.Am I correct?
2.What is the origin of such an "ecuation" as the one above?

P.S. The formula is a part of the Divisors sum formula.

Edit due to comment:

What I ment by what is the origin, is how do you get from the fraction in the right side, to the ecuation in the left side. I want a detaliated explication since I'm new to modular arithmetics.

2

There are 2 best solutions below

0
On BEST ANSWER

By little Fermat, $\,\rm mod\ p\!:\ b\not\equiv 0\,\Rightarrow 1 \equiv b^{p-1}\equiv b\cdot b^{p-2}\Rightarrow\ b^{-1}\equiv b^{p-2}$

Yours is the special case $\rm\, b = a\!-\!1,\,\ a\not\equiv 1$.

We implicitly used the uniqueness of inverses. Proof: $ $ if $\,\rm c',c$ are both inverses of $\,\rm b\,$ then

$$\rm c' \equiv c'(bc)\equiv (c'b)c\equiv c $$

This holds very generally since the above proof uses only commutativity and associativity.

0
On

1) If $a-1$ is not divisible by $p$, then you are correct that $(a-1)^{p-2}$ is the inverse, modulo $p$, of $a-1$. This is, in fact, Fermat's Little Theorem: if $b=a-1$, then $p$ divides $b^p-b=b(b^{p-1}-1)$—hence, when $p$ does not divide $b$, it divides $b^{p-1}-1$.

(on the other hand, if $p$ divides $a-1$, then $a-1$ has no inverse.)

2) The origin appears to be you.