Congruences, Powers, and Euler's Formula

**ycsanchez** · February 2nd 2009, 08:37 PM

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!!!

**SimonM** · February 3rd 2009, 01:20 AM

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

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

**roflzx** · February 23rd 2010, 02:10 PM

Can someone expand on this?

Thanks.

**Bacterius** · February 23rd 2010, 06:26 PM

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.

Thread: Congruences, Powers, and Euler's Formula

LinkBack

Thread Tools

Display

Congruences, Powers, and Euler's Formula

Similar Math Help Forum Discussions

Congruences, Powers, and Euler's Theorem

powers and congruences

Euler Formula..

Euler's Formula

Euler's formula

Search Tags