9
$\begingroup$

I have problem solving this modular equation $67^n \equiv 67 \pmod {317026939759222841944}$ with $n>1$. I have tried my Laptop and Wolfram Alpha engine, but I don't get any solution, I'm very confused about this, can anyone out there help me ?

$\endgroup$
  • $\begingroup$ I usually can solve this kind of equation easily(only using ordinary scientific calculator), but this one is quite confusing.. $\endgroup$ – Anton GT Apr 1 '17 at 13:08
  • $\begingroup$ Can anyone give the value of n ?. $\endgroup$ – Anton GT Apr 1 '17 at 13:17
9
$\begingroup$

You are looking for the multiplicative order, MultiplicativeOrder[k, m]. The multiplicative order is the smallest exponent $k$ such that $x^k \equiv 1 \pmod m$.

Note that the modulus $m=317026939759222841944$ is divisible by prime $67$. Your equation then becomes $67^{n-1}\equiv 1 \pmod {4731745369540639432}$.

MultiplicativeOrder[67, 4731745369540639432]

11673080393745762

Check this solution with

PowerMod[67, 11673080393745762, 4731745369540639432]

1

and

PowerMod[67, 11673080393745762 + 1, 317026939759222841944]

67

Hence, the final answer is $n=11673080393745763$.

$\endgroup$

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.