Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-1/1f/solution

For an odd composite and a unit modulo , is a Fermat pseudoprime to base when
It is an Euler pseudoprime to base when
where the right side is the Jacobi symbol.
By the Chinese remainder theorem,
and . The condition is automatic modulo and . Modulo it has
solutions. Thus there are Fermat bases, giving proportion
For the Euler condition, modulo , so the Jacobi symbol must be . The power condition is automatic modulo , while modulo it again restricts to the two solutions of . For each of those two residues, exactly half of the choices modulo and have Jacobi symbol . Hence there are Euler bases and proportion

New to topics? Read the docs here!