# Math Help - Congruences, Powers, and Euler's Formula

1. ## Congruences, Powers, and Euler's Formula

Hello I can't quite seem how to finish this problem:

The number 3750 satisfies f(3750) = 1000. Find a number a that has the following three properties:

(i) a º 7^3003 (mod 3750).
(ii) 1 < a < 5000.
(iii) a is not divisible by 7.

THANKS!!!

2. $f(3750) = \phi(3750) = 1000$

However, $a^{\phi ( n)} = 1 \pmod{n}$ (if gcd(n,a) = 1)

3. Can someone expand on this?

Thanks.

4. Note that $7^{3003} \equiv 343 \equiv 7^3 \pmod{3750}$ (it can be shown quite trivially using Euler's Generalization, with $\varphi{(3750)} = 1000$).

Such a number does not exist, since if $a \equiv 7^{3003} \equiv 7^3 \pmod{3750}$, then $7 | a$, and we have a contradiction.