Math Is Fun Forum

Primenumbers

Member

Registered: 2013-01-22

Posts: 149

Using Fermat's Little Theorem to find primes.

Introduction

The following is a way to find out if (a) is prime or not using Fermat's Little Theorem.

Rule

will be factorable by all primes <square root a if a is prime, otherwise it won't be.
x=(All primes below square root a)-1, multiplied together. I.e. (2-1)(3-1)(5-1)(7-1)(11-1)....
a=any odd no.

Theory

Fermat's little theorem states that if p is a prime number, then for any integer a, the number

     is an integer multiple of p.
So if y=p-1 then

will be factorable by p.
We know that remainders repeat themselves in a pattern when multiplying by a. So y could be a multiple of y and the answer would still be factorable by p.
In this way as long as x is factorable by p-1 then the answer will be factorable by p unless (a) itself is factorable by p.

Example

a=37
x=(2-1)(3-1)(5-1)=8

will be factorable by 2x3x5=30 because 37 is prime

a=21
x=(2-1)(3-1)=2

won't be factorable by 2x3=6 because 21 is factorable by 3.

Conclusion

I don't know but I would have thought this method would be useful for computers as it only requires a few computations. Don't computers usually have to factor possible factors separately? The numbers are very large though.

---

"Time not important. Only life important." - The Fifth Element 1997

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Using Fermat's Little Theorem to find primes.

Hi;

It is generally considered too slow to factor very large primes using Fermat.

---

In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Primenumbers

Member

Registered: 2013-01-22

Posts: 149

Re: Using Fermat's Little Theorem to find primes.

Oh! Fair enough.

---

"Time not important. Only life important." - The Fifth Element 1997

googol

Member

From: Delft, The Netherlands

Registered: 2016-04-22

Posts: 13

Re: Using Fermat's Little Theorem to find primes.

Using Fermat is very fast however this prime test is not deterministic but probabilistic. There are composite numbers that pass this test called pseudoprimes.

---

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Primenumbers

Member

Registered: 2013-01-22

Posts: 149

Re: Using Fermat's Little Theorem to find primes.

What if you used the prime as the base? It would be impossible for it to be factorable by factors of a composite because you are minusing 1.

---

"Time not important. Only life important." - The Fifth Element 1997

googol

Member

From: Delft, The Netherlands

Registered: 2016-04-22

Posts: 13

Re: Using Fermat's Little Theorem to find primes.

I'm not sure what you mean, can you give an example?

---

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Primenumbers

Member

Registered: 2013-01-22

Posts: 149

Re: Using Fermat's Little Theorem to find primes.

Well usually you'd do

where x=(2-1)(3-1)(5-1)(7-1) and it would be factorable by 2,3,5,7........
But if you use a composite Ie.

it won't be factorable by 3 and 7.
In this way you can find out if the base is prime or not in one simple calculation!

---

"Time not important. Only life important." - The Fifth Element 1997

googol

Member

From: Delft, The Netherlands

Registered: 2016-04-22

Posts: 13

Re: Using Fermat's Little Theorem to find primes.

That won't solve the problem of the pseudoprimes. You can use different bases to eliminate most pseudoprimes but some are pseudo for all bases co-prime to p.
These are called Carmichael Numbers.

---

10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Primenumbers

Member

Registered: 2013-01-22

Posts: 149

Re: Using Fermat's Little Theorem to find primes.

No way! That's not awesome.

---

"Time not important. Only life important." - The Fifth Element 1997