Product of successive primes in Cunningham chain of the second kind satisfying congruence conditions is Poulet number
Suppose is an odd prime number such that is also a prime number. Then, the number:
Note that the condition that are both primes means that they are consecutive members of a Cunningham chain of the second kind.
We give here the smallest few values of such that are both primes, and the corresponding Poulet numbers.
|Corresponding Poulet number (Fermat pseudoprime to base 2)|
- Fermat's little theorem
- Euler's criterion (for quadratic residue)
- Congruence condition for two to be a quadratic residue
Given: is a prime number such that is also a prime number. Let .
To prove: if and only if .
Proof: We have:
We thus have:
|Step no.||Assertion/construction||Facts used||Given data used||Previous steps used||Explanation|
|1||is congruent to 1 mod , or equivalently, is divisible by .||Fact (1)||is prime||The order of 2 mod p divides , which divides . More explicitly: [SHOW MORE]|
|2||is congruent to 1 or -1 mod , depending on whether 2 is a quadratic residue mod (1 if it is, -1 if it isn't)||Facts (1), (2)||is prime||[SHOW MORE]|
|3||is congruent to 1 or -1 mod , with 1 iff is congruent to 1 mod 12.||Fact (3)||are primes, is odd||Step (2)||[SHOW MORE]|
|4||is congruent to 1 mod iff .||Steps (1), (3)||Step-combination direct.|