Fermat's Little Theorem Calculator

Introduction

Fermat's Little Theorem provides a foundational result in modular arithmetic, describing the behaviour of an integer $a$ when raised to powers relative to a prime modulus $p$ . Examining this relationship offers an efficient means of simplifying large exponential expressions, assessing primality conditions, and exploring structural properties within elementary number theory.

What this calculator does

Modular arithmetic is used by the calculator to determine the remainder of $a^{p - 1}$ divided by $p$ . It requires an integer base and a modulus as primary inputs. The output provides a comprehensive analysis including the modular result, primality status, greatest common divisor, Euler's totient value, Legendre symbol, modular inverse, and the multiplicative order of the element.

Formula used

The primary calculation is based on Fermat's Little Theorem, which states that for a prime $p$ and an integer $a$ not divisible by $p$ , the congruence holds. Secondary calculations include the Legendre symbol $(\frac{a}{p})$ for quadratic residues and the modular inverse using $a^{p - 2}$ .

a^{p - 1} \equiv 1 (\mod p)

a^{\frac{p - 1}{2}} \equiv (\frac{a}{p}) (\mod p)

How to use this calculator

1. Enter the integer base $a$ into the designated field.
2. Input the prime modulus $p$ for the calculation.
3. Select the preferred number of decimal places for the formatted output.
4. Execute the calculation to view the congruence relation and step-by-step verification.

Example calculation

Scenario: A student in a number theory course is verifying the properties of modular residues for an integer base against a small prime modulus to confirm Fermat's theorem.

Inputs: $a = 3$ and $p = 5$ .

Working:

Step 1: $\exp = p - 1$

Step 2: $\exp = 5 - 1 = 4$

Step 3: $3^{4} mod 5$

Step 4: $81 mod 5 = 1$

Result: 1.00

Interpretation: Since the result is 1, the integer 3 and prime 5 satisfy the conditions of the theorem.

Summary: The calculation successfully demonstrates the modular property of primes.

Understanding the result

The primary result reveals whether the congruence relation $a^{p - 1} \equiv 1$ is satisfied. A result of 1 suggests the modulus is likely prime and does not divide the base. Other values indicate the base is a multiple of the modulus or the modulus is composite.

Assumptions and limitations

The algorithm assumes that inputs are within the range of -1,000,000,000,000 to 1,000,000,000,000. It requires the modulus $p$ to be at least 2. Certain outputs like the multiplicative order are restricted to moduli below 10,000 for computational efficiency.

Common mistakes to avoid

Typical errors include entering a composite number for $p$ while expecting the theorem to hold, or using a base $a$ that is a multiple of $p$ , which results in a remainder of 0 rather than 1. Scientific notation must also be avoided as it is not supported.

Sensitivity and robustness

The calculation is stable for discrete integer inputs. However, the primality of $p$ is a critical pivot; if $p$ changes from prime to composite, the Legendre symbol and modular inverse calculations will automatically shift to "N/A" or alternative algorithms to maintain mathematical accuracy.

Troubleshooting

If an "Invalid input detected" error appears, ensure no special characters or angle brackets are present. If the modular inverse or order returns "N/A" or "Unknown", verify that the inputs meet the coprimality or primality constraints required for those specific number-theoretic properties.

Frequently asked questions

What happens if p is not prime?

The calculator identifies the modulus as composite and proceeds with modular exponentiation, but the specific properties of Fermat's Little Theorem may not apply.

What is the Legendre Symbol?

It is a function that indicates whether an integer is a quadratic residue modulo a prime, represented as 1, -1, or 0.

Why is the order unknown for large p?

To ensure performance, the iterative search for the multiplicative order is limited to moduli less than or equal to 10,000.

Where this calculation is used

In number theory and modular algebra, these calculations are fundamental for understanding the structure of cyclic groups and field theory. Academic applications include the study of primality testing, the distribution of power residues, and the simplification of complex congruences in mathematical modelling. It serves as a pedagogical tool for students to visualise how residues behave under exponentiation and to verify the foundations of discrete mathematics used in computational research and academic data analysis.

Results are based on standard mathematical and statistical methods and may involve rounding or approximation. If precise accuracy is required, please verify results independently. See full disclaimer.