The number 3750 satisfies $\Phi(3750) = 1000$. Find a number $a$ that has the following three properties
$a \equiv 7^{3003}\bmod{3750}$
$1 \leq a \leq 5000 $
$a$ is not divisible by 7
Any help on how to go about this problem, thank you
This is related to Euler's theorem I think
Use Euler's theorem to figure out $a \pmod {3750}$
If $a \in [1,1250]$ you can add $3750$ to it and stay in range As $7$ does not divide into $3750$ evenly, at least one of the two will not be a multiple of $7$