Fundamentals of number theory: Book 7 Proposition 34
Translations
Δύο ἀριθμῶν δοθέντων εὑρεῖν, ὃν ἐλάχιστον μετροῦσιν ἀριθμόν. Ἔστωσαν οἱ δοθέντες δύο ἀριθμοὶ οἱ Α, Β: δεῖ δὴ εὑρεῖν, ὃν ἐλάχιστον μετροῦσιν ἀριθμόν. Οἱ Α, Β γὰρ ἤτοι πρῶτοι πρὸς ἀλλήλους εἰσὶν ἢ οὔ. ἔστωσαν πρότερον οἱ Α, Β πρῶτοι πρὸς ἀλλήλους, καὶ ὁ Α τὸν Β πολλαπλασιάσας τὸν Γ ποιείτω: καὶ ὁ Β ἄρα τὸν Α πολλαπλασιάσας τὸν Γ πεποίηκεν. οἱ Α, Β ἄρα τὸν Γ μετροῦσιν. λέγω δή, ὅτι καὶ ἐλάχιστον. εἰ γὰρ μή, μετρήσουσί τινα ἀριθμὸν οἱ Α, Β ἐλάσσονα ὄντα τοῦ Γ. μετρείτωσαν τὸν Δ. καὶ ὁσάκις ὁ Α τὸν Δ μετρεῖ, τοσαῦται μονάδες ἔστωσαν ἐν τῷ Ε, ὁσάκις δὲ ὁ Β τὸν Δ μετρεῖ, τοσαῦται μονάδες ἔστωσαν ἐν τῷ Ζ: ὁ μὲν Α ἄρα τὸν Ε πολλαπλασιάσας τὸν Δ πεποίηκεν, ὁ δὲ Β τὸν Ζ πολλαπλασιάσας τὸν Δ πεποίηκεν: ἴσος ἄρα ἐστὶν ὁ ἐκ τῶν Α, Ε τῷ ἐκ τῶν Β, Ζ. ἔστιν ἄρα ὡς ὁ Α πρὸς τὸν Β, οὕτως ὁ Ζ πρὸς τὸν Ε. οἱ δὲ Α, Β πρῶτοι, οἱ δὲ πρῶτοι καὶ ἐλάχιστοι, οἱ δὲ ἐλάχιστοι μετροῦσι τοὺς τὸν αὐτὸν λόγον ἔχοντας ἰσάκις ὅ τε μείζων τὸν μείζονα καὶ ὁ ἐλάσσων τὸν ἐλάσσονα: ὁ Β ἄρα τὸν Ε μετρεῖ, ὡς ἑπόμενος ἑπόμενον. καὶ ἐπεὶ ὁ Α τοὺς Β, Ε πολλαπλασιάσας τοὺς Γ, Δ πεποίηκεν, ἔστιν ἄρα ὡς ὁ Β πρὸς τὸν Ε, οὕτως ὁ Γ πρὸς τὸν Δ. μετρεῖ δὲ ὁ Β τὸν Ε: μετρεῖ ἄρα καὶ ὁ Γ τὸν Δ ὁ μείζων τὸν ἐλάσσονα: ὅπερ ἐστὶν ἀδύνατον. οὐκ ἄρα οἱ Α, Β μετροῦσί τινα ἀριθμὸν ἐλάσσονα ὄντα τοῦ Γ. ὁ Γ ἄρα ἐλάχιστος ὢν ὑπὸ τῶν Α, Β μετρεῖται. Μὴ ἔστωσαν δὴ οἱ Α, Β πρῶτοι πρὸς ἀλλήλους, καὶ εἰλήφθωσαν ἐλάχιστοι ἀριθμοὶ τῶν τὸν αὐτὸν λόγον ἐχόντων τοῖς Α, Β οἱ Ζ, Ε: ἴσος ἄρα ἐστὶν ὁ ἐκ τῶν Α, Ε τῷ ἐκ τῶν Β, Ζ. καὶ ὁ Α τὸν Ε πολλαπλασιάσας τὸν Γ ποιείτω: καὶ ὁ Β ἄρα τὸν Ζ πολλαπλασιάσας τὸν Γ πεποίηκεν: οἱ Α, Β ἄρα τὸν Γ μετροῦσιν. λέγω δή, ὅτι καὶ ἐλάχιστον. εἰ γὰρ μή, μετρήσουσί τινα ἀριθμὸν οἱ Α, Β ἐλάσσονα ὄντα τοῦ Γ. μετρείτωσαν τὸν Δ. καὶ ὁσάκις μὲν ὁ Α τὸν Δ μετρεῖ, τοσαῦται μονάδες ἔστωσαν ἐν τῷ Η, ὁσάκις δὲ ὁ Β τὸν Δ μετρεῖ, τοσαῦται μονάδες ἔστωσαν ἐν τῷ Θ. ὁ μὲν Α ἄρα τὸν Η πολλαπλασιάσας τὸν Δ πεποίηκεν, ὁ δὲ Β τὸν Θ πολλαπλασιάσας τὸν Δ πεποίηκεν. ἴσος ἄρα ἐστὶν ὁ ἐκ τῶν Α, Η τῷ ἐκ τῶν Β, Θ: ἔστιν ἄρα ὡς ὁ Α πρὸς τὸν Β, οὕτως ὁ Θ πρὸς τὸν Η. ὡς δὲ ὁ Α πρὸς τὸν Β, οὕτως ὁ Ζ πρὸς τὸν Ε: καὶ ὡς ἄρα ὁ Ζ πρὸς τὸν Ε, οὕτως ὁ Θ πρὸς τὸν Η. οἱ δὲ Ζ, Ε ἐλάχιστοι, οἱ δὲ ἐλάχιστοι μετροῦσι τοὺς τὸν αὐτὸν λόγον ἔχοντας ἰσάκις ὅ τε μείζων τὸν μείζονα καὶ ὁ ἐλάσσων τὸν ἐλάσσονα: ὁ Ε ἄρα τὸν Η μετρεῖ. καὶ ἐπεὶ ὁ Α τοὺς Ε, Η πολλαπλασιάσας τοὺς Γ, Δ πεποίηκεν, ἔστιν ἄρα ὡς ὁ Ε πρὸς τὸν Η, οὕτως ὁ Γ πρὸς τὸν Δ. ὁ δὲ Ε τὸν Η μετρεῖ: καὶ ὁ Γ ἄρα τὸν Δ μετρεῖ ὁ μείζων τὸν ἐλάσσονα: ὅπερ ἐστὶν ἀδύνατον. οὐκ ἄρα οἱ Α, Β μετρήσουσί τινα ἀριθμὸν ἐλάσσονα ὄντα τοῦ Γ. ὁ Γ ἄρα ἐλάχιστος ὢν ὑπὸ τῶν Α, Β μετρεῖται: ὅπερ ἔδει δεῖξαι.
Given two numbers, to find the least number which they measure. Let A, B be the two given numbers; thus it is required to find the least number which they measure. Now A, B are either prime to one another or not. First, let A, B be prime to one another, and let A by multiplying B make C; therefore also B by multiplying A has made C. [VII. 16] Therefore A, B measure C I say next that it is also the least number they measure. For, if not, A, B will measure some number which is less than C. Let them measure D. Then, as many times as A measures D, so many units let there be in E, and, as many times as B measures D, so many units let there be in F; therefore A by multiplying E has made D, and B by multiplying F has made D; [VII. Def. 15] therefore the product of A, E is equal to the product of B, F. Therefore, as A is to B, so is F E. [VII. 19] But A, B are prime, primes are also least, [VII. 21] and the least measure the numbers which have the same ratio the same number of times, the greater the greater and the less the less; [VII. 20] therefore B measures E, as consequent consequent. And, since A by multiplying B, E has made C, D, therefore, as B is to E, so is C to D. [VII. 17] But B measures E; therefore C also measures D, the greater the less: which is impossible. Therefore A, B do not measure any number less than C; therefore C is the least that is measured by A, B. Next, let A, B not be prime to one another, and let F, E, the least numbers of those which have the same ratio with A, B, be taken; [VII. 33] therefore the product of A, E is equal to the product of B, F. [VII. 19] And let A by multiplying E make C; therefore also B by multiplying F has made C; therefore A, B measure C. I say next that it is also the least number that they measure. For, if not, A, B will measure some number which is less than C. Let them measure D. And, as many times as A measures D, so many units let there be in G, and, as many times as B measures D, so many units let there be in H. Therefore A by multiplying G has made D, and B by multiplying H has made D. Therefore the product of A, G is equal to the product of B, H; therefore, as A is to B, so is H to G. [VII. 19] But, as A is to B, so is F to E. Therefore also, as F is to E, so is H to G. But F, E are least, and the least measure the numbers which have the same ratio the same number of times, the greater the greater and the less the less; [VII. 20] therefore E measures G. And, since A by multiplying E, G has made C, D, therefore, as E is to G, so is C to D. [VII. 17] But E measures G; therefore C also measures D, the greater the less: which is impossible. Therefore A, B will not measure any number which is less than C.