ggT(a,b) - a bei gegebenen b bestimmen

16.05.2021, 11:38	tweek	Auf diesen Beitrag antworten »
ggT(a,b) - a bei gegebenen b bestimmen Hallo! Ein etwas ungewöhnliches Problem: Wie bestimme ich alle Zahlen a, welche zusammen mit einer bestimmten Zahl b einen gemeinsamen ggT haben? Ich hab schon mit Primfaktorzerlegung rumprobiert, aber mir fehlt die zündende Idee... Kann mir wer weiterhelfen? Danke!
16.05.2021, 11:55	Elvis	Auf diesen Beitrag antworten »
Die natürliche Zahl $\begin{eqnarray} b>1 \end{eqnarray}$ hat eine (bis auf die Reihenfolge) eindeutige Primfaktorzerlegung $\begin{eqnarray} b=p_1^{n_1}\cdot ... \cdot p_k^{n_k} \end{eqnarray}$ mit einer natürlichen Zahl $\begin{eqnarray} k\ge 1 \end{eqnarray}$ , paarweise verschiedenen Primzahlen $\begin{eqnarray} p_1,...,p_k \end{eqnarray}$ und natürlichen Zahlen $\begin{eqnarray} n_1,...,n_k\ge 1 \end{eqnarray}$ . Eine natürliche Zahl $\begin{eqnarray} a \end{eqnarray}$ hat genau dann einen $\begin{eqnarray} ggT(a,b)\gt 1 \end{eqnarray}$ , wenn eine der Primzahlen $\begin{eqnarray} p_1,...,p_k \end{eqnarray}$ die Zahl $\begin{eqnarray} a \end{eqnarray}$ teilt.
16.05.2021, 21:52	tweek	Auf diesen Beitrag antworten »
Danke! Das ist schon mal ein guter Denkanstoss. Ich habe aber vergessen zu erwähnen, dass der ggT auch vorgegeben ist. Konkret lautet die Fragestellung: Alle a für ggT(a,270) = 18 Wie schränke ich hierbei ein?
16.05.2021, 22:37	Elvis	Auf diesen Beitrag antworten »
$\begin{eqnarray} 270=2\cdot 3^3\cdot 5=18\cdot 15 \end{eqnarray}$ . Also haben alle natürlichen Zahlen, die durch 18 und nicht durch 5 und nicht durch 27 geteilt werden, mit 270 den ggT 18. Alle anderen Primzahlen, die eventuell a noch teilen sind nicht Teiler von 270, teilen also nicht den ggT.
16.05.2021, 23:23	tweek	Auf diesen Beitrag antworten »
OK, also verstehe ich das richtig: Weil von den Primfaktoren von 270 die 2 die 18 teilt, die 3^3 und die 5 aber nicht, muss man halt die 27 und 5 ausschließen? Danke vielmals!
17.05.2021, 06:46	HAL 9000	Auf diesen Beitrag antworten »
Etwas weiter ausgeholt, und wo vielleicht eine Systematik für ähnliche Fragestellungen erkennbar ist: Wenn $\begin{eqnarray} ggT(a,b)=c \end{eqnarray}$ gilt, so bedeutet das für den Primfaktor $\begin{eqnarray} p \end{eqnarray}$ , der in den Zahlen $\begin{eqnarray} a,b,c \end{eqnarray}$ in den Vielfachheiten $\begin{eqnarray} u,v,w \end{eqnarray}$ enthalten sein möge die Beziehung $\begin{eqnarray} \min(u,v) = w \end{eqnarray}$ . Gehen wir das mal die verschiedenen Primfaktoren für $\begin{eqnarray} b=2^1\cdot 3^3\cdot 5^1 \end{eqnarray}$ sowie $\begin{eqnarray} c=2^1\cdot 3^2 \end{eqnarray}$ durch. $\begin{eqnarray} p=2 \end{eqnarray}$ : Hier ist $\begin{eqnarray} v=1 \end{eqnarray}$ und $\begin{eqnarray} w=1 \end{eqnarray}$ , die Forderung $\begin{eqnarray} \min(u,1)=1 \end{eqnarray}$ bedeutet $\begin{eqnarray} u\geq 1 \end{eqnarray}$ . $\begin{eqnarray} p=3 \end{eqnarray}$ : Hier ist $\begin{eqnarray} v=3 \end{eqnarray}$ und $\begin{eqnarray} w=2 \end{eqnarray}$ , die Forderung $\begin{eqnarray} \min(u,3)=2 \end{eqnarray}$ bedeutet $\begin{eqnarray} u=2 \end{eqnarray}$ . $\begin{eqnarray} p=5 \end{eqnarray}$ : Hier ist $\begin{eqnarray} v=1 \end{eqnarray}$ und $\begin{eqnarray} w=0 \end{eqnarray}$ , die Forderung $\begin{eqnarray} \min(u,1)=0 \end{eqnarray}$ bedeutet $\begin{eqnarray} u=0 \end{eqnarray}$ . $\begin{eqnarray} p\geq 7 \end{eqnarray}$ : Schlussendlich ist hier $\begin{eqnarray} v=0 \end{eqnarray}$ und $\begin{eqnarray} w=0 \end{eqnarray}$ , die Forderung $\begin{eqnarray} \min(u,0)=0 \end{eqnarray}$ ist für alle $\begin{eqnarray} u\geq 0 \end{eqnarray}$ erfüllt. Somit besitzt $\begin{eqnarray} a \end{eqnarray}$ zwangsläufig die Darstellung $\begin{eqnarray} a = 2^r\cdot 3^2\cdot a' \end{eqnarray}$ mit $\begin{eqnarray} r\geq 1 \end{eqnarray}$ , wobei $\begin{eqnarray} a' \end{eqnarray}$ allenfalls Primfaktoren $\begin{eqnarray} \geq 7 \end{eqnarray}$ enthalten darf (ggfs. aber auch gar keine). Das kann man dann auch so wie Elvis formulieren, d.h., $\begin{eqnarray} a \end{eqnarray}$ muss durch 18 teilbar sein, aber darf weder durch 27 noch durch 5 teilbar sein.
Anzeige

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »