1
$\begingroup$

Find an integer $x$ with $0\leq x \leq73$ such that $$2^{75}\equiv x \pmod{74}$$

I think I'm supposed to be using either Fermat's Little Theorem or the Fermat-Euler theorem here but I don't think I can do it directly because $74$ is not prime nor do I have $\operatorname{hcf}(2,74)=1.$

What should I be doing?

$\endgroup$
  • 1
    $\begingroup$ Hint: $2^{36}\equiv 1\pmod{37}$. Now calculating $2^{75}$ modulo $37$ is easy, and then one considers what happens modulo $2$. $\endgroup$ – André Nicolas May 27 '16 at 19:53
4
$\begingroup$

$$2^{75}\equiv x \pmod{74} \Rightarrow \frac{2^{75}}{2} \equiv \frac{x}{2} \left(\text{mod}{\frac{74}{2}}\right) \Rightarrow 2^{2 \cdot 37} \equiv \frac{x}{2} \pmod{37} \\ 4^{37} \equiv \frac{x}{2} \pmod{37}$$

$37$ is prime, so you can apply Fermat Little Theorem. That is:

$$a^{37} \equiv a \pmod{37} \Rightarrow \frac{x}{2} = 4 \Rightarrow x = 8.$$

$\endgroup$
2
$\begingroup$

Hint : $2^{36} \equiv1$ mod $37$ $\implies$ $2^{72} \equiv 1$ mod $37$ $\implies$ $2^{72} = 37k + 1$ for some $k \in \mathbb{N}$.

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