I wonder about an equation given as a solution to the following task:
Calculate the multiplicative inverse $$5^{−1} \pmod {13}$$
The solution ends in this equation: $$ 5^{11} \equiv 5^{10} \cdot 5 \equiv −1\cdot 5 \equiv 8 \pmod {13} $$ and the check:
$$ 5 \cdot 8 \equiv 40 \equiv 1 \pmod{13} $$
1) What is the inverse here now?
2) Why is $5^{10} \equiv -1 \pmod {13}$?
As far as I understood Fermat the rule is given as: $$ x^{(p−1)} \equiv 1 \pmod p $$ which won't come into account here, since in this case $p = 13$ and not ideal for calculating $5^{11}$.
If I would use $x^{p−1}$ it would be $5^{12}$ in this case, so I'd still need to divide by $5^1$ to get to the result of $5^{11}$.
I am so confused although it should be really easy.
Question 2: Why is $5^{10}\equiv - \pmod {13}$.
Well....Because it is.
$5^2 \equiv 25\equiv -1\pmod {13}$ so $5^{10}\equiv (-1)^5\equiv -1 \pmod {13}$.
The real question is why are we trying to find $5^{10}$?
$5^{11}*5 \equiv 5^{12} \equiv 1 \pmod {13}$ so $5^{-1}\equiv 5^{11}$ and..... well, I guess the author just figured $5^{10}$ could be easily calculated by subsequent squaring. $5^{11} \equiv 5*5^{10}\equiv 5*(5^2)^5$ is an easy way do to it.
We could, just to be different figure $5^{11} = (5^3)^3*5^2\equiv 125^3*(-1)\equiv -8^3\equiv (-8)^3 \equiv 5^3 \equiv 125 \equiv 8\pmod {13}$ but that would be unnecessarily complicated.
Or we could just do increasing powers and see when we return to $1$. $5^1 \equiv 5$ and $5^2 \equiv -1$ so $5^3\equiv -1*5 \equiv 8$ and $5^4\equiv 1$. So $5^{4} =1$ and $5^{-1} \equiv 5^3 \equiv 8$
To be honest.... I do not know why the author assumed that it'd be "obvious" that $5^{10} \equiv -1$ but not that it'd be "obvious" that $5^{11}\equiv 8$.
But one way or another..... $5^{11}*5 \equiv 1\pmod {13}$ so $5^{-1}$ is $5^{11}$ whatever that is. And roll up your sleeves and do it... $5^{11}\equiv 8\pmod {13}$ by one method or another.
Question 1:
What is the inverse? Well, since $5*8\equiv 1$ it is $8$