HesapHanem

Fermat Primality Test Calculator

Enter a number and a base to run the Fermat primality test.

How it is calculated

The tool computes the residue r = an−1 mod n using fast modular exponentiation, so large powers are never written out in full. The largest n it accepts is 9,007,199,254,740,992 (2⁵³); above that a number can no longer be held exactly. If r = 1 the verdict is Probably prime; any other value is proof that n is Composite. Both n and the base a must be whole numbers, n must be at least 4, and a must lie between 2 and n − 2; otherwise there is no result. If the base is left empty it uses 2. The verdict “Probably prime” is not a proof: composite numbers that pass for a given base are called Fermat pseudoprimes, so a second base should be tried.

Worked example

Test n = 341 with base a = 2. The tool needs 2340 mod 341. Since 210 = 1024 = 3 × 341 + 1, we have 210 ≡ 1 (mod 341), so 2340 = (210)34 ≡ 1. The residue is 1 and the verdict is Probably prime. But 341 = 11 × 31 is composite: it is a pseudoprime to base 2. Run the same n with base 3 and the residue is 56, which gives Composite and exposes it.

Try this example →

Common mistakes

  • Taking Probably prime as a proof of primality. 341 passes with base 2 yet equals 11 × 31, so always repeat with several bases such as 2, 3, 5 and 7.
  • Trying n = 1, 2 or 3, or a base outside 2 to n − 2. The tool returns nothing for these, since the theorem needs a base in that range.
  • Choosing a base that shares a factor with n. For n = 561 the base 3 gives a residue of 375 and is rejected, while the base 5 gives 1; a failing base is conclusive, a passing one is not.
  • Entering a decimal or a number with thousands separators. n and a must be plain whole numbers.
  • Thinking Carmichael numbers like 561 are caught by trying more bases. Any base coprime to n passes for them, so a different test is needed.

About this calculator

Fermat's little theorem states that if n is a prime number, then for any integer base a not divisible by n, a^(n-1) ≡ 1 (mod n). This calculator runs that check in reverse: given a number n and a chosen base a, it computes a^(n-1) mod n — if the result isn't 1, n is definitely composite; if it is 1, n is only probably prime, since rare composite numbers (Fermat pseudoprimes, and the especially stubborn Carmichael numbers) can pass the test for many or even all bases.

Because it's fast to compute even for large numbers, the Fermat test is used as a cheap first-pass filter in cryptography and computer science education — quickly discarding obvious composites before running slower, more rigorous primality tests like Miller-Rabin, which underpins real-world RSA key generation. It's also a standard exercise in number theory courses for illustrating modular exponentiation and the difference between a necessary and a sufficient condition for primality.

Was this helpful?

You can pick up to 3 reactions.

Comments (1)

  • Editorial team

    A failed test is a certificate, a passed one is only a hint. Try 15 with the preset base 2: the residue is 4, not 1, which proves 15 is composite without finding any factor. Now try 17, the preset, where 2 to the 16th power leaves remainder 1. Teaching examples are a good fit for this tool. Which numbers do you test, and do you try several bases in a row?

Popular calculators

Loan Calculator

Monthly payment, total interest and full amortization schedule.

Percentage Calculator

Percent change, percent of, and ratio calculations.

Discount Calculator

Calculate final price, savings, and discount amount.

BMI Calculator

Body mass index from height and weight (metric or imperial).

Age Calculator

Compute your exact age in years, months and days from a birth date.

Compound Interest Calculator

Calculate the final amount and interest earned with compounding.

All Calculators