-2
$\begingroup$

$(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? This figure

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

Use Extended gcd algorithm. The time complexity is $O(\log n)$.

$\endgroup$
0
$\begingroup$

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".

$\endgroup$
2
  • $\begingroup$ Can you solve this? (d*7) mod 60=1 $\endgroup$
    – broman
    Jul 24 at 16:44
  • $\begingroup$ Yea my bad. I was confused with some other computational problem $\endgroup$
    – nir shahar
    Jul 24 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.