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

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

(i)º 7^3003 (mod 3750).a

(ii) 1<a<5000.

(iii)is not divisible by 7.a

THANKS!!!

Printable View

- Feb 2nd 2009, 08:37 PMycsanchezCongruences, 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 numberthat has the following three properties:**a**

(i)º 7^3003 (mod 3750).**a**

(ii) 1__<__**a**__<__5000.

(iii)is not divisible by 7.**a**

THANKS!!!

- Feb 3rd 2009, 01:20 AMSimonM
$\displaystyle f(3750) = \phi(3750) = 1000$

However, $\displaystyle a^{\phi ( n)} = 1 \pmod{n}$ (if gcd(n,a) = 1) - Feb 23rd 2010, 02:10 PMroflzx
Can someone expand on this?

Thanks. - Feb 23rd 2010, 06:26 PMBacterius
Note that $\displaystyle 7^{3003} \equiv 343 \equiv 7^3 \pmod{3750}$ (it can be shown quite trivially using Euler's Generalization, with $\displaystyle \varphi{(3750)} = 1000$).

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