Results 1 to 4 of 4

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

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    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!!!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2008
    From
    Guernsey
    Posts
    69
    f(3750) = \phi(3750) = 1000

    However, a^{\phi ( n)} = 1 \pmod{n} (if gcd(n,a) = 1)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2010
    Posts
    1
    Can someone expand on this?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Bacterius's Avatar
    Joined
    Nov 2009
    From
    Wellington
    Posts
    927
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruences, Powers, and Euler's Theorem
    Posted in the Number Theory Forum
    Replies: 11
    Last Post: January 22nd 2010, 02:14 AM
  2. powers and congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 23rd 2009, 05:14 PM
  3. Euler Formula..
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 19th 2009, 12:29 PM
  4. Euler's Formula
    Posted in the Calculus Forum
    Replies: 2
    Last Post: September 7th 2008, 06:20 AM
  5. Euler's formula
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: April 13th 2008, 05:43 PM

Search Tags


/mathhelpforum @mathhelpforum