2

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?

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

2 Answers2

4

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

the_candyman
  • 14,064
  • 4
  • 35
  • 62
2

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

quid
  • 42,135
Hmm.
  • 3,052