# How to solve modulo math equation in RSA algorithm?

$$(3 \cdot d) \mod 8=1$$. I know the answer is $$d=3$$ by common sense. But what is the mathematical approach to solve this problem? How do I solve this mathematically?

How do we get this value of 125^107 mod 187=5?

• If there are two questions, ask them separately. And, do not use images in your questions, see this. Jul 24 at 18:52

Use Extended gcd algorithm. The time complexity is $$O(\log n)$$.
We know that $$gcd(3,8)=1$$ since $$3$$ is a prime, and therefore $$3$$ has one and unique inverse under multiplication modulo $$8$$.
As you have seen, its not hard to guess that $$3$$ is its own inverse, that is, $$x=3$$ is the solution for the equation: $$3x\equiv1 \mod 8$$
Since there is only one and unique solution, we know that $$3$$ is the only solution.