4
$\begingroup$

Is the following a correct statement for the Fermat primality test?

For all $b$ if

  1. $n$ is prime and
  2. $(b,n)=1$

then $b^{n-1} \equiv 1 \bmod{n}$.

The contrapositive is if $b^{n-1} \not \equiv 1 \bmod{n}$ then condition (1) and/or (2) is false (they are equivalent --both attest to $n$ not being prime).

$\endgroup$
  • $\begingroup$ It's not enough to tell you that $n$ is prime if it passes but it is enough to tell you that $n$ is not prime if it fails. $\endgroup$ – fleablood May 30 '18 at 18:10
  • $\begingroup$ Actually $b^{n-1}\equiv 0 \mod n$ is could mean $n$ is prime and $n|b$. So condition 2) being false does not attest to $n$ not being prime (but only if $(b,n) =n$). $\endgroup$ – fleablood May 30 '18 at 18:12
  • $\begingroup$ Instead of the statement $(b,n)=1$ you can just check for all $b$ from $1$ till $n-1$. If it doesn't pass the test, it is definitely not prime. If it does, it is mostly prime. A composite number that passes this test is known as a Carmichael number (e.g. $561$) $\endgroup$ – Haran May 31 '18 at 6:25
1
$\begingroup$

No, it's not, it's a correct statement of the test that tests whether $n$ is a prime number or a Carmichael number. That's a subtly different thing.

From a theoretical point of view, it doesn't matter if $b < n$ or not. For example, $$b^{n - 1} \equiv (n + b)^{n - 1} \pmod n.$$ The same goes for $2n + b$, $3n + b$, etc.

From a practical point of view, you need to be able to tell your algorithm to stop somewhere. $n - 1$ might not be the optimal point to stop, but it's much better than the largest number you can handle, e.g., to test $561$ it's better to stop at $560$ than at $2^{31} - 1$.

Then your algorithm is going to test each $b$ from $2$ to $n - 1$. However, you have the condition of $(b, n) = 1$ as of this writing. So if $n$ is composite, then the test as you originally wrote it requires us to skip $b$ such that $\gcd(b, n) > 1$ even if $b < n$.

Nor did you say to skip $b$ known to be composite, at least not in the original statement of your question.

Therefore, what you have is a test that returns true if $n$ is prime or a Carmichael number (see Sloane's OEIS).

But since the Carmichael numbers are relatively rare, if a large number (like a prime close to the largest known Mersenne prime) is a Fermat pseudoprime to a lot of small $b$, it might be a prime number after all.

$\endgroup$
  • $\begingroup$ Is This a valid statement: n is prime iff for all a bet 2 and n-2 , a^(n-1) =1 mod n. $\endgroup$ – j yar Aug 12 '18 at 21:35
0
$\begingroup$

If you don't require the test to be definitive, then, well, um, maybe.

For it to be practical, however, I would change "all $b$" to "all $1 < b < n$". Obviously $n^{n - 1} \equiv 0 \bmod n$. Since this test involves exponentiation, I would want to avoid having to do more multiplications than necessary.

Let's try $n = 341$. Clearly 341 is an odd number. Either Wolfram Mathematica or Wolfram Alpha readily tells us that $2^{340} \equiv 1 \bmod 341$. Likewise we see that with a base 10 digital root of 8, 341 is not divisible by 3 but $3^{340} \equiv 56 \bmod 341$. Indeed $341 = 11 \times 31$. Looks like the test works.

But let's not be satisfied with one successful run. How about $n = 561$? I'm not pulling that number out of a hat. It came from one of the comments.

Okay, so 561 is also odd, and we see that $2^{560} \equiv 1 \bmod 561$. With a digit sum of 12, we see that 561 is divisible by 3, so we skip 3 and move on to 4. We see that $4^{560} \equiv 1 \bmod 561$ which means that the...

Hey, wait a minute! If 561 is divisible by 3, can it be prime? No, it's composite. Indeed $3^{560} \equiv 375 \bmod 561$. But you will find that if $b$ is not divisible by 3, 11 or 17, then $b^{560} \equiv 1 \bmod 561$.

This is why 341 is called a pseudoprime to base 2 and a few others, and 561 is called a pseudoprime to bases 2, 4, 5, 7, 8, 10, 13, 14, etc.

This means that the Fermat primality test is by itself not reliable, it gives a lot of small false positives. However, if for a largish odd number you can rule out a lot of small primes (like 3, 11, 17) as prime factors with trial division, and it's a pseudoprime to a lot of small bases, that might be a good enough indication of primality for your purposes.

By the way, PrimeQ in Wolfram Mathematica is not definitive either. But no one has found a false positive yet, maybe no one ever will.

$\endgroup$
  • $\begingroup$ The question is, if youdo not know whether n is prime and we get b^(n-1) not congruent to 1 then condition 1 or 2 is violated and n must be composite ex 3^560 = 375 (mod 561) and so 561 is composite. what is wrong with that logic? $\endgroup$ – j yar May 31 '18 at 22:32
  • 1
    $\begingroup$ Nothing, unless you give it to a computer that tries to do exactly what you told it to do. The computer would check 2, 4, 5, 7, 8, 10, 13, 14, 16, 19, 20, 23, etc., up to 560 and report that 561 is prime even though it's not. $\endgroup$ – Robert Soupe Jun 1 '18 at 1:47
  • $\begingroup$ NO. You tell the computer : Do i= 2, n ,if i^(n-1)Not congruent to 1, OUPUT composite ELSE output PRIME Actually you need only try primes. I think this test may even be deterrmenistic ie it will catch carmichael #s $\endgroup$ – j yar Jun 1 '18 at 16:55
  • 1
    $\begingroup$ Because $\gcd(b = \{3, 11, 17\}, n = 561) > 1$. By my understanding of what you highlighted in your original question text, those $b$ are not to be tested against $b^{560} \bmod 561$. $\endgroup$ – Robert Soupe Jun 1 '18 at 19:32
  • 1
    $\begingroup$ Thus the best test would be : for all b, 1<b<n compute (b,n) if >1, n is composite,if =1 for all b ,n is prime. Then the question becomes what is more efficient computationally computing b^(n-1)mod n or (b,n)?? $\endgroup$ – j yar Jun 1 '18 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.