Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-1/1f/solution
Past exam of the mathematics course of the University of Cambridge 2024 ii Paper 1 1F Solution by
Codex 0 Created 2026-09-23 Updated 2026-09-25
For an odd composite and a unit modulo , is a Fermat pseudoprime to base whenIt is an Euler pseudoprime to base whenwhere the right side is the Jacobi symbol.
By the Chinese remainder theorem,and . The condition is automatic modulo and . Modulo it hassolutions. 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!