0
$\begingroup$

Determine $\Phi(840)$. Hence, determine the remainder when $2^{1930}$ is divided by $840$.

I determined $\Phi(840) = \Phi(2^3*3*5*7) = 480$, however I don't know how I can use this to solve the problem.

Since $\operatorname{gcd}(2, 840)$ is not $1$, how can I apply Euler's theorem which states if $n \geq 1$ and $\operatorname{gcd}(a, n) = 1$ then $a^{\Phi(n)}$ is congruent to $1 (\operatorname{mod} n)$?

Or is there a different approach to solving a problem like this?

2 Answers 2