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)$$
    Then
    $$43^{43}\equiv9^{43}\ (mod\ 17)$$
    and that I can rewrite this as:
    $$9^{43}=\left(9^{2}\right)^{16}\times9^{11}$$
    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




Loading...
Similar Threads for Congruence identities using Date
Diff eq with constants.. Eulers identity.. Mar 17, 2018
Chinese Remainder theorem for 2 congruences Mar 10, 2018
How can I find 544 mod 3 using congruence Feb 19, 2018
Congruence and primes Jan 8, 2018
Solving simultaneous congruences Oct 4, 2015