# Congruences, Powers, and Euler's Formula

• Feb 2nd 2009, 09:37 PM
ycsanchez
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!!!
• Feb 3rd 2009, 02:20 AM
SimonM
$f(3750) = \phi(3750) = 1000$

However, $a^{\phi ( n)} = 1 \pmod{n}$ (if gcd(n,a) = 1)
• Feb 23rd 2010, 03:10 PM
roflzx
Can someone expand on this?

Thanks.
• Feb 23rd 2010, 07:26 PM
Bacterius
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.