Teilerfremde Zahlen

06.11.2005, 00:35

OrlandoGardiner

Auf diesen Beitrag antworten »

Teilerfremde Zahlen

Hallo!

Ich soll folgende Aufgabe lösen:

Zeige, dass die beiden Zahlen $\begin{eqnarray*} 22k+7 \end{eqnarray*}$ und $\begin{eqnarray*} 33k+5 \end{eqnarray*}$ für alle $\begin{eqnarray*} k\in \mathbb{Z} \end{eqnarray*}$ teilerfremd sind.

Aber irgendwie habe ich da gerade ein Brett vorm Kopf... Kann ja eigentlich nicht so schwer sein.

Mein erster Gedanke war, dass das aufgrund der Primfaktoren der 22=2*11 und der 33=3*11 sowie der Addition der beiden Primzahlen so ist.

Ich habe dann erstmal versucht die Differenz der Zahlen zu bilden (zuerst in einer Tabelle mittels Einsetzen der Zahlen 0-5), weil ich mir dachte, dass wenn dabei eine Primzahl herauskommt die beiden Zahlen keinen gemeinsamen Teiler haben könne (Seltsamer Ansatz? Etwas besseres ist mir nicht eingefallen... Liegt hier mein Denkfehler?). Das Ganze wollte ich dann durch vollständige Induktion beweisen. Dabei habe ich mich aber vollkommen verhaspelt und weiß nun nicht mehr weiter.

Hat jemand eine bessere Idee? Ich hoffe, ihr könnt mir helfen.

06.11.2005, 00:54

AD

Auf diesen Beitrag antworten »

Das Naheliegende ist ja wohl der euklidische Algorithmus. Warum probierst du es nicht mit dem?

06.11.2005, 08:34

Thales

Auf diesen Beitrag antworten »

Alternativ kann man auch die Tatsache zur Hilfe nehmen, dass jeder gemeinsame Teiler von $\begin{eqnarray*} 22k+7 \end{eqnarray*}$ und $\begin{eqnarray*} 33k+5 \end{eqnarray*}$ auch gemeinsamer Teiler von $\begin{eqnarray*} a*(22k+7) \end{eqnarray*}$ und $\begin{eqnarray*} b*(33k+5) \end{eqnarray*}$ mit $\begin{eqnarray*} a, b \in \mathbb Z \end{eqnarray*}$ ist. Damit muss er auch $\begin{eqnarray*} a*(22k+7)-b*(33k+5) \end{eqnarray*}$ teilen. Bei geschickter Wahl von a und b kämest Du ebenfalls auf einen Beweis.

06.11.2005, 10:19

AD

Auf diesen Beitrag antworten »

Und der euklidische Algorithmus (in seiner erweiterten Variante) gestattet es ja gerade, solche ganzzahligen Faktoren $\begin{eqnarray*} a,b \end{eqnarray*}$ zu bestimmen. D.h. solche mit

$\begin{eqnarray*} a(22k+7)-b(33k+5) = 1 \end{eqnarray*}$ .

06.11.2005, 11:11

OrlandoGardiner

Auf diesen Beitrag antworten »

Danke!

Das werde ich gleich mal probieren.

06.11.2005, 14:23

OrlandoGardiner

Auf diesen Beitrag antworten »

Hallo.

Leider verstehe ich das noch immer nicht so ganz.

Ich habe mich mal daran versucht bekomme aber am Ende keine Lösung heraus.

Ich habe so angefangen:

$\begin{eqnarray*} \begin{tabular}[t]{cc|cc|cc}$a$ & $b$ & $q$ & $r$ & $x$ & $y$\\\hline$22k+7$&$33k+5$&$\frac{2}{3}$&$\frac{11}{3}$&$1$&$-\frac{2}{3}$\\$33k+5$&$\frac{11}{3}$&$9k+1$&$\frac{4}{11}$&$-9k-1$&$6k+\frac{1}{3}$\\\vdots&\vdots&\vdots&\vdots&\vdots&\vdots\\\end{tabular} \end{eqnarray*}$

