Humanitext Reader

Euclid · Elements §7.prop.1-7.prop.2

Test for Coprime Numbers and the Euclidean Algorithm

Passage 111 of 316 · Greek

Summary

Euclid proves that if the Euclidean algorithm applied to two numbers leaves a unit as the last remainder, the numbers are prime to one another (Proposition 1), and presents the algorithm to find the greatest common measure of two numbers that are not prime to one another, along with its proof and a corollary (Proposition 2).

§7.prop.1δύο ἀριθμῶν ἀνίσων ἐκκειμένων, ἀνθυφαιρουμένου δὲ ἀεὶ τοῦ ἐλάσσονος ἀπὸ τοῦ μείζονος, ἐὰν ὁ λειπόμενος μηδέποτε καταμετρῇ τὸν πρὸ ἑαυτοῦ, ἕως οὗ λειφθῇ μονάς, οἱ ἐξ ἀρχῆς ἀριθμοὶ πρῶτοι πρὸς ἀλλήλους ἔσονται.
If two unequal numbers be set out, and the less be continually subtracted from the greater, if the remainder never measure the one before it until a unit is left, the original numbers will be prime to one another.
δύο γὰρ ἀριθμῶν τῶν ΑΒ, ΓΔ ἀνθυφαιρουμένου ἀεὶ τοῦ ἐλάσσονος ἀπὸ τοῦ μείζονος ὁ λειπόμενος μηδέποτε καταμετρείτω τὸν πρὸ ἑαυτοῦ, ἕως οὗ λειφθῇ μονάς· λέγω, ὅτι οἱ ΑΒ, ΓΔ πρῶτοι πρὸς ἀλλήλους εἰσίν, τουτέστιν ὅτι τοὺς ΑΒ, ΓΔ μονὰς μόνη μετρεῖ.
For, the less of two numbers AB, ΓΔ being continually subtracted from the greater, let the remainder never measure the one before it until a unit is left; I say that AB, ΓΔ are prime to one another, that is, that a unit alone measures AB, ΓΔ.
εἰ γὰρ μή εἰσιν οἱ ΑΒ, ΓΔ πρῶτοι πρὸς ἀλλήλους, μετρήσει τις αὐτοὺς ἀριθμός.
For, if AB, ΓΔ be not prime to one another, some number will measure them.
μετρείτω, καὶ ἔστω ὁ Ε·
Let it measure them, and let it be E; and let ΓΔ, measuring BZ, leave ZA less than itself, and let AZ, measuring ΔH, leave HΓ less than itself, and let HΓ, measuring ZΘ, leave a unit ΘA.
καὶ ὁ μὲν ΓΔ τὸν ΒΖ μετρῶν λειπέτω ἑαυτοῦ ἐλάσσονα τὸν ΖΑ, ὁ δὲ ΑΖ τὸν ΔΗ μετρῶν λειπέτω ἑαυτοῦ ἐλάσσονα τὸν ΗΓ, ὁ δὲ ΗΓ τὸν ΖΘ μετρῶν λειπέτω μονάδα τὴν ΘΑ. ἐπεὶ οὖν ὁ Ε τὸν ΓΔ μετρεῖ, ὁ δὲ ΓΔ τὸν ΒΖ μετρεῖ καὶ ὁ Ε ἄρα τὸν ΒΖ μετρεῖ·
Since then E measures ΓΔ, and ΓΔ measures BZ, E also measures BZ.
μετρεῖ δὲ καὶ ὅλον τὸν ΒΑ· καὶ λοιπὸν ἄρα τὸν ΑΖ μετρήσει.
But it also measures the whole BA; therefore it will also measure the remainder AZ.
ὁ δὲ ΑΖ τὸν ΔΗ μετρεῖ· καὶ ὁ Ε ἄρα τὸν ΔΗ μετρεῖ·
But AZ measures ΔH; therefore E also measures ΔH.
μετρεῖ δὲ καὶ ὅλον τὸν ΔΓ· καὶ λοιπὸν ἄρα τὸν ΓΗ μετρήσει.
But it also measures the whole ΔΓ; therefore it will also measure the remainder ΓH.
ὁ δὲ ΓΗ τὸν ΖΘ μετρεῖ· καὶ ὁ Ε ἄρα τὸν ΖΘ μετρεῖ·
But ΓH measures ZΘ; therefore E also measures ZΘ.
μετρεῖ δὲ καὶ ὅλον τὸν ΖΑ· καὶ λοιπὴν ἄρα τὴν ΑΘ μονάδα μετρήσει ἀριθμὸς ὤν· ὅπερ ἐστὶν ἀδύνατον.
But it also measures the whole ZA; therefore it will also measure the remaining unit AΘ, though it is a number; which is impossible.
οὐκ ἄρα τοὺς ΑΒ, ΓΔ ἀριθμοὺς μετρήσει τις ἀριθμός·
Therefore no number will measure the numbers AB, ΓΔ.
οἱ ΑΒ, ΓΔ ἄρα πρῶτοι πρὸς ἀλλήλους εἰσίν· ὅπερ ἔδει δεῖξαι.
Therefore AB, ΓΔ are prime to one another. (Which was) to be proved.
§7.prop.2δύο ἀριθμῶν δοθέντων μὴ πρώτων πρὸς ἀλλήλους τὸ μέγιστον αὐτῶν κοινὸν μέτρον εὑρεῖν.
Given two numbers not prime to one another, to find their greatest common measure.
ἔστωσαν οἱ δοθέντες δύο ἀριθμοὶ μὴ πρῶτοι πρὸς ἀλλήλους οἱ ΑΒ, ΓΔ. δεῖ δὴ τῶν ΑΒ, ΓΔ τὸ μέγιστον κοινὸν μέτρον εὑρεῖν.
Let the two given numbers not prime to one another be AB, ΓΔ. It is required then to find the greatest common measure of AB, ΓΔ.
εἰ μὲν οὖν ὁ ΓΔ τὸν ΑΒ μετρεῖ, μετρεῖ δὲ καὶ ἑαυτόν, ὁ ΓΔ ἄρα τῶν ΓΔ, ΑΒ κοινὸν μέτρον ἐστίν.
If now ΓΔ measures AB, and it also measures itself, ΓΔ is a common measure of ΓΔ, AB.
καὶ φανερόν, ὅτι καὶ μέγιστον· οὐδεὶς γὰρ μείζων τοῦ ΓΔ τὸν ΓΔ μετρήσει.
And it is manifest that it is also the greatest; for no number greater than ΓΔ will measure ΓΔ.
εἰ δὲ οὐ μετρεῖ ὁ ΓΔ τὸν ΑΒ, τῶν ΑΒ, ΓΔ ἀνθυφαιρουμένου ἀεὶ τοῦ ἐλάσσονος ἀπὸ τοῦ μείζονος λειφθήσεταί τις ἀριθμός, ὃς μετρήσει τὸν πρὸ ἑαυτοῦ.
But, if ΓΔ does not measure AB, then, the less of the numbers AB, ΓΔ being continually subtracted from the greater, some number will be left which will measure the one before it.
μονὰς μὲν γὰρ οὐ λειφθήσεται· εἰ δὲ μή, ἔσονται οἱ ΑΒ, ΓΔ πρῶτοι πρὸς ἀλλήλους· ὅπερ οὐχ ὑπόκειται.
For a unit will not be left; otherwise, AB, ΓΔ will be prime to one another, which is contrary to the hypothesis.
λειφθήσεταί τις ἄρα ἀριθμός, ὃς μετρήσει τὸν πρὸ ἑαυτοῦ.
Therefore some number will be left which will measure the one before it.
καὶ ὁ μὲν ΓΔ τὸν ΒΕ μετρῶν λειπέτω ἑαυτοῦ ἐλάσσονα τὸν ΕΑ, ὁ δὲ ΕΑ τὸν ΔΖ μετρῶν λειπέτω ἑαυτοῦ ἐλάσσονα τὸν ΖΓ, ὁ δὲ ΓΖ τὸν ΑΕ μετρείτω.
And let ΓΔ, measuring BE, leave EA less than itself; let EA, measuring ΔZ, leave ZΓ less than itself; and let ΓZ measure AE.
ἐπεὶ οὖν ὁ ΓΖ τὸν ΑΕ μετρεῖ, ὁ δὲ ΑΕ τὸν ΔΖ μετρεῖ, καὶ ὁ ΓΖ ἄρα τὸν ΔΖ μετρήσει·
Since then ΓZ measures AE, and AE measures ΔZ, ΓZ will also measure ΔZ.
μετρεῖ δὲ καὶ ἑαυτόν· καὶ ὅλον ἄρα τὸν ΓΔ μετρήσει.
But it also measures itself; therefore it will also measure the whole ΓΔ.
ὁ δὲ ΓΔ τὸν ΒΕ μετρεῖ· καὶ ὁ ΓΖ ἄρα τὸν ΒΕ μετρεῖ·
But ΓΔ measures BE; therefore ΓZ also measures BE.
μετρεῖ δὲ καὶ τὸν ΕΑ· καὶ ὅλον ἄρα τὸν ΒΑ μετρήσει·
But it also measures EA; therefore it will also measure the whole BA.
μετρεῖ δὲ καὶ τὸν ΓΔ· ὁ ΓΖ ἄρα τοὺς ΑΒ, ΓΔ μετρεῖ.
But it also measures ΓΔ; therefore ΓZ measures AB, ΓΔ.
ὁ ΓΖ ἄρα τῶν ΑΒ, ΓΔ κοινὸν μέτρον ἐστίν.
Therefore ΓZ is a common measure of AB, ΓΔ.
λέγω δή, ὅτι καὶ μέγιστον.
I say then that it is also the greatest.
εἰ γὰρ μή ἐστιν ὁ ΓΖ τῶν ΑΒ, ΓΔ μέγιστον κοινὸν μέτρον, μετρήσει τις τοὺς ΑΒ, ΓΔ ἀριθμοὺς ἀριθμὸς μείζων ὢν τοῦ ΓΖ. μετρείτω, καὶ ἔστω ὁ Η. καὶ ἐπεὶ ὁ Η τὸν ΓΔ μετρεῖ, ὁ δὲ ΓΔ τὸν ΒΕ μετρεῖ, καὶ ὁ Η ἄρα τὸν ΒΕ μετρεῖ·
For, if ΓZ is not the greatest common measure of AB, ΓΔ, some number which is greater than ΓZ will measure the numbers AB, ΓΔ.
μετρεῖ δὲ καὶ ὅλον τὸν ΒΑ·
Let it measure them, and let it be H. And since H measures ΓΔ, and ΓΔ measures BE, H also measures BE.
καὶ λοιπὸν ἄρα τὸν ΑΕ μετρήσει.
But it also measures the whole BA; therefore it will also measure the remainder AE.
ὁ δὲ ΑΕ τὸν ΔΖ μετρεῖ· καὶ ὁ Η ἄρα τὸν ΔΖ μετρήσει·
But AE measures ΔZ; therefore H will also measure ΔZ.
μετρεῖ δὲ καὶ ὅλον τὸν ΔΓ· καὶ λοιπὸν ἄρα τὸν ΓΖ μετρήσει ὁ μείζων τὸν ἐλάσσονα· ὅπερ ἐστὶν ἀδύνατον·
But it also measures the whole ΔΓ; therefore it will also measure the remainder ΓZ, the greater measuring the less; which is impossible.
οὐκ ἄρα τοὺς ΑΒ, ΓΔ ἀριθμοὺς ἀριθμός τις μετρήσει μείζων ὢν τοῦ ΓΖ· ὁ ΓΖ ἄρα τῶν ΑΒ, ΓΔ μέγιστόν ἐστι κοινὸν μέτρον· .
Therefore no number which is greater than ΓZ will measure the numbers AB, ΓΔ; therefore ΓZ is the greatest common measure of AB, ΓΔ.
Πόρισμα ἐκ δὴ τούτου φανερόν, ὅτι ἐὰν ἀριθμὸς δύο ἀριθμοὺς μετρῇ, καὶ τὸ μέγιστον αὐτῶν κοινὸν μέτρον μετρήσει· ὅπερ ἔδει δεῖξαι.
Corollary From this it is manifest that, if a number measure two numbers, it will also measure their greatest common measure. (Which was) to be proved.

