Fermat primality test

by Firepanda
Tags: fermat, primality, test
 P: 432 Use the Fermat test for the base a = 2 to show that 240+1 is not a prime number. so, attempting 2240 = 1 mod (240+1) But what now? :/ unusually large modulo im not use to, must be some trick to this? Thanks
 P: 432 Another attempt: using the above 2240 = 1 mod (240+1) write 2240 as 264624 now: 26464524 and 264 = 0 mod (240+1) according to my calculator, so 2240 = 0 mod (240+1) edit: wolfram mathworld disagrees with my calculator on 264 = 0 mod (240+1) so I guess this is wrong edit again: it was pretty obvious my calculator was wrong actually as 240+1 is odd and 264 is even
P: 311
 Quote by Firepanda Use the Fermat test for the base a = 2 to show that 240+1 is not a prime number.
Do you not really want to show that 2240+1 is not a prime number?

P: 432

Fermat primality test

 Quote by Martin Rattigan Do you not really want to show that 2240+1 is not a prime number?
nope the question is for 240+1
 P: 311 But isn't that pretty obvious? If 240+1 were a prime p then 2 would have order 80 in the nonzero multiplicative group, so 5 would have to divide p-1=240 (which is clearly not on).
 P: 432 well it depends on how obvious you think that is :P well i know how to show p cannot be prime using the miller-rabin test but the question states to use fermats primality test, and that's what I'm stuck on unless that shows it, but it looks like a pretty abstract method I've never had practise with
 P: 311 OK then 240+1=(28)5+1. Try dividing that by (28)+1. What would the remainder be?
 P: 311 If you do that it should become clear that the first test for a number 2n+1 to be prime is that n is a power of 2.
P: 432
 Quote by Martin Rattigan OK then 240+1=(28)5+1. Try dividing that by (28)+1. What would the remainder be?
I'm not following why we're doing that..

(28+1).25 -31 = 240+1

is what i think you're asking..
 P: 403 Fermat's theorem tells you that, for example: $$2^{4}\equiv 1\left(\rm{mod} 5\right)$$ What does this imply for $2^{40} \left(\rm{mod 5}\right)$?
P: 432
 Quote by JSuarez Fermat's theorem tells you that, for example: $$2^{4}\equiv 1\left(\rm{mod} 5\right)$$ What does this imply for $2^{40} \left(\rm{mod 5}\right)$?
is congruent to 1 also
 P: 403 Exactly. How could you use this to simplify your original congruence (the one from the Fermat test)? Could you use it to prove that 2240 falsifies the test?
P: 432
 Quote by JSuarez Exactly. How could you use this to simplify your original congruence (the one from the Fermat test)? Could you use it to prove that 2240 falsifies the test?
well I'm not too sure why we're working in mod 5 all of a sudden, it's part of the prime factorization of 40 is all i can see
 P: 311 Sorry - had to disappear to bed last night. What I asked was badly put. Sometimes you can factorize numbers that are given by substituting numbers into a polynomial by factorizing the polynomial and then substituting the numbers. So when I said try dividing (28)5+1 by 28+1, I was really hinting at factorizing x5+1. When n is odd xn+1 factorizes as (x+1)(xn-1-xn-2+xn-3 ... +1). The first term in the right hand bracket gives you the xn you want in the answer when you multiply by the x from the first bracket, but you get an unwanted xn-1 when you multiply it by the 1. The second term cancels the first unwanted term when you multiply by the x, but gives you a new unwanted term -xn-2 and so on. Each term after the first in the right hand bracket cancels out the unwanted term you get from multiplying the previous term by x+1. That carries on till you get down to 1, when the "unwanted" term is actually exactly what you want i.e. the 1 from xn+1. This only works when n is odd because the signs in the second bracket alternate and for even n you finish up with a -1 at the end instead of 1. Anyway if you replace x in x5+1=(x+1)(x4-x3+x2-x+1) by 28 this gives you an explicit factorization of 240+1. If you think about the above process you should be able to see that you will always be able to factorize a number of the form 2n+1 if n has an odd factor. Which means 2n+1 has no chance of being prime unless n is a power of 2. Another way of looking at it is to use the ideas behind the test you wanted to apply. If p is a prime number the numbers other than 0 mod p form a group under multiplication. If you have a prime p and p=2n+1 then the order of this group is 2n. Because 2n+1=0 mod p 2n=-1 mod p so 22n=1 mod p which means that the order of 2 is a divisor of 2n larger than n. (Notice that none of the numbers 2, 22, ... 2n can be 1 mod p.) The order of 2 is thus 2n. But then 2n must be a factor of 2n, so again n must be a power of 2. It is quicker in this case to check whether 40 is a power of 2 (no) than to go ahead with checking that 2p-1=1 mod p.

 Related Discussions Linear & Abstract Algebra 1 Linear & Abstract Algebra 6 Linear & Abstract Algebra 11 Introductory Physics Homework 2 Linear & Abstract Algebra 2