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

Homework Help: Discrete Math Problem

  1. Nov 2, 2005 #1
    could someone show me how u would solve 2^27841 mod 34 by hand? I know what theorm to use, im just having trouble using it? Thanks
     
  2. jcsd
  3. Nov 2, 2005 #2

    AKG

    User Avatar
    Science Advisor
    Homework Helper

    What theorem would you use? Anyways, if it helps, 27841 = 11x2531 and 34 = 2x17. I found that 11 was a factor of 27841 by trial and error, and then by a lot more trial and error, found that 2531 is prime. Hopefully I didn't make a mistake in the calculations.
     
  4. Nov 2, 2005 #3
    Is there any other way to do this without changing the base?
     
  5. Nov 2, 2005 #4

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Euler's totient theorem?
    Is a bit tricky because 34 and 2 are not co-prime.
    but
    [tex]2^{17} \equiv 2 \mod 34[/tex]
    Then we can use that
    [tex]27841 \equiv 1 \mod 16[/tex]
    to get
    [tex]2^{27841} \equiv 2^{1} \equiv 2 \mod 34[/tex]
     
  6. Nov 3, 2005 #5
    hrm yeah that works. How would you solve it with modular exponentiation?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook