Skip to content
LoveToCalc

Theorem — what does that mean?

Greatest common divisor

The largest number that goes exactly into all of them. It is the number you simplify a fraction by.

In Swedish: Största gemensamma delare

gcd(a, b)=gcd(b, amodb)

a
First number
b
Second number

Practice questions

Work out

gcd(110, 66)

The rule

gcd(a, b) is the largest whole number that divides both a and b with no remainder. There are two ways to find it.

With prime factors. Factorise the numbers into primes and take the primes they share, each to the lowest power it appears with.

With Euclid’s algorithm. Divide the larger number by the smaller and keep the remainder. Then divide the smaller number by the remainder, and carry on. When the remainder is 0, the last remainder that was not 0 is the answer. The algorithm needs no factorising, so it also works on large numbers.

Worked examples

gcd(84, 360) with prime factors. 84 = 2² · 3 · 7 and 360 = 2³ · 3² · 5. Shared are 2 and 3. The lowest power of 2 is 2², of 3 it is 3¹. gcd = 2² · 3 = 12.

The same with Euclid.

The last remainder that was not 0 is 12.

Simplifying a fraction. 84/360: divide numerator and denominator by the gcd, 12, to get 7/30, which cannot be simplified further.

gcd and lcm together. For two numbers, gcd(a, b) · lcm(a, b) = a · b. Here 12 · 2520 = 30,240 = 84 · 360, so the least common multiple is 2520.

The GCD calculator works it out for several numbers and shows both methods.

Common mistakes

Common questions

What is the difference between the gcd and the lcm? The gcd is the largest number that goes into the numbers; it is at most as large as the smallest of them. The lcm is the smallest number the numbers go into; it is at least as large as the largest of them.

Why does Euclid’s algorithm work? A number that divides both a and b also divides the remainder when a is divided by b, because the remainder is a minus some number of b’s. The pairs (360, 84), (84, 24) and (24, 12) therefore have the same common divisors, and the last pair shows them directly.

How do you find the gcd of three numbers? Two at a time: gcd(a, b, c) = gcd(gcd(a, b), c). With prime factors, take the primes that appear in all three, to the lowest power.

Divisibility rules

Table

Divisibility rules
Divisible byRuleExampleCounterexample
2The last digit is even.124125
3The digit sum is divisible by 3.126127
4The last two digits form a number divisible by 4.168169
5The last digit is 0 or 5.210211
6The number is divisible by both 2 and 3.252253
8The last three digits form a number divisible by 8.336337
9The digit sum is divisible by 9.378379
10The last digit is 0.420421
11The digits alternately added and subtracted give a number divisible by 11.462463
25The last two digits are 00, 25, 50 or 75.1,0501,051

Last reviewed September 24, 2026 ·How pages are reviewed

Calculate it in practice

Ready-made worksheets with this formula

Sheets that ask this formula, with their answer keys. Open one to see the questions or print it.

Middle school

  • GCD and LCM

    Sixteen pairs of numbers: eight greatest common divisors and eight least common multiples. No calculator. The first one is worked.

ArithmeticAll formulas