Home›Mathematics›Prime Factorization Calculator
🔢

Prime Factorization & Number Theory

Factorize any number into primes, check primality with Miller-Rabin test, calculate GCD and LCM, find Euler's totient, list prime numbers in a range and perform modular arithmetic.

Up to 10¹²GCD, LCM & More
Prime Factorization
Primality Test
GCD & LCM
Primes in Range
Modular Arithmetic
a mod m
Modular Inverse: a⁻¹ mod m
Modular Exponentiation: aᵉ mod m
Chinese Remainder Theorem: x ≡ a₁ (mod m₁) and x ≡ a₂ (mod m₂)

What is Prime Factorization?

Prime factorization is the process of expressing a positive integer as a product of its prime factors. Every composite number can be broken down into prime numbers that multiply together to give the original number. For example, 360 = 2³ × 3² × 5.

To find the prime factorization of a number n, we repeatedly divide by the smallest prime factor (starting from 2) until the quotient is 1. The collection of all prime divisors (with their multiplicities) is the prime factorization.

The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states that every integer greater than 1 either is itself a prime, or can be represented as a product of prime numbers, and that this representation is unique up to the order of the factors. This uniqueness makes prime factorization a cornerstone of number theory.

Euler's Totient Function φ(n)

Euler's totient function φ(n) counts the number of positive integers up to n that are relatively prime to n (i.e., GCD(k, n) = 1 for 1 ≤ k ≤ n). It is a fundamental function in number theory with deep connections to RSA cryptography.

For n = p₁^e₁ × p₂^e₂ × … × pₖ^eₖ: φ(n) = n × ∏(1 − 1/pᵢ)

nCoprime integersφ(n)
1{1}1
2{1}1
3{1, 2}2
4{1, 3}2
5{1, 2, 3, 4}4
6{1, 5}2
7{1, 2, 3, 4, 5, 6}6
8{1, 3, 5, 7}4
9{1, 2, 4, 5, 7, 8}6
10{1, 3, 7, 9}4
11{1,2,3,4,5,6,7,8,9,10}10
12{1, 5, 7, 11}4

Frequently Asked Questions

This calculator handles numbers up to 10¹² (one trillion) using trial division up to the square root, which is fast enough for client-side computation. For primality checking (not full factorization), the Miller-Rabin test with deterministic witnesses handles numbers up to about 3.3 × 10²⁴ accurately.
The Greatest Common Divisor (GCD) is used to simplify fractions, find common denominators, solve linear Diophantine equations, and in cryptography (RSA algorithm). If GCD(a,b)=1 the numbers are called coprime, which is a key property in modular arithmetic.
Euler's totient function φ(n) counts how many integers from 1 to n are coprime to n. For a prime p, φ(p) = p−1. It is central to Euler's theorem: a^φ(n) ≡ 1 (mod n) when GCD(a,n)=1, which underpins the RSA encryption algorithm.
Modular arithmetic works with remainders after division. 'a mod m' is the remainder when a is divided by m. For example, 17 mod 5 = 2. It is used in cryptography, computer science (hash functions, checksums), calendar calculations, and number theory. The modular inverse a⁻¹ mod m exists when GCD(a,m)=1.