Notes

  1. §7.prop.1δύο ἀριθμῶν ἀνίσων ἐκκειμένων, ἀνθυφαιρουμένου δὲ ἀεὶ τοῦ ἐλάσσονος ἀπὸ τοῦ μείζονος — Two consecutive genitive absolute clauses setting out the hypothesis and the process. The participles ἐκκειμένων and ἀνθυφαιρουμένου introduce the initial condition and the mathematical procedure (continual subtraction, i.e., the Euclidean algorithm).
  2. §7.prop.1ἕως οὗ λειφθῇ μονάς — The temporal conjunction ἕως οὗ ('until') is used here with the subjunctive λειφθῇ (aorist passive of λείπω) without the particle ἄν to express an expected limit. This construction is highly typical of Hellenistic prose and mathematical texts.
  3. §7.prop.1μηδέποτε καταμετρείτω τὸν πρὸ ἑαυτοῦ — The third-person singular present imperative καταμετρείτω ('let it never measure') is employed here. In Euclidean proofs, the imperative is standardly used to set up hypothetical conditions or mathematical constructions for the sake of argument.
  4. §7.prop.2τὸ μέγιστον αὐτῶν κοινὸν μέτρον εὑρεῖν — The infinitive εὑρεῖν ('to find') is used independently as a title or statement of a mathematical problem (as opposed to a theorem, which typically uses the future indicative like ἔσονται). This is the standard formula for problems in Euclid's Elements.

Cite this passage

Euclid, Elements §7.prop.1-7.prop.2. Humanitext Reader, https://reader.humanitext.ai/en/text/urn:cts:greekLit:tlg1799.tlg001.humanitext-grc2:7.prop.1-7.prop.2

Please note the AI-draft status of the translation and the date accessed.

Translation, notes and summary are AI-generated drafts, revised through reader feedback.