$(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?
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ If there are two questions, ask them separately. And, do not use images in your questions, see this. $\endgroup$– Inuyasha YagamiJul 24, 2021 at 18:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Use Extended gcd algorithm. The time complexity is $O(\log n)$.
answered Jul 24, 2021 at 16:55
$\begingroup$
$\endgroup$
2
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.
Its important to note that "guessing" a solution and verifying it, is a totally fine thing to do, and it is totally "mathematical".
answered Jul 24, 2021 at 16:25
-
-
$\begingroup$ Yea my bad. I was confused with some other computational problem $\endgroup$ Jul 24, 2021 at 17:19