Register to reply

Fermat primality test

by Firepanda
Tags: fermat, primality, test
Share this thread:
Firepanda
#1
Apr30-10, 05:28 PM
P: 431
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
Phys.Org News Partner Science news on Phys.org
New type of solar concentrator desn't block the view
Researchers demonstrate ultra low-field nuclear magnetic resonance using Earth's magnetic field
Asian inventions dominate energy storage systems
Firepanda
#2
Apr30-10, 05:46 PM
P: 431
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
Martin Rattigan
#3
Apr30-10, 06:20 PM
P: 312
Quote Quote by Firepanda View Post
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?

Firepanda
#4
Apr30-10, 06:22 PM
P: 431
Fermat primality test

Quote Quote by Martin Rattigan View Post
Do you not really want to show that 2240+1 is not a prime number?
nope the question is for 240+1
Martin Rattigan
#5
Apr30-10, 06:29 PM
P: 312
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).
Firepanda
#6
Apr30-10, 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 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
#7
Apr30-10, 06:44 PM
P: 312
OK then 240+1=(28)5+1. Try dividing that by (28)+1. What would the remainder be?
Martin Rattigan
#8
Apr30-10, 06:52 PM
P: 312
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.
Firepanda
#9
Apr30-10, 06:54 PM
P: 431
Quote Quote by Martin Rattigan View Post
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..
JSuarez
#10
Apr30-10, 09:11 PM
P: 402
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
#11
Apr30-10, 09:14 PM
P: 431
Quote Quote by JSuarez View Post
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]?
is congruent to 1 also
JSuarez
#12
Apr30-10, 09:24 PM
P: 402
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?
Firepanda
#13
Apr30-10, 09:26 PM
P: 431
Quote Quote by JSuarez View Post
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
Martin Rattigan
#14
May1-10, 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 (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.


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