Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Congruences, Fermats Little Theorm

  1. Sep 29, 2004 #1
    Can someone explain how to solve these types of things, my book gives one example and its useless:

    find a such that 0 < a < 73
    a=9^794(mod 73) (= means congruent equals)

    solve
    x^86=6(mod 29)

    Thanks in advance :smile:
     
  2. jcsd
  3. Sep 29, 2004 #2
    In the equation X^86 ==6 Mod 29, we note that for X not 0, X^28==1, by Fermat's Little Theorem. Thus X^86 ==X^28*X^28*X^28*X^2 ==X^2==6 Mod 29. That should be a start on the problem.
     
  4. Sep 29, 2004 #3

    Gokul43201

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    For the first problem :

    You could start from the ground up :

    9^2 = 81== 8 (mod 73) => 9^4 == 64 == -9 => 9^8==81==8...(lucky!) and so on, but you don't have to, because 73 is prime and does not divide 9. So you can happily use the Little Theorem.

    ie: 9^72 == 1 (mod 73) => (9^72)^n == 1^n = 1 (mod 73), for any n. With n=11, you get 9^792==1 (mod 73).

    So 9^794 == 9^2 (mod 73)
     
    Last edited: Sep 29, 2004
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Congruences, Fermats Little Theorm
Loading...