3
$\begingroup$

In a previous part of the question, I am asked to find $11^{-1} \mod 40$. I've done that, the answer's $11$. The question continues:

find $x$ where $x^{11} \mod 41 = 10$ showing how you could get the final answer with a calculator that can manage a maximum of $9$ digits.

I'm pretty sure I need Fermat's little theorem, but I'm not sure.

$\endgroup$
  • $\begingroup$ Combine Mark's answer with Sonnhard's hint. The latter (suitably interpreted) gives you some information on the order of $10$ modulo $41$, in other words, gives you "small" exponents $m$ such that $10^m\equiv1\pmod{41}$. $\endgroup$ – Jyrki Lahtonen Jan 6 '15 at 20:45
5
$\begingroup$

Hint: Little Fermat tells us that $x^{40}\equiv 1 \mod 41$ for $x$ not divisible by $41$ and this means that $x^{40r+1}\equiv x \mod 41$. Use what you already know to sort out the exponent correctly. Then manage the arithmetic so your calculator can handle it.

$\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.