Paper 3, Section I, G

Number Theory
Part II, 2017

Explain what is meant by an Euler pseudoprime and a strong pseudoprime. Show that 65 is an Euler pseudoprime to the base bb if and only if b2±1(mod65)b^{2} \equiv \pm 1(\bmod 65). How many such bases are there? Show that the bases for which 65 is a strong pseudoprime do not form a subgroup of (Z/65Z)×(\mathbb{Z} / 65 \mathbb{Z})^{\times}.