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: Congruence identities using Fermat's Little Theorem

  1. Apr 15, 2012 #1
    1. The problem statement, all variables and given/known data

    Show the remainder when 43^43 is divided by 17.

    2. Relevant equations

    $$43 = 16 \times 2 + 11$$
    $$a^{p-1}\equiv1\ (mod\ p)$$

    3. The attempt at a solution

    I believe I can state at the outset that as:
    $$43\equiv9\ (mod\ 17)$$
    $$43^{43}\equiv9^{43}\ (mod\ 17)$$
    and that I can rewrite this as:
    Then applying Fermat's Little Theorem we get:
    $$\left(9^{2}\right)^{16}\equiv1\ (mod\ 17)$$
    So that
    $$43^{43}\equiv 1\times9^{11}\ (mod\ 17)$$
    But I'm unsure where to go from here.
    Any help appreciated
  2. jcsd
  3. Apr 15, 2012 #2
    There are numerous ways to go about solving the problem from this kind of point. You just try to simplify the numbers more and more. A nice way I found to solve this is to consider [itex]9^2 (mod 17)[/itex]. You can simplify the problem nicely in the next step after that.
  4. Apr 15, 2012 #3
    Thanks for taking the time out.
    I feel like I'm probably not far away!

    $$9^2\equiv13\ (mod\ 17)$$

    So I guess I can consider $$9^{11}=\left(9^2\right)^5\times9$$ and simplify to:

    $$43^{43}\equiv13^5\times 9$$

    But still unsure how to proceed. I'll have another think...
  5. Apr 15, 2012 #4
    Okay, good! What is another way of writing 13 mod 17?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook