Number Theory Calculator

Number Theory Explained

Number theory studies whole numbers and the relationships between them — this calculator covers three foundational tools: breaking a number into its prime building blocks, testing primality, and efficiently computing huge modular powers.

Prime factorization writes a number as a product of primes: $$n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$$

Modular exponentiation computes $b^e \bmod n$ efficiently using square-and-multiply, repeatedly squaring the base and reducing modulo $n$ at every step rather than computing the full power first.

Worked Example: Fermat's Little Theorem Check

Using the modular exponentiation mode's defaults — base 7, exponent 560, modulus 561 — the result comes out to 1. This is a deliberately chosen example: 561 is the smallest Carmichael number, a composite number that still satisfies Fermat's little theorem-like behavior for many bases, which is exactly why naive Fermat primality testing can be fooled by numbers like it (real primality tests use more robust methods, like Miller-Rabin, specifically to catch these edge cases).

Why Prime Factorization Underlies Modern Cryptography

RSA encryption, one of the most widely deployed public-key cryptographic systems, relies directly on the practical difficulty of factoring the product of two large prime numbers, even though multiplying those two primes together is trivial. This asymmetry — easy to multiply, hard to un-multiply — is the entire security foundation of RSA, and it's why finding faster factorization algorithms (or building a sufficiently powerful quantum computer, which could factor efficiently via Shor's algorithm) remains a subject of serious ongoing research.

A Brief History of Number Theory

Euclid's Elements (circa 300 BCE) contains some of the earliest recorded results in number theory, including a proof that there are infinitely many primes. Pierre de Fermat's 17th-century work on number properties (including his famously unproven "last theorem," not resolved until Andrew Wiles's 1994 proof) established number theory as a serious mathematical discipline. The field's practical importance exploded in the late 20th century once RSA (1977) and related cryptographic systems built modern digital security directly on top of number-theoretic hardness assumptions.

Common Number Theory Mistakes

Assuming a number is prime just because it passes a quick divisibility check by a few small primes is a common error — genuine primality testing must rule out every possible factor up to the square root (or use a rigorous probabilistic test for very large numbers). Confusing the security of RSA-style cryptography with the impossibility of factoring (it's merely impractically slow with current classical methods, not mathematically impossible) is another frequent misconception. Forgetting to reduce modulo n at each intermediate step in a hand-calculation of modular exponentiation — instead computing the full power first — is a third common mistake, and one this calculator's algorithm specifically avoids.

Number Theory Terms You Should Know

Prime Number — a whole number greater than 1 with no divisors other than 1 and itself.

Prime Factorization — expressing a number as a product of its prime factors.

Modular Arithmetic — arithmetic performed with numbers that "wrap around" after reaching a modulus.

Carmichael Number — a composite number that can fool simple Fermat-based primality tests for many bases.

This calculator uses trial division for factorization and primality testing, which is exact but can be slow for very large numbers with large prime factors; it uses BigInt arithmetic for exact large-integer modular exponentiation.