Results 1 to 12 of 12

Math Help - Congruence Fermat's little theorem help

  1. #1
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    Post Congruence Fermat's little theorem help

    Using Fermat's Little Theorem find the value for x.

    x 9^(794) mod 73

    I don't even know where to begin, I need step by step help majorly : )
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Begin with 9^72 = 1 (mod 73)
    Now keep on rasing exponents to get 794
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    feeling dumb

    This is totally stupid I know, but what is the base for using Mods? I've never used them by hand, only TI89 which now I have to show by hand, I'm totally lost..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by duggaboy View Post
    This is totally stupid I know, but what is the base for using Mods? I've never used them by hand, only TI89 which now I have to show by hand, I'm totally lost..
    Basis :

    a=b\mod n means that a-b is a multiple of n.

    In some cases, b represents the remainder of a in the Euclidian division by n.
    a and b can be negative or positive.

    Basic operations :

    a=b \mod n \Longleftrightarrow a+c=b+c \mod n

    Also, a=b \mod n \Longleftrightarrow a=b+kn \mod n, for any k in \mathbb{Z}

    a=b \mod n \implies a^c=b^c \mod n << for this one, always look for congruences to 1, because any power of 1 always yields 1.

    a=b \mod n \implies a*c=b*c \mod n

    Be careful :

    a=b \mod n \not \implies \frac ac=\frac bc \mod n



    There are several properties you should know...

    Fermat's little theorem states :

    \text{If p is a prime number, then } a^{p-1}=1 \mod p (with a, not multiple of p)
    Last edited by Moo; June 2nd 2008 at 02:20 PM. Reason: added some lines...thanks for quoting mathstud ! xD
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Mathstud28's Avatar
    Joined
    Mar 2008
    From
    Pennsylvania
    Posts
    3,641
    Quote Originally Posted by Moo View Post
    Hello,



    Basis :

    a=b\mod n means that a-b is a multiple of n.

    In some cases, b represents the remainder of a in the Euclidian division by n.

    Basic operations :

    a=b \mod n \Longleftrightarrow a+c=b+c \mod n

    a=b \mod n \implies a^c=b^c \mod n << for this one, always look for congruences to 1, because any power of 1 always yields 1.

    Be careful :

    a=b \mod n \not \implies \frac ac=\frac bc \mod n



    There are several properties you should know...

    Fermat's little theorem states :

    \text{If p is a prime number, then } a^{p-1}=1 \mod p
    Just to add to Moo's wonderful response, it also might be helpful to know Wilson's Theorem

    Iff p is a prime then (p-1)!+1\equiv{0} \mod\text{ p}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    congruence mods

    Okay that makes a lot of sense thank you so much!!!

    In solving x9^(794) mod 73

    I see where 9^72 *9^72 (until I get 794) but here I'm a little stuck cause 9^72 (11 times) gives me 9^792 so then at that point would I also include 9^2??
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by duggaboy View Post
    Okay that makes a lot of sense thank you so much!!!

    In solving x9^(794) mod 73

    I see where 9^72 *9^72 (until I get 794) but here I'm a little stuck cause 9^72 (11 times) gives me 9^792 so then at that point would I also include 9^2??
    Yep, nearly ^^


    Actually, when dealing with such questions, always find the power to which the number (here, 9) will be congruent to 1 modulo n (794).

    Then, do the Euclidian division :

    794=72*11+2

    Therefore 9^{794}=(9^{72})^{11}*9^2 (these are powers rules)


    -------> 9^{794}=1^{11}*9^2 \mod 794

    Conclude ?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    getting so close

    BTW your the BEST!!

    now that I have the 1^11*9^2 (mod 794)

    Would I use the equation a^p = 9 + 794k to find a?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by duggaboy View Post
    BTW your the BEST!!

    now that I have the 1^11*9^2 (mod 794)

    Would I use the equation a^p = 9 + 794k to find a?
    Hmmmm strange oO
    what is this formula ?



    All you need is to "simplify" 9^{794} \mod 73, in order to get x.

    x=1^{11}*9^2 \mod 73, not 794 Don't confuse with the numbers, it's quite common to see that kind of mistakes ^^

    Now, just simplify 1^11 and calculate 9. It will give you x
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    ahha

    not sure where i came across that formula ??
    mods kill me!!

    THANK YOU AGAIN!
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by duggaboy View Post
    mods kill me!!
    Okay. How would you like to die?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Jun 2008
    Posts
    39

    checking point

    when solving for x here using the approach from the previous problem

    x^86 = = 6 (mod 29)

    I am getting
    x = 36 (mod 29)

    36^86 = = 6 (mod 29) or just

    36 = = 6 (mod 29)
    Last edited by duggaboy; June 2nd 2008 at 03:38 PM. Reason: question
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  2. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 24th 2010, 12:51 PM
  3. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 11th 2010, 09:43 AM
  4. Find x in the congruence using Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: March 24th 2009, 10:15 AM
  5. Replies: 1
    Last Post: March 9th 2009, 01:51 PM

Search Tags


/mathhelpforum @mathhelpforum