Prime Factorization and Number Theory, Explained
After reading this you will be able to break an integer into its prime factors, count its divisors, find the greatest common divisor and least common multiple of a list, and compute modular inverses and modular powers by hand or with a check.
What this calculator does
Number theory studies the integers and the relationships between them. This page handles three tasks that come up constantly: factoring a number into primes, finding the GCD and LCM of several numbers, and doing arithmetic modulo m.
Here is a single example that ties it together. Take 360. Its prime factorization is 360 = 2^3 \cdot 3^2 \cdot 5. From that one line you can read off almost everything: 360 has 24 divisors, the sum of those divisors is 1170, and Euler's totient \varphi(360) = 96. You do not need to test each divisor separately. The prime factorization is the compact code that generates the rest.
When to use it, and when not
Reach for prime factorization when you need the internal structure of a number: reducing a fraction, finding a common denominator, counting divisors, or checking whether one number divides another. Use GCD and LCM when you combine several numbers, for instance syncing two repeating events or simplifying \frac{84}{120}.
Use modular arithmetic when only the remainder matters: clock arithmetic, check digits, hashing, and the core steps of RSA and Diffie-Hellman key exchange.
Trial-division factoring is fast for numbers up to roughly 15 digits but slows sharply beyond that. A 30-digit semiprime (a product of two large primes) can be out of reach here. That difficulty is exactly what public-key cryptography relies on, so do not treat this page as a way to break real keys.
The formulas and the intuition
The starting point is the fundamental theorem of arithmetic: every integer greater than 1 has exactly one prime factorization, apart from the order of the factors. Write it as
Here each p_i is a distinct prime and each exponent a_i is at least 1. From this form three quantities follow directly.
The number of divisors counts every choice of exponent from 0 up to a_i for each prime:
The sum of divisors uses the geometric series for each prime:
Euler's totient counts the integers from 1 to n that share no factor with n:
For GCD and LCM the primes explain everything too. The GCD takes the smallest exponent of each shared prime; the LCM takes the largest exponent across all primes. A useful identity for two numbers is
In modular arithmetic the modular inverse of a is the number x with a x \equiv 1 \pmod{m}. It exists exactly when \gcd(a,m) = 1. The extended Euclidean algorithm finds it. Fast modular exponentiation computes a^b \bmod m by squaring, so even 17^{1000} takes only about 10 multiplications instead of 1000.
A worked example with 360
Factoring 360 and reading its properties
This reproduces the demo: mode set to prime factorization with n = 360.
- Divide by 2 repeatedly:
360 / 2 = 180,180 / 2 = 90,90 / 2 = 45. That is three factors of 2, so 2^3. - 45 is odd. Divide by 3:
45 / 3 = 15,15 / 3 = 5. Two factors of 3, so 3^2. - 5 is prime and stops there, giving 5^1.
- So 360 = 2^3 \cdot 3^2 \cdot 5.
- Divisor count: (3+1)(2+1)(1+1) = 4 \cdot 3 \cdot 2 = 24.
- Sum of divisors: \frac{2^4-1}{1} \cdot \frac{3^3-1}{2} \cdot \frac{5^2-1}{4} = 15 \cdot 13 \cdot 6 = 1170.
- Totient: 360 \cdot \frac{1}{2} \cdot \frac{2}{3} \cdot \frac{4}{5} = 96.
Every number on the results panel comes from that one factorization. Change the exponent on any prime and watch all three quantities shift.
GCD and LCM of a list
Switch mode to GCD and LCM and enter several numbers. Take 84, 120 and 360.
| Number | 2 | 3 | 5 | 7 |
|---|---|---|---|---|
| 84 | 2 | 1 | 0 | 1 |
| 120 | 3 | 1 | 1 | 0 |
| 360 | 3 | 2 | 1 | 0 |
For the GCD take the smallest exponent in each column: 2^2 \cdot 3^1 = 12. For the LCM take the largest exponent in each column: 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520. Note that 7 appears in the LCM because it appears in at least one number, but it is absent from the GCD because 120 and 360 have no factor of 7.
For a fraction like \frac{84}{120}, dividing top and bottom by \gcd(84,120) = 12 gives \frac{7}{10} in lowest terms.
Modular arithmetic in practice
Set mode to modular arithmetic. The default operation is a \bmod m, which returns the remainder. With a = 17 and m = 43 the answer is 17, since 17 is already less than 43.
The modular inverse answers: which x satisfies 17 x \equiv 1 \pmod{43}? Because \gcd(17,43) = 1, an inverse exists. It is 38, and you can check that 17 \cdot 38 = 646 = 15 \cdot 43 + 1, so 646 \equiv 1 \pmod{43}.
The modular power uses the default a = 17, b = 1000, m = 43. Since 43 is prime and 17 is not a multiple of 43, Fermat's little theorem says 17^{42} \equiv 1 \pmod{43}. Reduce the exponent: 1000 = 23 \cdot 42 + 34, so 17^{1000} \equiv 17^{34} \pmod{43}. The calculator squares its way there and returns 18.
To check a modular power by hand, reduce the exponent modulo \varphi(m) first when \gcd(a,m) = 1. For prime m, \varphi(m) = m - 1, so here you replace 1000 with 34 before computing. That turns a large exponent into a small one.
17^b mod 43 stay inside the range 0 to 42 and repeat with a fixed period. Large exponents never produce large answers.Common mistakes
Treating 1 as prime. The number 1 has no prime factors, and 1 is neither prime nor composite. The factorization of 1 is the empty product.
Assuming an inverse always exists. There is no inverse of 6 modulo 9 because \gcd(6,9) = 3 \ne 1. If the calculator reports no inverse, the two numbers share a factor.
Reducing exponents with the wrong modulus. You reduce the base by m, but you reduce the exponent by \varphi(m), not by m. Mixing these gives wrong answers.
Sign confusion in remainders. Mathematical convention keeps a \bmod m in the range 0 to m-1, so -7 \bmod 5 = 3, not -2. Some programming languages differ, so verify which convention your source uses.
Related tools
Once you have a factorization, several neighboring calculators pick up the thread. Use the Fraction to decimal converter to reduce fractions and see repeating decimals. For arithmetic with numbers far larger than this page factors comfortably, the Big number calculator keeps every digit exact. To view your integers in binary or hexadecimal, try the Number base converter. If you are counting arrangements rather than divisors, the Combinatorics calculator handles \binom{n}{r} and related counts.
Frequently asked questions
How do I find the number of divisors without listing them?
Factor the number, add 1 to each exponent, and multiply. For 360 = 2^3 \cdot 3^2 \cdot 5 that is 4 \cdot 3 \cdot 2 = 24 divisors.
Why does the modular inverse sometimes fail?
An inverse of a modulo m exists only when \gcd(a,m) = 1. For example, 4 has no inverse modulo 6 because both share the factor 2.
What is the largest number this can factor?
Numbers up to about 15 digits factor quickly. Beyond that, a number that is the product of two large primes may not finish in reasonable time, which is by design in cryptography.
How are GCD and LCM related?
For two numbers, \gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b. With 84 and 120, \gcd = 12 and \operatorname{lcm} = 840, and 12 \cdot 840 = 10080 = 84 \cdot 120.
What does Euler's totient count?
It counts integers from 1 to n that are coprime to n. For 360 the answer is 96, so 96 of the numbers from 1 to 360 share no factor with 360.
Related tools
Inverse Symbolic Calculator
Paste a decimal, get its closed form: 1.6449340668 → π²/6. Also names integer sequences.
Number Base Converter
Binary, octal, decimal, hex and any base from 2 to 36.
Scientific Notation & Significant Figures
Convert to scientific and engineering notation, round to sig figs.
Big Number Calculator
Exact arithmetic with thousands of digits: +, −, ×, ÷, ^, fact().
Fraction ↔ Decimal ↔ Continued Fraction
Exact conversions with repeating decimals and convergents.
Roman Numeral Converter
Numbers to Roman numerals and back, with validation.