Let p be a Sophie Germain prime. Let q = 2p + 1. Let a = −q − 2p. Given that q ≡ 3 (mod p − 1), prove that pq is a pseudoprime to base a.
I want to show pq is pseudoprime to base a but I am struggling as p is Sophie Germain. $$q = 2p + 1$$ $$ a = -q-2p$$ $$q=3(mod(p-1))$$
I thought I could use Chinese Remainder Theorem but will unknowns not concrete values I am struggling making any progress in this way. I have my definition for pseudoprime as $a^n=a(modn)$ so any further advice would be great
$$a^{pq}-1=a(a^{pq-1}-1)=a(a^{\frac{pq-1}2}-1)(a^{\frac{pq-1}2}+1)$$
Due to Euler's criterion:
$a^{\frac{pq-1}2-1}-1 \equiv 0 \bmod pq$, if $a\equiv x^2 \bmod pq$
$a^{\frac{pq-1}2-1}+1 \equiv 0 \bmod pq$, if $a\not\equiv x^2 \bmod pq$
Hence in any case :
$a^{pq}-1\equiv 0 \bmod pq$
Example:
$p=11$, $q=2\cdot 11 +1=23$
$a=-23-2\times 22=-45$
$(-45)^{\frac{(23\times 11=253)-1}2 }=45^{126}$
$45^{126}=(45^2)^{63}$
$45^2=2025=(8\times 253 +1)\equiv 1 \bmod 253 $
Therefore:
$(a=-45)^{126}-1\equiv 0 bmod 253$
that is:
$(-45)^{11\times23}-(-45)\equiv 0\bmod (11\times 23)$
Comment: This is equivalent to $a^{n-1}-1\equiv 0 \bmod n$.