1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    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


    User Avatar
    Science Advisor
    Homework Helper

    Euler's totient theorem?
    Is a bit tricky because 34 and 2 are not co-prime.
    [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