Dann kommt aber am Ende nur Unsinn heraus. Bin ich mit dem Ansatz total auf dem Holzweg, oder habe ich nur irgendwo einen Rechenfehler gemacht?

Anzeige

06.11.2005, 14:49

4c1d

Auf diesen Beitrag antworten »

Warum machst du es dir so kompliziert? Der euklidische Algorithmus basiert ja im Grunde auf der Gleichung (a,b)=(a,a-b) (mit a,b aus Z).
Also (22k+7,33k+5)=(22k+7,11k-2)=...

06.11.2005, 14:58

AD

Auf diesen Beitrag antworten »

Genauso ist es:

$\begin{eqnarray*} (33k+5) - 1 * (22k+7) &=& 11k-2\\ (22k+7) - 2*(11k-2) &=& 11\\ (11k-2) - (k-1)*11 &=& 9\\ 11 - 1 * 9 &=& 2\\ 9 - 4 * 2 &=& 1 \end{eqnarray*}$

Und jetzt "rückwärts" eingesetzt:

$\begin{eqnarray*} (33k+5) - 1 * (22k+7) &=& 11k-2\\ -2*(33k+5) + 3*(22k+7) &=& 11\\ (2k-1)*(33k+5) + (-3k+2)*(22k+7) &=& 9\\ (-2k-1)*(33k+5) + (3k+1)*(22k+7) &=& 2\\ (10k+3)*(33k+5) + (-15k-2)*(22k+7) &=& 1 \end{eqnarray*}$

Also im Endeffekt mit $\begin{eqnarray*} a=10k+3,b=15k+2 \end{eqnarray*}$ die gesuchte Gleichung $\begin{eqnarray*} a(33k+5)-b(22k+7) &=& 1 \end{eqnarray*}$ .

06.11.2005, 16:13

Thales

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Und der euklidische Algorithmus (in seiner erweiterten Variante) gestattet es ja gerade, solche ganzzahligen Faktoren $\begin{eqnarray*} a,b \end{eqnarray*}$ zu bestimmen. D.h. solche mit

$\begin{eqnarray*} a(22k+7)-b(33k+5) = 1 \end{eqnarray*}$ .

Es reicht aber doch schon, über kgV dazu zu kommen, dass $\begin{eqnarray*} 3*(22k+7)-2*(33k+5) = 11 \end{eqnarray*}$ ist. Damit käme als ggT>1 nur noch 11 in Frage, aber bei Division durch 11 lassen die Zahlen den Rest 7 bzw. 5, so dass auch das ausgeschlossen ist. Oder ist in diesem Beweis irgendeine Lücke? verwirrt

verwirrt

06.11.2005, 16:17

AD

Auf diesen Beitrag antworten »

Klar, geht auch - aber warum auf halben Wege stehenbleiben?

06.11.2005, 16:27

Thales

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Klar, geht auch - aber warum auf halben Wege stehenbleiben?

Um sich die Arbeit mit dem Algorithmus zu sparen. Das geht zwar nur in Fällen wie diesem, wo das kgV der k-Koeffizienten relativ einfach zu bilden ist und man nur eine einzige Möglichkeit für den ggT ausprobieren muss, aber immerhin geht es. Augenzwinkern

Augenzwinkern

06.11.2005, 17:09

OrlandoGardiner

Auf diesen Beitrag antworten »

Vielen Dank euch allen, ich glaube, ich habe es jetzt verstanden... smile

smile

06.11.2005, 18:26

Fiona

Auf diesen Beitrag antworten »

Ich muss die selbe Aufgabe bearbeiten und habe es leider noch nicht verstanden.

Das mit der Tabelle, was OrlandoGardener da gemacht hat, kenne ich und hatte ich auch probiert. Hat aber auch nicht geklappt.

