Why do remainders reveal the GCD? Euclid from fractions to cryptography
Learn the Euclidean algorithm with gift bags and a step-by-step proof, then see how the GCD helps with square tiles, image ratios, fractions and RSA.

Mục lục
Suppose you have 210 sweets and 78 cookies to put into gift bags. Every bag must contain the same number of sweets and the same number of cookies, with nothing left over. Two bags are easy; three work too. But what is the largest possible number of bags, without trying every number in turn?
The answer is 6 bags, each containing 35 sweets and 13 cookies. The Euclidean algorithm for finding the greatest common divisor (GCD) reaches that number in just four divisions with remainder. The method is short: divide the larger number by the smaller, then divide the smaller number by the remainder. Keep going until a division leaves nothing over [1].
The gift bags are an illustrative example. The same calculation answers questions about cutting materials, tiling rectangles and simplifying image ratios. It also contributes a step in generating cryptographic keys. First, let us try it by hand.
Find the GCD by dividing what remains
The number of bags must divide both 210 and 78 exactly. Six bags meet that condition: 210 divided by 6 is 35, and 78 divided by 6 is 13. The greatest common divisor is simply the largest number that divides both original numbers without leftovers.
At school, you might factor both numbers into primes and find their shared factors. Euclid does not need that step. Start by dividing 210 by 78: two copies of 78 fit, leaving 54.
Remember: the quotient 2 is not the answer. Keep the divisor 78 and the remainder 54. These become the next pair to divide.
| Current pair | Division | Keep for the next step |
|---|---|---|
| 210 and 78 | 210 divided by 78 is 2, remainder 54 | 78 and 54 |
| 78 and 54 | 78 divided by 54 is 1, remainder 24 | 54 and 24 |
| 54 and 24 | 54 divided by 24 is 2, remainder 6 | 24 and 6 |
| 24 and 6 | 24 divided by 6 is 4, remainder 0 | Stop and take 6 |
In the final division, 6 divides 24 exactly, so the algorithm returns 6, the divisor in the line that leaves no remainder. The remainder 0 tells us the job is finished; it is not the answer. But carrying out the divisions is not enough: we must explain why 6 divides both original numbers and why no larger answer is possible.
To try another pair, use 48 and 18. Dividing 48 by 18 leaves 12; dividing 18 by 12 leaves 6; dividing 12 by 6 leaves nothing. The answer is again 6, without guessing any divisors in advance.
Mathematical proof: why is the Euclidean algorithm correct?
We need a proof for any two positive integers, not just a check of 210 and 78. Call them and , with . If the first number is smaller, swap them first; the common divisors do not change.
Dividing by gives:
Here is the integer quotient and the remainder. The equation restates ordinary division: dividend equals divisor times quotient, plus remainder. We must prove that replacing with preserves the GCD [1] [3].
Step 1: every common divisor of a and b also divides b and r
Take any positive common divisor of and . By the definition of divisibility, there are integers such that:
In other words, both and are times an integer. Rearrange the original division and substitute these expressions:
Since is an integer, the final expression shows that divides . It already divides , so it is a common divisor of and .
We chose arbitrarily, without assuming it is a particular number or already the greatest divisor. The conclusion therefore applies to every common divisor of the original pair.
Step 2: every common divisor of b and r also divides a and b
Conversely, take any positive common divisor of and . There are integers such that:
Substitute into :
Because is an integer, divides . Together with its divisibility of , this makes a common divisor of and .
Step 1 shows that the new pair loses none of the old common divisors. Step 2 shows that it gains no others. The two pairs have exactly the same set of positive common divisors, so the largest members of those sets are equal:
The notation means greatest common divisor. This reasoning also holds when : every positive integer divides 0, because .
Step 3: why does repeating the division preserve the GCD?
Call the original numbers . At step , divide by to obtain remainder , then set:
The index numbers the steps; is the original pair. Our result applies at every step, so:
After any number of completed steps, the GCD therefore still equals that of the original pair. We are not assuming the next step has the right answer; we have proved that moving between steps preserves all common divisors.
Step 4: why must the process stop?
The remainder condition gives:
Unless the process has stopped, is a positive integer at least 1 smaller than . Infinitely many steps cannot keep these divisors positive: there are only finitely many positive integers no greater than .
It follows that after finitely many steps, the second number must become 0. This proves that the algorithm always terminates, rather than merely observing that some test runs finish [3].
Step 5: why is the returned number the greatest common divisor?
At termination, the current pair is with . The number divides both and 0, since:
Every positive common divisor of and 0 must also divide . Thus for a positive integer , which implies . The number is therefore a common divisor with none greater than itself:
Since the GCD is preserved at every step, we conclude:
The algorithm therefore terminates and returns the correct GCD for every original pair of positive integers. In the table, is an application of this general result, not evidence replacing its proof.
Three familiar questions that use the same calculation
Gift bags: the largest number of identical portions
Return to the 210 sweets and 78 cookies. Six bags are the most we can make if every bag is identical and both kinds of food are used up. Four bags do not work because 78 cookies will not divide evenly by 4. Thirteen bags do not work either because the sweets would leave a remainder.
Fewer than six bags are possible, such as two or three. The GCD answers “the largest number”, not “the only way”. If bags need not be identical, or leftovers are allowed, we are asking a different question.
Square tiles: the largest size without cutting
Suppose a rectangular sheet measures 210 cm across and 78 cm high. We want to divide it into identical squares, arranged in rows and columns, without leftover edges. The largest square side is also 6 cm: 35 squares fit across and 13 fit vertically.
We can visualize the algorithm by placing large squares first. Two squares of side 78 cover most of the sheet, leaving a 54 × 78 rectangle. Next place one square of side 54, then two of side 24, and finally four of side 6.

