
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
May 5th, 2012, 12:10 PM  #1 
Member Joined: Dec 2011 Posts: 75 Thanks: 0  Fermat's little theorem ( stuck on completing a question)
Hey all! just stuck on a question, would be grateful if someone could help! 1) Use Fermat’s Little Theorem to find the remainder when 43^43 is divided by 17. (Use the fact that 43 = 2×16 + 11.) this is where I've got to so far 43 = 9 (mod 17) so 43^43 = 9^43 (mod 17) Fermat's theorem gives us p = 17 and a = 9 hence 9^16 = 1 (mod 17) therefore knowing (43 = 16 *2 + 11) gives us 43^43 = 9^43 = (9^16)^2 + 9^11 = (1)^2 + 9^11 this is were I'm stuck how do i complete this ? 9^11 is a big number!! many thanks ! 
May 5th, 2012, 12:16 PM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Fermat's little theorem ( stuck on completing a question
a^(b + c) is a^b * a^c, not a^b + a^c. You'll need to fix that to get the right answer. You can always break the problem down modularly, even when you're not using the Little Theorem. So 9^11 = 9 * 9^10 = 9 * (9^5)^2 mod 17. If 9^5 is still too big, break it down similarly. 
May 6th, 2012, 08:12 AM  #3 
Member Joined: Dec 2011 Posts: 75 Thanks: 0  Re: Fermat's little theorem ( stuck on completing a question
Hello CRGreathouse! Thanks for the reply! I really do struggle quite a lot with modular arithmetic, don't really know why. Just find it hard to picture whats going on! ( If you have any extra advice that would be great! ) but back to the question so basically I need to find a number that when 43^43 is divided by 17 it has a remainder (which is the number I'm after?) So did you mean I should do (9^16)^2 x 9^11 ? (as ^11 is a power?) and how can you simplify 9 * (9^5)^2? ( As 5 is a prime ? ) and when you simplify this, are you meant to leave that answer in that form? e.g 9 * (9^5)^2 mod 17 ? Tell me if I'm wrong here but this is what I understand of the idea of modular arithmetic. That any same number with different powers will produce a pattern, when divided by one particular number (So like 2^1 remainder something when divided by 7 and 2^2 remainder something when divided by 7) and eventually this pattern produces the only remainders of this number (number 2 in this example) regardless of the power? (pattern just repeats itself) So by finding a smaller power and working out the remainders in a pattern. I should be able to work out a larger power, just from the pattern produces from smaller sets of powers. ? I'm not sure I'm on the right track at all? If you have time further advice would be grateful! 
May 6th, 2012, 11:17 AM  #4  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Fermat's little theorem ( stuck on completing a question Quote:
 

Tags 
completing, fermat, question, stuck, theorem 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Fermat's Last Theorem  mathbalarka  Number Theory  2  April 3rd, 2012 11:03 AM 
More Fermat's Last Theorem.  theomoaner  Number Theory  29  November 26th, 2011 10:23 PM 
Brief : Fermat's last theorem  rnck  Number Theory  9  August 24th, 2011 04:58 AM 
Fermat's Last Theorem  McPogor  Number Theory  15  May 31st, 2011 07:31 AM 
Fermat's last theorem  xfaisalx  Number Theory  2  July 25th, 2010 04:59 AM 