# Homework Help: Fermat primality test

1. Apr 30, 2010

### Firepanda

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

2. Apr 30, 2010

### Firepanda

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

Last edited: Apr 30, 2010
3. Apr 30, 2010

### Martin Rattigan

Do you not really want to show that 2240+1 is not a prime number?

4. Apr 30, 2010

### Firepanda

nope the question is for 240+1

5. Apr 30, 2010

### Martin Rattigan

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).

6. Apr 30, 2010

### Firepanda

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

7. Apr 30, 2010

### Martin Rattigan

OK then 240+1=(28)5+1. Try dividing that by (28)+1. What would the remainder be?

8. Apr 30, 2010

### Martin Rattigan

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.

Last edited: Apr 30, 2010
9. Apr 30, 2010

### Firepanda

I'm not following why we're doing that..

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

is what i think you're asking..

10. Apr 30, 2010

### 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)$?

11. Apr 30, 2010

### Firepanda

is congruent to 1 also

12. Apr 30, 2010

### 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?

13. Apr 30, 2010

### Firepanda

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

14. May 1, 2010

### Martin Rattigan

Sorry - had to disappear to bed last night.

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.

Last edited: May 1, 2010