Wie berechnet man den größten gemeinsamen Teiler?

Mehr über den größten gemeinsamen Teiler (manchmal auch als größter gemeinsamer Faktor bezeichnet) : Der größte gemeinsame Teiler (GCD) zwischen zwei positiven Ganzzahlen $n_1$ und $n_2$ ist die größte Ganzzahl, die sowohl $n_1$ als auch $n_2$ teilt. Es ist normalerweise leicht durch Inspektion zu finden (das heißt, viele Zahlen werden systematisch ausprobiert, bis wir sie finden), aber das gilt nur für kleine Zahlen. Das Berechnen der GCD für große Zahlen durch Inspektion kann mühsam oder einfach schwierig sein.

Glücklicherweise gibt es eine systematische, einfache Methode (Husten, Husten), um die GCD für zwei Zahlen zu berechnen. Die Methode geht so

• Berechnen Sie die Hauptzersetzung von $n_1$ und $n_2$. Symbolisch hätten wir so etwas: $$n_1 = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_n^{\alpha_n}$$ $$n_2 = q_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdots p_m^{\alpha_m}$$
• Suchen Sie die Liste der gebräuchlichen Primzahlen in der entsprechenden Primzerlegung. Wenn es keine gemeinsamen Primzahlen gibt, dann STOP, haben Sie festgestellt, dass GCD = 1. Andernfalls sei $\{r_1, ..., r_k \}$ die Liste der gemeinsamen Primzahlen $k$ und $\alpha_{i_l}, \beta_{i_l}$ für $l=1,2,..,k$ die entsprechenden Exponenten, die in der Primzerlegung von $n_1$ und $n_2$ für die entsprechenden gemeinsamen gefunden wurden Primzahlen.
  
  
• Die GCD wird berechnet als: $$GCD = r_1^{\min\{\alpha_{i_1}, \beta_{i_1}\}} \cdot r_2^{ \min\{\alpha_{i_2}, \beta_{i_2}\}} \cdots r_k^{\min\{\alpha_{i_k}, \beta_{i_k}\}}$$

Die obige Methode sieht zu komplex aus? Nicht wirklich. Sehen wir uns ein Beispiel an: Berechnen wir die GCD für $n_1 = 165$ und $n_2 = 1575$. Lassen Sie uns die Hauptzerlegung jeder dieser Zahlen finden (Sie können unseren Hauptzerlegungsrechner verwenden).

$$165 = 3 \cdot 5 \cdot 11$$ $$1575 = 3^2 \cdot 5^2 \cdot 7$$

Aus dem oben Gesagten: Welche Primzahlen haben diese beiden Zahlen gemeinsam? Wie wir sehen können, sind die gemeinsamen Primzahlen 3 und 5. Wenn wir die Exponenten dieser gemeinsamen Primzahlen in jeder der Zahlen betrachten, sehen wir das Minimum zwischen den beiden. In diesem Fall ist der minimale Exponent für 3 1 und der minimale Exponent für 5 ist ebenfalls 1. Daher

$$GCD = 3^1 \cdot 5^1 = 3 \cdot 5 = 15$$

Neben dem GDC-Rechner können Sie aus unserer Auswahl wählen Algebra-Rechner und Löser .