Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [pseudoprimes]

Pseudoprimes are composite numbers which pass some primality test - a property that is always true for prime numbers. This may be Fermat's Little Theorem for one base or many, or some other test.

Pseudoprimes are composite numbers that have some properties that every prime number has (that is, properties that might be used to test for primality).

For example, if $p$ is a prime number and $\gcd(b, p) = 1$, then, by Fermat's little theorem, $b^{p - 1} \equiv 1 \pmod p$. However, there are also composite numbers that satisfy this congruence for some coprime $b$ (these are called Fermat pseudoprimes) and composite numbers that satisfy this property for every coprime $b$ (these are called Carmichael numbers).

154 questions
4
votes
1 answer

Fermat and strong pseudoprimes

A composite number is said to be a Fermat pseudoprime to the base $a$ if $\gcd(a, n) = 1$ and $a^{n - 1} \equiv 1 \bmod n$. Let $n$ be an odd composite number, $n = t2^k + 1$ with $t$ odd. Let $a$ be such that $\gcd(a, n) = 1$. It is said that $n$…
Alicia Bryant
  • 53
  • 2
1
vote
1 answer

Pseudo-primes with non-prime bases

Given an odd integer n ≥ 5, and a base 2 ≤ a ≤ n-2, $a^{n-1} = 1 \mod n$ whenever n is a prime, and whenever the result is not 1, n is composite. Plus composite numbers where the result is 1 are rare. A composite number passing this test is a…
gnasher729
  • 10,113
1
vote
1 answer

Has anyone explored prime-like numbers in other dimensions?

Prime numbers are often described with an example like the following: 'if you have n counters, and can't make a rectangle which has both sides longer than 1, n is prime' I think it would be interesting to see what happens if we extend this to 'if…
JeffUK
  • 117
0
votes
4 answers

Why is $561$ missing from this list?

On the MathWorld page: http://mathworld.wolfram.com/FermatPseudoprime.html in the first table, I expect to see $561$ on every line, but it is not on the line for base $3$. When you click on the link to the OEIS page, it also is missing from the…
B. Goddard
  • 1
0
votes
2 answers

A number is a pseudoprime

Can Someone please help me prove that the number 1729 is a Pseudoprime? So a pseudoprime is a composite $n$ such that $n |(2^n − 2)$. And every prime number also has this property.
Ryan Sole
  • 1