Mathematics · Number Theory
Number Theory Divisibility Calculator
Determines whether one integer divides another and computes quotient, remainder, GCD, and LCM using fundamental number theory principles.
Calculator
Formula
In the division algorithm, a is the dividend, b is the divisor, q is the integer quotient, and r is the non-negative remainder. When r = 0, b divides a exactly (written b | a). The GCD is computed recursively via the Euclidean algorithm until the remainder reaches zero. The LCM is derived from the identity relating the product of two integers to the product of their GCD and LCM.
Source: Hardy & Wright, An Introduction to the Theory of Numbers, 6th ed., Oxford University Press (2008); Euclid's Elements, Book VII.
How it works
Divisibility is one of the oldest concepts in mathematics. We say an integer b divides an integer a — written b | a — if there exists an integer k such that a = k·b, leaving no remainder. The Division Algorithm guarantees that for any integers a and b (b ≠ 0), there exist unique integers q (quotient) and r (remainder) satisfying a = q·b + r with 0 ≤ r < |b|. This uniqueness is what makes integer arithmetic so predictable and useful in theoretical and applied contexts.
The Greatest Common Divisor (GCD) of two integers a and b is the largest positive integer that divides both without remainder. The most efficient method for computing the GCD is the Euclidean Algorithm, which repeatedly replaces the larger number with the remainder of dividing the pair: gcd(a, b) = gcd(b, a mod b), terminating when the remainder is zero. The Least Common Multiple (LCM) is then obtained via the identity lcm(a, b) = |a·b| / gcd(a, b), which avoids the need for prime factorisation. Both GCD and LCM are symmetric: gcd(a, b) = gcd(b, a) and lcm(a, b) = lcm(b, a).
Practical applications are extensive. In fraction arithmetic, the GCD is used to reduce a fraction a/b to its lowest terms by dividing numerator and denominator by gcd(a, b). The LCM determines the common denominator when adding fractions with different denominators. In scheduling and signal processing, the LCM of two cycle lengths gives the period after which both cycles repeat simultaneously. In cryptography, algorithms such as RSA rely directly on properties of divisibility, modular arithmetic, and the GCD — specifically the extended Euclidean algorithm for computing modular inverses. Computer scientists use the modulo operation (remainder) in hash table indexing, circular buffer management, and checksum algorithms.
Worked example
Suppose you want to analyse the relationship between a = 360 and b = 24.
Step 1 — Division Algorithm: Divide 360 by 24. q = floor(360 / 24) = 15, r = 360 − 15 × 24 = 360 − 360 = 0. Since r = 0, we confirm that 24 | 360 exactly.
Step 2 — GCD via Euclidean Algorithm:
gcd(360, 24): 360 = 15 × 24 + 0. The remainder is immediately 0, so gcd(360, 24) = 24. This makes sense because 24 is itself a divisor of 360.
Step 3 — LCM: lcm(360, 24) = |360 × 24| / gcd(360, 24) = 8640 / 24 = 360. Again intuitive — since 24 divides 360, the smallest multiple common to both is simply 360 itself.
A second example with a non-zero remainder: Let a = 250 and b = 36.
q = floor(250 / 36) = 6, r = 250 − 6 × 36 = 250 − 216 = 34. Since r ≠ 0, 36 does not divide 250.
GCD: gcd(250, 36) → gcd(36, 250 mod 36 = 34) → gcd(34, 2) → gcd(2, 0) = 2.
LCM: |250 × 36| / 2 = 9000 / 2 = 4500.
Limitations & notes
This calculator operates on integers; inputting decimal (non-integer) values will produce mathematically undefined results since divisibility is defined only over the integers. Very large integers may be subject to JavaScript's floating-point precision limits (safe integer range is ±2^53 − 1 = 9,007,199,254,740,991); for cryptographic-scale integers (hundreds of digits), specialised big-integer libraries are required. Division by zero (b = 0) is undefined — the calculator will return NaN or Infinity for quotient and LCM in that case. The remainder output follows the mathematical convention (always non-negative), which may differ from the sign convention used in some programming languages (e.g., C and Java return a remainder with the same sign as the dividend for negative inputs). The LCM of zero and any integer is defined as zero by convention, but this edge case has limited practical significance.
Frequently asked questions
What does it mean for b to divide a in number theory?
We say b divides a (written b | a) if there is an integer k such that a = k·b, meaning the division leaves no remainder. For example, 6 divides 42 because 42 = 7 × 6 with remainder 0. If any non-zero remainder exists, b does not divide a.
What is the Euclidean algorithm and why is it used for GCD?
The Euclidean algorithm is an ancient, highly efficient method that computes the GCD by repeatedly taking remainders: gcd(a, b) = gcd(b, a mod b) until the remainder is zero, at which point the last non-zero value is the GCD. It runs in O(log(min(a, b))) steps, making it far faster than factorisation for large numbers and the backbone of many cryptographic routines.
How are GCD and LCM related to each other?
For any two positive integers a and b, the product of their GCD and LCM equals the product of the numbers: gcd(a, b) × lcm(a, b) = a × b. This identity makes it easy to compute one from the other once the GCD is known, avoiding the need for independent prime factorisation of both numbers.
What are common divisibility rules I should know?
Some widely used divisibility rules include: a number is divisible by 2 if its last digit is even; by 3 if the sum of its digits is divisible by 3; by 5 if it ends in 0 or 5; by 9 if the digit sum is divisible by 9; and by 11 if the alternating digit sum is divisible by 11. These shortcuts derive from properties of the decimal (base-10) number system.
Where is divisibility theory used in computer science and cryptography?
Divisibility is central to RSA encryption, where the security of the algorithm relies on the difficulty of factoring a large semiprime (product of two primes) and on computing modular inverses using the extended Euclidean algorithm. In programming, the modulo operator is used for hash table indexing, cyclic iteration, calendar computations, checksums, and random number generation. The LCM is used for scheduling repeating tasks and computing LCD in rational arithmetic libraries.
Last updated: 2025-01-15 · Formula verified against primary sources.