Do not confuse the different squares in the picture with the final tile size. They are steps in the search. The answer is the side of the largest identical squares that can cover the entire sheet. Real floor tiling must also account for grout, available tile sizes and construction tolerances.
Two repeating rhythms: when do they meet again?
Suppose two lights flash together initially. The first flashes every 12 seconds, the second every 18 seconds. When do they next flash together?
The first flashes at seconds 12, 24 and 36. The second flashes at seconds 18 and 36. They meet again at second 36. This is the least common multiple, the earliest positive time containing a whole number of both cycles.
The GCD finds that time without listing every flash: multiply 12 by 18, then divide by their GCD. Since the GCD is 6, the result is 36 seconds [3]. A question about the “largest shared part” has helped solve a question about the “earliest meeting”.
Starting together is an important condition. If the lights are offset initially, we cannot apply the same calculation unchanged and conclude that they meet after 36 seconds. This example assumes regular rhythms with a shared starting point.
What do computers use the GCD for?
The examples above help us recognize the pattern. In software, the same need appears when reducing two numbers to a compact ratio, or working with calculations that keep only remainders.
Recognizing matching image proportions
What is the aspect ratio of an image 1,920 pixels wide and 1,080 pixels high? We could keep that pair of numbers, but 16:9 is easier to understand and compare. To find it, calculate the GCD of 1,920 and 1,080, which is 120, then divide both by 120.
An image-processing tool checking whether two sizes have matching proportions can reduce each pair first. A 1,280 × 720 frame also reduces to 16:9, while 1,080 × 1,080 reduces to 1:1. The program can then tell when resizing preserves the whole image and when cropping or borders will be needed.
This is one way to implement an aspect-ratio check, not a claim that every image application uses it. The GCD only simplifies the dimensions. It does not decide which crop looks good, nor does it sharpen the image.
Calculating fractions without immediately rounding to decimals
A calculation program can store 210/78 as two integers and reduce it to 35/13. It thereby preserves the exact fraction instead of replacing it with a rounded decimal.
This is an existing use in Python: its fractions library uses math.gcd to normalize the numerator and denominator [8]. After adding or multiplying fractions, reduction removes shared factors that need not be retained. It resembles simplifying a recipe from “two cups for four people” to “one cup for two people” without changing the ratio.
Not every calculation involving money or measurements should use fractions. The representation must suit the problem. This example simply shows that a calculation learned at school still performs a concrete job in a software library.
Generating cryptographic keys: finding multiplication that can be undone
On a 12-hour clock, adding 12 hours brings you back to the same position. Computers also use a similar kind of calculation: after multiplying, keep only the remainder upon division by a chosen number. This arithmetic on a circle is called modular arithmetic.
Take a circle with 43 positions. Multiplying by 17 and then by 38 returns every position to its starting point, provided we reduce modulo 43 after each multiplication. The reason is this small calculation: 17 × 38 = 646 = 15 × 43 + 1. Fifteen whole turns plus one step is equivalent to just one step.
The number 38 is an inverse, an operation that undoes multiplication by 17 on this particular circle. Euclid checks whether such an undo operation exists: 17 and 43 must have GCD 1. The extended version of Euclid also finds 38 itself by retaining additional information from the divisions [4] [5].
When generating RSA keys, the key generator needs the same kind of inverse to calculate a private exponent from information they have chosen [6]. The real numbers are much larger, but the need is still to find a suitable inverse operation. RSA and digital signatures in JWT continues the story of how a key pair signs and verifies messages.
Why is the method named after Euclid?
Around 300 BCE, Euclid’s work presented the greatest-common-measure method in the Elements [1] [3]. In the ancient presentation, the reader repeatedly subtracts the smaller number from the larger. Division with remainder bundles those subtractions into a single step.
This is not a new trick invented especially for computers. Computers reuse a way of organizing arithmetic that has existed for a long time. However, there is not enough evidence to describe a particular day when Euclid devised it; the method may have earlier origins [2] [3].
Euclid and the axiomatic method follows another idea from the same work: where mathematical reasoning begins. Here, the habit to remember is simply to handle the part that divides evenly, then continue with the remainder. The cover portrait is a later interpretation, not an authenticated likeness of Euclid [7].
Run Euclid yourself and draw the sheet
If you want to try it on a computer, the Python below performs the four divisions in the article and generates Figure 1. The GCD calculation is inside the while loop: divmod supplies the quotient and remainder, while a, b = b, r moves to the next pair. Everything else is for drawing.
You need matplotlib. Run the code from the directory where you want images/ to be created. The data are fixed; nothing is random. If programming is not your interest, skip this section: the examples above already explain how to use the algorithm by hand.
from pathlib import Pathfrom math import gcdimport matplotlibmatplotlib.use("Agg")import matplotlib.pyplot as pltfrom matplotlib.patches import Rectangle
def euclid(a, b): # Keep the divisor and remainder for the next step. a, b = abs(a), abs(b) steps = [] while b: q, r = divmod(a, b) steps.append((a, b, q, r)) a, b = b, r return a, steps
a, b = 210, 78result, steps = euclid(a, b)assert result == gcd(a, b) == 6for u, v, q, r in steps: print(f"{u} = {q} × {v} + {r}")print(f"GCD = {result}; divisions = {len(steps)}")
plt.rcParams.update({"font.family": "DejaVu Sans", "font.size": 12})fig, (ax, notes) = plt.subplots(1, 2, figsize=(12, 5.2), gridspec_kw={"width_ratios": [1.7, 1]})fig.patch.set_facecolor("#fcfcfb")x = y = 0w, h = a, bwhile w and h: side = min(w, h) ax.add_patch(Rectangle((x, y), side, side, facecolor="#dce7ed", edgecolor="#303c45", linewidth=1.4)) if side >= 24: ax.text(x + side / 2, y + side / 2, str(side), ha="center", va="center", color="#17242e", fontsize=14) if w >= h: x, w = x + side, w - side else: y, h = y + side, h - sideax.set(xlim=(-4, a + 4), ylim=(-4, b + 4), aspect="equal")ax.invert_yaxis()ax.axis("off")ax.set_title("Rectangle 210 × 78", color="#17242e", pad=18)notes.axis("off")notes.text(0, 0.85, "Each line is one division", color="#17242e", weight="bold")for i, (u, v, q, r) in enumerate(steps): notes.text(0, 0.69 - i * 0.14, f"{u} = {q} × {v} + {r}", color="#17242e")notes.text(0, 0.05, "Four smallest squares have side 6.\nGCD(210, 78) = 6.", color="#17242e", linespacing=1.8)fig.tight_layout(pad=2)output = Path("images/thuat-toan-euclid/lat-hinh-euclid-en.png")output.parent.mkdir(parents=True, exist_ok=True)fig.savefig(output, dpi=170, facecolor=fig.get_facecolor())plt.close(fig)Output:
210 = 2 × 78 + 5478 = 1 × 54 + 2454 = 2 × 24 + 624 = 4 × 6 + 0GCD = 6; divisions = 4An application needing only the result can call math.gcd directly. This illustrative function saves the divisions so we can see the process. The drawing is specifically for the positive sides 210 and 78; changing the picture means updating both dimensions and labels.
Return to the gift bags
Six gift bags, each containing 35 sweets and 13 cookies. The answer required no long list of trial divisions. We simply divided, kept the remainder and divided again.
Moving from gift bags to a rectangular sheet or an image ratio changes the task’s name. But the underlying question stays familiar: what is the largest shared divisor of these two numbers? The Euclidean algorithm answers with a short sequence of divisions, without needing to know all their factors beforehand.
Draw geometric illustrations free for students and teachers: EyeViz.
Tài liệu tham khảo
- [1]Euclid; English text and commentary by David E. Joyce. Elements, Book VII, Proposition 2. Clark University.
- [2]J. J. O’Connor and E. F. Robertson. Euclid of Alexandria. MacTutor History of Mathematics, University of St Andrews.
- [3]Euclidean algorithm for computing the greatest common divisor. CP-Algorithms.
- [4]Extended Euclidean Algorithm. CP-Algorithms.
- [5]Modular Multiplicative Inverse. CP-Algorithms.
- [6]RSA Algorithm. DI Management Services.
- [7]Portrait of Euclid, André Thevet. Wikimedia Commons.
- [8]fractions: Rational numbers. Python documentation.


