Results 1 to 2 of 2

Math Help - congruence

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    12

    congruence

    I am trying to find the smallest positive a such that a^20 == 3 mod 101. I am kind of leaning toward there being no solutions but I don't know how to prove that. I think Fermat's Little Theorem is useful here? Any hints would be appreciated. Thanks.
    Last edited by mr fantastic; October 26th 2009 at 05:31 AM. Reason: Restored deleted question.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Since 101 is prime, Fermat's theorem applies and we must have a^{100}\equiv 1 \mod 101 for all a relatively prime to 101, and 0 in all other cases. Now suppose we have an a with a^{20} \equiv 3 \mod 101. Then

    (a^{20})^5 \equiv 3^5 \mod 101

    a^{100} \equiv 41 \mod 101

    and that is clearly impossible.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruence
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: May 12th 2009, 11:19 AM
  2. Congruence
    Posted in the Geometry Forum
    Replies: 1
    Last Post: November 10th 2008, 02:52 PM
  3. congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 06:04 PM
  4. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 30th 2008, 10:11 AM
  5. Congruence
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 29th 2008, 11:57 AM

Search Tags


/mathhelpforum @mathhelpforum