Aber die Gleichungen von Arthur Dent sagen mir leider überhaupt nix... traurig

traurig

Ich kann die Einsetzung, von der da die Rede ist nicht erkennen... und auch sonst ist mir nicht wirklich klar, was da eigentlich vor sich geht...

Kann mir das bitte jemand erklären? Ich stehe da echt auf dem Schlauch...

06.11.2005, 20:06

OrlandoGardiner

Auf diesen Beitrag antworten »

Argh... jetzt dachte ich, ich hätte das verstanden, aber als ich mir das gerade nochmal angeschaut habe, habe ich nur noch Bahnhof verstanden.

Wie kommst du auf -2 und 3 im zweiten Teil?

06.11.2005, 20:19

AD

Auf diesen Beitrag antworten »

Ich setze mal abkürzend $\begin{eqnarray*} u=33k+5 \end{eqnarray*}$ und $\begin{eqnarray*} v=22k+7 \end{eqnarray*}$ . Dann lauten die ersten beiden Zeilen aus dem oberen Block:

$\begin{eqnarray*} u - 1 * v &=& 11k-2\\ v - 2*(11k-2) &=& 11 \end{eqnarray*}$

Jetzt setze ich den Ausdruck für $\begin{eqnarray*} 11k-2 \end{eqnarray*}$ aus der ersten Zeile in die zweite ein:

$\begin{eqnarray*} v - 2*(u - 1 * v) &=& 11 \end{eqnarray*}$ , also
$\begin{eqnarray*} -2*u + 3 * v &=& 11 \end{eqnarray*}$

Genauso bei den anderen Zeilen.

06.11.2005, 21:04

OrlandoGardiner

Auf diesen Beitrag antworten »

Soweit klar... aber daraus folgt dirket meine nächste Frage. Ich scheine da offenbar etwas grundsätzliches nicht verstanden zu haben, kann aber nicht genau sagen was.

$\begin{eqnarray*} u - 1 * v &=& 11k-2\\ v - 2*(11k-2) &=& 11 \end{eqnarray*}$

woher kommt dabei die erste 2 in der zweiten Zeile.

Tut mir echt leid, dass ich dich mit diesen ganzen dämlichen Fragen nerve... Vielen, vielen Dank für die Hilfe.

06.11.2005, 21:12

AD

Auf diesen Beitrag antworten »

Willkür... nein im Ernst: Normalerweise muss das laut euklidischen Algorithmus $\begin{eqnarray*} \left\lfloor \frac{22k+7}{11k-2} \right\rfloor \end{eqnarray*}$ sein. Und für $\begin{eqnarray*} k\geq 2 \end{eqnarray*}$ kommt da nun mal

$\begin{eqnarray*} \left\lfloor \frac{22k+7}{11k-2} \right\rfloor = \left\lfloor 2+\frac{11}{11k-2} \right\rfloor = 2 \end{eqnarray*}$

raus. Und um $\begin{eqnarray*} k\leq 1 \end{eqnarray*}$ kümmern wir uns zunächst nicht, denn das für alle ganzzahligen $\begin{eqnarray*} k \end{eqnarray*}$ gültige Endresultat

$\begin{eqnarray*} (10k+3)(33k+5)-(15k+2)(22k+7) = 1 \end{eqnarray*}$

rechtfertigt die Umformungen. Klingt vielleicht seltsam, ist aber so.

07.11.2005, 09:34

OrlandoGardiner

Auf diesen Beitrag antworten »

Ja, okay. Da leuchtet mir ein. smile

smile

Vielen Dank.

07.11.2005, 10:33

Fiona

Auf diesen Beitrag antworten »

Oh Gott... Das war ja einfach...

Die beiden Blöcke von Arthur Dent waren also alternativ... und ich dachte, die würden aufeinander folgen...

Danke auch von mir! Wink

Wink

Freude

Liebe Grüße, Fiona

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »