Περιεχόμενο

• Βήματα
• Μέθοδος 1 από 2: Αλγόριθμος διαιρέτη
• Μέθοδος 2 από 2: Πρωταρχικοί παράγοντες
• Συμβουλές

Ο μεγαλύτερος κοινός διαιρέτης (GCD) δύο ακεραίων είναι ο μεγαλύτερος ακέραιος που διαιρεί καθέναν από αυτούς τους αριθμούς. Για παράδειγμα, το gcd για 20 και 16 είναι 4 (τόσο το 16 όσο και το 20 έχουν μεγάλους διαιρέτες, αλλά δεν είναι κοινά - για παράδειγμα, το 8 είναι διαιρέτης του 16, αλλά όχι διαιρέτης του 20). Υπάρχει μια απλή και συστηματική μέθοδος για την εύρεση του GCD, που ονομάζεται "αλγόριθμος του Ευκλείδη". Αυτό το άρθρο θα σας δείξει πώς να βρείτε τον μεγαλύτερο κοινό διαιρέτη δύο ακεραίων.

Βήματα

Μέθοδος 1 από 2: Αλγόριθμος διαιρέτη

1. 1 Παραλείψτε τυχόν σημάδια μείον.
2. 2 Μάθετε την ορολογία: όταν διαιρείται το 32 με το 5,
   • 32 - μέρισμα
   • 5 - διαιρέτης
   • 6 - ιδιωτικό
   • 2 - υπόλοιπο
3. 3 Προσδιορίστε το μεγαλύτερο από τους αριθμούς. Θα διαιρεθεί και ο μικρότερος αριθμός θα είναι ο διαιρέτης.
4. 4 Γράψτε τον ακόλουθο αλγόριθμο: (μέρισμα) = (διαιρέτης) * (πηλίκο) + (υπόλοιπο)
5. 5 Βάλτε έναν μεγαλύτερο αριθμό στη θέση του μερίσματος και έναν μικρότερο στη θέση του διαιρέτη.
6. 6 Βρείτε πόσες φορές ο μεγαλύτερος αριθμός διαιρείται με τον μικρότερο και γράψτε το αποτέλεσμα αντί για το πηλίκο.
7. 7 Βρείτε το υπόλοιπο και γράψτε το στην κατάλληλη θέση στον αλγόριθμο.
8. 8 Γράψτε ξανά τον αλγόριθμο, αλλά (Α) γράψτε τον προηγούμενο διαιρέτη ως νέο μέρισμα και (Β) το προηγούμενο υπόλοιπο ως νέο διαιρέτη.
9. 9 Επαναλάβετε το προηγούμενο βήμα έως ότου το υπόλοιπο είναι 0.
10. 10 Ο τελευταίος διαιρέτης θα είναι ο μεγαλύτερος κοινός διαιρέτης (GCD).
11. 11 Για παράδειγμα, ας βρούμε το GCD για 108 και 30:
12. 12 Παρατηρήστε πώς οι αριθμοί 30 και 18 από την πρώτη γραμμή σχηματίζουν τη δεύτερη γραμμή. Στη συνέχεια, 18 και 12 αποτελούν την τρίτη σειρά και 12 και 6 αποτελούν την τέταρτη σειρά. Δεν χρησιμοποιούνται πολλαπλάσια των 3, 1, 1 και 2. Αντιπροσωπεύουν τον αριθμό των φορών που το μέρισμα διαιρείται με τον διαιρέτη και ως εκ τούτου είναι μοναδικό για κάθε σειρά.

Μέθοδος 2 από 2: Πρωταρχικοί παράγοντες

1. 1 Παραλείψτε τυχόν σημάδια μείον.
2. 2 Βρείτε πρώτους παράγοντες αριθμών. Παρουσιάστε τα όπως φαίνεται στην εικόνα.
   • Για παράδειγμα, για 24 και 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Για παράδειγμα, για 50 και 35:
     • 50- 2 x 5 x 5
     • 35- 5 x 7
3. 3 Βρείτε κοινούς πρωταρχικούς παράγοντες.
   • Για παράδειγμα, για 24 και 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 Χ 3 x 3
   • Για παράδειγμα, για 50 και 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Πολλαπλασιάστε τους κοινούς πρωταρχικούς παράγοντες.
   • Για 24 και 18, πολλαπλασιάστε 2 και 3 και παρε 6... Το 6 είναι ο μεγαλύτερος κοινός παρονομαστής των 24 και 18.
   • Δεν υπάρχει τίποτα να πολλαπλασιαστεί για 50 και 35. 5 Είναι ο μόνος κοινός πρωταρχικός παράγοντας και είναι το GCD.
5. 5 Εκανε!

Συμβουλές

• Ένας τρόπος για να το γράψετε αυτό είναι: μέρισμα> mod divider> = υπόλοιπο? GCD (a, b) = b εάν mod b = 0, και gcd (a, b) = gcd (b, a mod b) αλλιώς.
• Για παράδειγμα, ας βρούμε το GCD (-77.91). Πρώτον, χρησιμοποιήστε 77 αντί -77: το GCD (-77,91) μετατρέπεται σε GCD (77,91). Το 77 είναι μικρότερο από 91, οπότε πρέπει να τα αλλάξουμε, αλλά σκεφτείτε πώς λειτουργεί ο αλγόριθμος αν δεν το κάνουμε. Κατά τον υπολογισμό του 77 mod 91, παίρνουμε 77 (77 = 91 x 0 + 77). Δεδομένου ότι αυτό δεν είναι μηδέν, εξετάζουμε την κατάσταση (b, a mod b), δηλαδή GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (το 14 είναι το υπόλοιπο). Δεν είναι μηδέν, οπότε το GCD (91,77) γίνεται GCD (77,14). 77 mod 14 = 7. Αυτό δεν είναι μηδέν, οπότε το GCD (77,14) γίνεται GCD (14,7). 14 mod 7 = 0 (από 14/7 = 2 χωρίς υπόλοιπο). Απάντηση: GCD (-77.91) = 7.
• Η περιγραφόμενη μέθοδος είναι πολύ χρήσιμη για την απλοποίηση των κλασμάτων. Στο παραπάνω παράδειγμα: -77/91 = -11/13, αφού το 7 είναι ο μεγαλύτερος κοινός παρονομαστής των -77 και 91.
• Εάν το a και το b είναι ίσο με το μηδέν, τότε οποιοσδήποτε μη μηδενικός αριθμός είναι ο διαιρέτης τους, οπότε σε αυτή την περίπτωση δεν υπάρχει GCD (οι μαθηματικοί απλά πιστεύουν ότι ο μεγαλύτερος κοινός διαιρέτης του 0 και του 0 είναι 0).