Register to reply 
Fermat primality test 
Share this thread: 
#1
Apr3010, 05:28 PM

P: 431

Use the Fermat test for the base a = 2 to show that 2^{40}+1 is not
a prime number. so, attempting 2^{240} = 1 mod (2^{40}+1) But what now? :/ unusually large modulo im not use to, must be some trick to this? Thanks 


#2
Apr3010, 05:46 PM

P: 431

Another attempt:
using the above 2^{240} = 1 mod (2^{40}+1) write 2^{240} as 2^{646}^{24} now: 2^{64}^{645}^{24} and 2^{64} = 0 mod (2^{40}+1) according to my calculator, so 2^{240} = 0 mod (2^{40}+1) edit: wolfram mathworld disagrees with my calculator on 2^{64} = 0 mod (2^{40}+1) so I guess this is wrong edit again: it was pretty obvious my calculator was wrong actually as 2^{40}+1 is odd and 2^{64} is even 


#3
Apr3010, 06:20 PM

P: 312




#4
Apr3010, 06:22 PM

P: 431

Fermat primality test



#5
Apr3010, 06:29 PM

P: 312

But isn't that pretty obvious? If 2^{40}+1 were a prime p then 2 would have order 80 in the nonzero multiplicative group, so 5 would have to divide p1=2^{40} (which is clearly not on).



#6
Apr3010, 06:33 PM

P: 431

well it depends on how obvious you think that is :P
well i know how to show p cannot be prime using the millerrabin 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 


#7
Apr3010, 06:44 PM

P: 312

OK then 2^{40}+1=(2^{8})^{5}+1. Try dividing that by (2^{8})+1. What would the remainder be?



#8
Apr3010, 06:52 PM

P: 312

If you do that it should become clear that the first test for a number 2^{n}+1 to be prime is that n is a power of 2.



#9
Apr3010, 06:54 PM

P: 431

(2^{8}+1).2^{5} 31 = 2^{40}+1 is what i think you're asking.. 


#10
Apr3010, 09:11 PM

P: 403

Fermat's theorem tells you that, for example:
[tex] 2^{4}\equiv 1\left(\rm{mod} 5\right) [/tex] What does this imply for [itex]2^{40} \left(\rm{mod 5}\right)[/itex]? 


#11
Apr3010, 09:14 PM

P: 431




#12
Apr3010, 09:24 PM

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 2^{240} falsifies the test?



#13
Apr3010, 09:26 PM

P: 431




#14
May110, 03:37 AM

P: 312

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 (2^{8})^{5}+1 by 2^{8}+1, I was really hinting at factorizing x^{5}+1. When n is odd x^{n}+1 factorizes as (x+1)(x^{n1}x^{n2}+x^{n3} ... +1). The first term in the right hand bracket gives you the x^{n} you want in the answer when you multiply by the x from the first bracket, but you get an unwanted x^{n1} 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 x^{n2} 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 x^{n}+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 x^{5}+1=(x+1)(x^{4}x^{3}+x^{2}x+1) by 2^{8} this gives you an explicit factorization of 2^{40}+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 2^{n}+1 if n has an odd factor. Which means 2^{n}+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=2^{n}+1 then the order of this group is 2^{n}. Because 2^{n}+1=0 mod p 2^{n}=1 mod p so 2^{2n}=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, 2^{2}, ... 2^{n} can be 1 mod p.) The order of 2 is thus 2n. But then 2n must be a factor of 2^{n}, 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 2^{p1}=1 mod p. 


Register to reply 
Related Discussions  
Fast primality test for small numbers  Linear & Abstract Algebra  1  
Euler's theorem as primality test?  Linear & Abstract Algebra  6  
Another (candidate) test of primality of Mersenne number  Linear & Abstract Algebra  11  
Strong primality test ... ?  Introductory Physics Homework  2  
A primality test for Fermat numbers faster than Pépin's test ?  Linear & Abstract Algebra  2 