Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**Primenumbers****Member**- Registered: 2013-01-22
- Posts: 127

**Introduction**

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

**Rule**

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

a=21

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

** 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*

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 107,661

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

Offline

**Primenumbers****Member**- Registered: 2013-01-22
- Posts: 127

Oh! Fair enough.

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

Offline

**googol****Member**- From: Delft, The Netherlands
- Registered: 2016-04-22
- Posts: 13

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**

Offline

**Primenumbers****Member**- Registered: 2013-01-22
- Posts: 127

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*

Offline

**googol****Member**- From: Delft, The Netherlands
- Registered: 2016-04-22
- Posts: 13

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

**10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000**

Offline

**Primenumbers****Member**- Registered: 2013-01-22
- Posts: 127

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*

Offline

**googol****Member**- From: Delft, The Netherlands
- Registered: 2016-04-22
- Posts: 13

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**

Offline

**Primenumbers****Member**- Registered: 2013-01-22
- Posts: 127

No way! That's not awesome.

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

Offline