Intuition The one core ideaEvery whole number is built by multiplying smaller whole numbers together, and the HCF asks: what is the biggest single number hiding inside BOTH of two numbers at once? Everything on the parent page — prime factors, the "min exponent" rule, Euclid's swapping trick — is just two different ways to hunt down that shared building block.
This page assumes you have seen nothing . We will define every symbol the parent note throws at you, anchor each to a picture, and say why the topic can't live without it . Read top to bottom — each idea leans on the one above it.
Definition Natural numbers and integersA natural number is a counting number: 1 , 2 , 3 , 4 , … integer adds zero and the negatives: … , − 2 , − 1 , 0 , 1 , 2 , … n
Look at the figure: the row of dots IS the number. When we later say "12 splitting rows of dots into equal groups — you can only understand "divides evenly" if you can see the dots.
⋅ a ⋅ b a b a × b ⋅ x rectangle of dots, a b
The rectangle picture is the secret hero of this whole chapter. A number that can be drawn as a non-trivial rectangle (more than one row AND more than one column) is made of smaller pieces . That is exactly what "divides" will mean next.
d n d ∣ n n complete rows of d with none left over . Formally: n = d ⋅ k k ∣ not confuse it with a fraction line — 6 ∣ 12 true/false statement , while 12 6 number .
Intuition Why the topic needs "divides"HCF is defined as the biggest number that divides both . If you can't picture "d n 4 ∣ 12 5 ∣ 12 remainder .
Definition Division with remainderWhen d not divide n n = d ⋅ q + r , 0 ≤ r < d . q quotient ) is how many full rows fit, and r remainder ) is the leftover dots — always smaller than d , because if it were ≥ d
17 = 5 ⋅ 3 + 2 5 3 q = 3 15 2 r = 2 5 ⋅ 3 + 2 = 17 d ∣ n r = 0
Why the topic needs this: Euclid's whole algorithm is built on the line a = b q + r
A prime is a natural number bigger than 1 only rectangle is the boring 1 × n cannot be drawn as a fatter rectangle. Examples: 2 , 3 , 5 , 7 , 11 , … composite number (like 12 can be drawn as a fatter rectangle, so it splits into smaller factors.
Intuition Why primes are the "atoms"Every whole number is a product of primes and nothing smaller — primes are the un-splittable building blocks. This is the promise of the Fundamental Theorem of Arithmetic : the factorization is unique . Method 1 of the parent note lines up these atoms and keeps only the shared ones. See Prime Numbers & Factorization for the hunting techniques.
Definition Exponent notationp α p α 2 3 = 2 ⋅ 2 ⋅ 2 = 8 p base (which prime) and α alpha , just a name for a number) is the exponent (how many copies).
Picture: a tower of that prime, α
p 0 = 1 1 1
Why the topic needs this: the parent writes 360 = 2 3 ⋅ 3 2 ⋅ 5 1 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ 3 ⋅ 5 p 0 same list of primes (a missing prime just gets exponent 0
∏ i ∏ pi ) is a loop that multiplies . ∏ i p i α i 1 2 i counter — "for each prime, indexed by i ∏
∏ ∏ i p i α i 2 , 3 , 5 3 , 2 , 1 2 3 ⋅ 3 2 ⋅ 5 1 = 8 ⋅ 9 ⋅ 5 = 360
Why the topic needs it: it's the compact way to write "the product of shared primes to their minimum exponents". Nothing scary — it's a for-each-prime, multiply instruction.
min max min ( α , β ) smaller of the two numbers. max ( α , β ) larger .
(β beta , another Greek name-for-a-number.) Picture: two towers side by side — min max
min shorter of the two prime-towers — because it must fit inside both numbers. Take one block more and it no longer divides the shorter one. So HCF grabs the shortest tower of every shared prime: min LCM — Least Common Multiple , grabs the tallest: max
g cd( a , b ) g cd( a , b ) Greatest Common Divisor of a b HCF (Highest Common Factor) is the exact same thing — two names, one idea.
Convention: g cd( a , 0 ) = a everything divides 0 0 a
If g cd( a , b ) = 1 no prime atoms — they are called coprime (or relatively prime). Picture: two towers with no floor in common.
These feed directly into Reducing Fractions to Lowest Terms (divide top and bottom by their g cdModular Arithmetic & RSA (which needs coprime numbers).
■ done — proven ". It's punctuation, not maths. When you see it in the parent note, the reasoning above it is complete.
Whole numbers as dot rows
Divides d mid n, remainder 0
Multiplication as rectangles
Remainder r and quotient q
HCF by prime factorization
Euclidean algorithm a = bq + r
Read it as: dots and rectangles let you define "divides"; "divides" plus leftovers gives remainder — the fuel for Euclid. Rectangles also give primes; primes plus exponents plus min give Method 1. Both roads arrive at g cd
Test yourself — cover the right side and answer before revealing.
What does d ∣ n n d zero left over; i.e. n = d ⋅ k
In n = d q + r q r r q r 0 ≤ r < d
What makes a number prime , as a rectangle? Its only rectangle is the 1 × n
What does 2 3 2 ⋅ 2 ⋅ 2 = 8 2
What is p 0 1
What does ∏ i p i α i For each prime in the list, raise it to its exponent, then multiply them all together.
Does HCF use min max min
What does g cd( a , 0 ) a 0 a
Two numbers with g cd= 1 Coprime (relatively prime) — no shared prime atoms.
