How this calculator works
For a prime modulus, raising any integer a to p leaves the same remainder as a. When p does not divide a, the related exponent p - 1 gives remainder 1. Repeated squaring computes the residues without constructing enormous powers. Trial division verifies the bounded prime input; Fermat congruences alone are not used as a primality proof.
Formula
For prime p, a^p ≡ a (mod p). If p does not divide a, then a^(p-1) ≡ 1 (mod p).
Worked example
With a = 2 and p = 7, 2^7 = 128 leaves remainder 2, and 2^6 = 64 leaves remainder 1. With a = 7 and p = 7, both powers leave remainder 0.
Advertisement
Frequently asked questions
Does a Fermat congruence prove primality?
No. Some composite numbers pass such checks for particular bases, and Carmichael numbers pass many of them.
What if p divides a?
The a^p congruence still holds, but a^(p-1) has remainder 0 rather than 1.
Can a be negative?
Yes. Modular residues are normalized to the interval from 0 to p - 1.