In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem. Fermat's little theorem states that if p is prime and a is coprime to p, then \(a^{p−1} − 1 \) is divisible by p.
For an integer a > 1, if a composite integer x divides \( a^{x−1} − 1, \) then x is called a Fermat pseudoprime to base a. In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes the Fermat primality test for the base a. It follows that if x is a Fermat pseudoprime to base a, then x is coprime to a.
The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: \( 2^{340} ≡ 1 \) (mod 341) and thus passes the Fermat primality test for the base 2. Pseudoprimes to base 2 are sometimes called Poulet numbers, after the Belgian mathematician Paul Poulet, Sarrus numbers, or Fermatians (sequence A001567 in the OEIS).
A Fermat pseudoprime is often called a pseudoprime, with the modifier Fermat being understood. An integer x that is a Fermat pseudoprime for all values of a that are coprime to x is called a Carmichael number.Now 25351 is a member of OEIS A005936: Pseudoprimes to base 5. This is because \( 5^{25350} ≡ 1 \) (mod 25351). However, it turns out that 25351 is not simply a Fermat pseudoprime. It is also a strong pseudoprime defined by Wikipedia as:
In number theory, a probable prime is a number that passes a primality test. A strong probable prime is a number that passes a strong version of a primality test. All primes pass these tests, but a small fraction of composites also pass, making them "false primes". Unlike the Fermat pseudoprimes, for which there exist numbers that are pseudoprimes to all coprime bases (the Carmichael numbers), there are no composites that are strong pseudoprimes to all bases.
Formally, an odd composite number \(n = d \times 2^s + 1 \) with d also odd is called a strong (Fermat) pseudoprime to a base a when one of the following conditions holds:$$ a^{d} \equiv 1\! \mod n \text{ or}$$$$a^{d\cdot 2^{r}}\equiv -1 \!\mod n\quad {\mbox{ for some }}0\leq r < s $$ If a number n satisfies one of the above conditions and we don't yet know whether it is prime, it is more precise to refer to it as a strong probable prime to base a. But if we know that n is not prime, then one may use the term strong pseudoprime. The definition is trivially met if a ≡ ±1 mod n so these trivial bases are often excluded. Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.
Now 25351 = 2 * 12675 + 1 satisfies the \(n = 12675\times 2^s + 1 \) form and
\( 5^{12675} ≡ 1 \) (mod 25351). Hence 25351 is a strong pseudoprime. This condition may seem somewhat arbitrary but there is good explanation of why it's so at WolframAlpha.
Things get more complicated still when we learn that 25351 is also a Euler pseudoprime but I'm not going to delve any deeper at the moment. That's probably enough except that I'll finish up by saying a little about the Carmichael numbers that satisfy Fermat's little theorem to all coprime bases. The first of these numbers are 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841 and 29341. Carmichael numbers have at least three positive prime factors e.g. 561 = 3 * 11 * 17.
ADDENDUM: entered on March 11th 2020
I'm revisiting pseudoprimes because it's a topic about which I always seem to get confused. I've mentioned them previously in the following posts:
- Fermat Pseudoprimes on the 30th August 2018
- Carmichael Numbers on the 30th January 2019
- The Original Taxi Cab Number in a New Light on the 21st December 2019
What brought to mind again was the number 25909, the number of days old that I was yesterday. One of its properties is that it's a member of OEIS A020267: strong pseudoprimes to base 41. Now it's easy enough to show that it's a pseudoprime to base 41 because$$41^{25908}-1 \equiv 0 \bmod{25909}$$However, to show 25909 is a strong pseudoprime, it needs to fulfil one of two possible conditions. Formally, an odd composite number \(n = d \times 2^s + 1\) with d also odd is called a strong (Fermat) pseudoprime to a base, when one of the following conditions holds:$$ a^{d} \equiv 1\! \mod n \text{ or}$$$$a^{d\cdot 2^{r}}\equiv -1 \!\mod n\quad {\mbox{ for some }}0\leq r \leq s $$So in the case of 25909 we have: $$25909=25908+1=2^2 \times 3 \times 17 \times 127+1=6477 \times 2^2+1$$The value of \(d\) here is 6477 so let's test it out using the first condition. We find that:$$41^{6477} \equiv 8805 \bmod{25909}$$Clearly it does not pass the first test, so let's try the second.$$41^{6477*2} \equiv -1 \bmod 25909$$It passes and so 25909 can claim to be a strong pseudoprime.
No comments:
Post a Comment