Fermat primality test

Firepanda

Use the Fermat test for the base a = 2 to show that 2⁴⁰+1 is not
a prime number.

so, attempting

2²⁴⁰ = 1 mod (2⁴⁰+1)

But what now? :/ unusually large modulo im not use to, must be some trick to this?

Thanks

Firepanda

Another attempt:

using the above

2²⁴⁰ = 1 mod (2⁴⁰+1)

write 2²⁴⁰

as 2⁶⁴⁶²⁴

now: 2^6464524

and 2⁶⁴ = 0 mod (2⁴⁰+1)

according to my calculator,

so 2²⁴⁰ = 0 mod (2⁴⁰+1)

edit: wolfram mathworld disagrees with my calculator on 2⁶⁴ = 0 mod (2⁴⁰+1) so I guess this is wrong
edit again: it was pretty obvious my calculator was wrong actually as 2⁴⁰+1 is odd and 2⁶⁴ is even

Martin Rattigan

Do you not really want to show that 2²⁴⁰+1 is not a prime number?

Firepanda

nope the question is for 2⁴⁰+1

Martin Rattigan

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

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

Martin Rattigan

OK then 2⁴⁰+1=(2⁸)⁵+1. Try dividing that by (2⁸)+1. What would the remainder be?

Martin Rattigan

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

Firepanda

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

(2⁸+1).2⁵ -31 = 2⁴⁰+1

is what i think you're asking..

JSuarez

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

Firepanda

is congruent to 1 also

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 2²⁴⁰ falsifies the test?

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

Martin Rattigan

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⁸)⁵+1 by 2⁸+1, I was really hinting at factorizing x⁵+1.

When n is odd xⁿ+1 factorizes as (x+1)(x^n-1-x^n-2+x^n-3 ... +1). The first term in the right hand bracket gives you the xⁿ you want in the answer when you multiply by the x from the first bracket, but you get an unwanted x^n-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 -x^n-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 xⁿ+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⁵+1=(x+1)(x⁴-x³+x²-x+1) by 2⁸ this gives you an explicit factorization of 2⁴⁰+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ⁿ+1 if n has an odd factor. Which means 2ⁿ+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ⁿ+1 then the order of this group is 2ⁿ.

Because 2ⁿ+1=0 mod p

2ⁿ=-1 mod p

so

2²ⁿ=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ⁿ can be 1 mod p.) The order of 2 is thus 2n. But then 2n must be a factor of 2ⁿ, 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^p-1=1 mod p.