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
    9
    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 01: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
    9
    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 02: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, 08:51 AM
  2. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 24th 2010, 11:51 AM
  3. Fermat's Little Theorem
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 11th 2010, 08: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, 09:15 AM
  5. Replies: 1
    Last Post: March 9th 2009, 12:51 PM

Search Tags


/mathhelpforum @mathhelpforum