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!

Application of Fermat's Little Theorem

Tags:
  1. Nov 19, 2016 #1
    1. The problem statement, all variables and given/known data

    Find the remainder of ##4^{87}## in the division by ##17##.

    2. Relevant equations

    Fermat's Little Theorem:

    If ##p## is prime and ##a## is an integer not divisible by ##p##, then

    ##a^{p-1} \equiv 1 (\mod \space p)##

    or equivalently,

    ##a^p \equiv a (\mod \space p)##

    3. The attempt at a solution

    I began by directly applying the theorem, since ##p=17## is prime and doesn't divide ##a=4##:

    ##17|4^{17} - 4 \rightarrow 17|4(4^{16} - 1) \rightarrow 17|4^{16}-1##

    By definition of the modulo, ##p|a-b \rightarrow a \equiv b (\mod \space p)## , so ##4^{16} \equiv 1 (\mod \space 17)##

    Next I note that ##87 = 16 * 5 + 7##, so

    ##[4^{87}]_{17} = [4^{16*5 + 7}]_{17} = [4^{16*5}]_{17} * [4^7]_{17} = [4^{16}]^5_{17} * [4^7]_{17} = [1]^5_{17} * [4^7]_{17} = [1]_{17} * [4^7]_{17} = [4^7]_{17}##

    Then I repeated the process from the beginning based on the result I just got:

    ##17|4^7 - 4 \rightarrow 17|4(4^6 - 1) \rightarrow 17|4^6-1##, where ##4^6 \equiv 1 (\mod \space 17)##

    Since ##87 = 6 * 14 + 3##, I wrote

    ##[4^{87}]_{17} = [4^{6*14 + 3}]_{17} = [4^6]^{14}_{17} * [4^3]_{17} = [1]_{17} * [4^3]_{17} = [4^3]_{17}##

    At this point it seems easy enough to note that ##4^3 = 64## and

    ##64 = 17*3 + 13##

    So the remainder is 13... I think? Is this procedure correct?

    Just in case it is, I actually tried repeating the process once more when I got ##[4^3]_{17}##, so that

    ##17|4^3 - 4 \rightarrow 17|4(4^2 - 1) \rightarrow 17|4^2 -1##

    And, repeating the same procedure of rewriting the exponent, arrived at ##[4^{87}]_{17} = [4]_{17}##.

    Of course, 4 doesn't yield a remainder of 13 when divided by 17, unlike ##4^7## and ##4^3##.

    Naturally, it's easy enough to note that ## 4^2 -1 < 17##, so ##17## doesn't divide ##4^2 - 1##. I'm a little confused here, though... is it necessary for the term ##a^{p-1} - 1## to be larger than ##p## for the application of the theorem to work?
     
  2. jcsd
  3. Nov 19, 2016 #2

    fresh_42

    Staff: Mentor

    I haven't checked your calculation, but why don't you work with ##4^2##?
     
  4. Nov 19, 2016 #3

    I like Serena

    User Avatar
    Homework Helper

    Hi Enharmonics! :oldsmile:

    You were fine until you "repeated the process".
    Unfortunately ##17|4^7-4## is not true.
    Where did you get it from? It's not Fermat's little theorem.

    Instead we have:
    ##[4^6]_{17}=[(4^3)^2]_{17}=[64^2]_{17}=[13^2]_{17}=[(-4)^2]_{17}=[16]_{17}=[-1]_{17}##

    So we have ##4^6\equiv -1 \pmod{17}## and ##17|4^7+4##.
    It's by accident that it still yields the correct remainder 13.
     
  5. Nov 19, 2016 #4
    I got ##17|4^7-4## from the fact given by re-applying the fact that ##p|a^p-a## (taken from Fermat's Little Theorem). I thought that since I found it by using the fact that ##17|4^{17} - 4##, it would be okay to use. I kinda suspected it wasn't okay, since it would be uncharacteristically easy and formulaic given the subject matter (Discrete Math), so imagine how excited I was when I actually got the right answer! (even though it turned out to be by accident)

    I'm a bit lost now, though. If ##17|4^7-4## isn't valid, how come you start at ##[4^6]_{17}## when our last result was ##[4^87]_{17} = [4^7]_{17}##? Is it by using the fact that ##a^{p-1} = 1 (\mod \space p)##?

    Also, how did you do these particular steps:

    ##... [64^2]_{17}=[13^2]_{17}=[(-4)^2]_{17}= ... ##

    Is it just by using the Division Algorithm, i.e. ## 64 = 17*1 + 13##, ##13 = 17*1 + (-4)## ?

    Finally, how do I use the final result ##4^6 = -1 (\mod \space 17)## and ##17|4^7 +4## to show that the remainder is 13?

    Thanks.
     
  6. Nov 20, 2016 #5

    I like Serena

    User Avatar
    Homework Helper

    ... but that's not a re-application...
    A reapplication is either ##7|4^7-4## or ##17|4^{17}-4##.
    That's because the ##p## occurs twice and has to be the same!

    Yes. It's the division algorithm.

    Let's get back on track.
    We have:

    ##[4^{87}]_{17} \equiv 4^{7} \equiv (4^3)^2\cdot 4 \equiv 64^2 \cdot 4 \equiv (-4)^2 \cdot 4 \equiv 64 \equiv 13 \pmod{17}##
     
  7. Nov 20, 2016 #6

    fresh_42

    Staff: Mentor

    I still think to work with ##[4^2]_{17}## is by far less complicated.
     
  8. Nov 20, 2016 #7

    ehild

    User Avatar
    Homework Helper
    Gold Member

    Fermat's Little was not needed. 487=4*1643=4*(17-1)43. From the Binomial Theorem, all terms of (a-1)n divides by a, except the last term, which is (-1)n. So 1643=-1 mod 17. It is straightforward from here.
    edit: I think it is the same as fresh's hint.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Application of Fermat's Little Theorem
  1. Fermat Little Theorem? (Replies: 10)

Loading...