# Application of Fermat's Little Theorem/Fermat Euler Theorem

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?

• 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^{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.$$
Hint : $2^{36} \equiv1$ mod $37$ $\implies$ $2^{72} \equiv 1$ mod $37$ $\implies$ $2^{72} = 37k + 1$ for some $k \in \mathbb{N}$.