My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
May 5th, 2012, 01: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 !
fe phi fo is offline  
 
May 5th, 2012, 01:16 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

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.
CRGreathouse is offline  
May 6th, 2012, 09: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!
fe phi fo is offline  
May 6th, 2012, 12:17 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Fermat's little theorem ( stuck on completing a question

Quote:
Originally Posted by fe phi fo
and how can you simplify 9 * (9^5)^2? ( As 5 is a prime ? )
Lots of ways. For one, you can replace 9^5 with 9 * 9^4 and 9^4 with (9^2)^2.
CRGreathouse is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
completing, fermat, question, stuck, theorem



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


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





Copyright © 2017 My Math Forum. All rights reserved.