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

Mod problem. can someone help

  1. Oct 19, 2006 #1
    compute 6^100 (mod 13).
    Compute 5^100 (mod 13).
     
  2. jcsd
  3. Oct 19, 2006 #2

    shmoe

    User Avatar
    Science Advisor
    Homework Helper

    What have you tried so far? First hint is to make use of Fermat's little theorem.
     
  4. Oct 19, 2006 #3
    Fermat's little theorem
    is that a^p=a*(mod p)

    but we have 6^100 mod13

    a=6
    p=100

    6=6(mod100)?
    we want mod 13 though
     
  5. Oct 20, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    What is (x^a)*(x^b)? (Forget mod at the moment.)
     
  6. Oct 20, 2006 #5
    x^(a*b)?
    i dont quiet understand or how that help us.
     
  7. Oct 20, 2006 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    No, that is not correct. And it does help. Have a ponder on it. If I wanted to work out x^{some really large number}, can I use smaller powers of x to get there? (Yes.)
     
  8. Oct 21, 2006 #7
    x^a*x^b
    =x^(a+b)
    ?
    can you guys give me the answer and i can work backward? because i can try many ways and will not know its the correct answer or not.
    thanks
     
  9. Oct 22, 2006 #8

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Just giving you the answer won't mean that the method you get to get the same number is correct or not.

    If 6^12=1, mod 13, what is 6^24?
     
  10. Oct 22, 2006 #9

    JasonRox

    User Avatar
    Homework Helper
    Gold Member

    I would suggest exploring what happens when you have large exponents, but in simple cases.

    matt grime points you in the right direction.

    Note: Mathematics is about going forward and not backwards.
     
  11. Oct 22, 2006 #10
    try [tex]6^{100} \left(\bmod \ 13\right) = \left(6^{12}\right)^8.6^4 \left(\bmod \ 13\right)[/tex]
    and [tex]5^{100} \left(\bmod \ 13\right) = \left(5^{12}\right)^8.5^4 \left(\bmod \ 13\right)[/tex]
     
    Last edited: Oct 22, 2006
  12. Oct 23, 2006 #11
    I did this using excel

    6^100mod13 is equal to 9?

    if its right, i think i did it right.

    5^100mod13 is equal to 1?
     
  13. Oct 23, 2006 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Excel? Why? Did you not pay attention to the hints people have given you? If you raised 6 to the power 100 then reduced mod 13 you did it wrong. There is never any need to raise 6 (or any number coprime to 13) higer than the power 11 because x^12=1 mod 13 for x coprime with 13.
     
  14. Oct 23, 2006 #13
    i follow the notes from my class.
    the teacher created a chart of
    all possible number n, 6^n, 6^n%13.
    6^100 = (6^10)^10?
    and knowing that 6^10=4
    4^10mod13 =9
    therefore 6^100mod13=9

    n 6^n 6^n % 13
    1 6 6
    2 36 10
    3 216 8
    4 1296 9
    5 7776 2
    6 46656 12
    7 279936 7
    8 1679616 3
    9 10077696 5
    10 60466176 4
    11 362797056 11
    12 2176782336 9
     
  15. Oct 24, 2006 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Since you know all of the powers of 6 mod 13, why go to powers of 4? It is completely unnecessary. Further, why, for simplicitly do you use 36 for 6^2, instead of 10? There is never any need to work out powers large than 12 (for mod(13)), and never any need to multiply numbers that are larger than 13 (for mod(13)). Useful to remember if you don't have a calculator, or a computer to use.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?