Euklidscher Algorithmus

26.11.2007, 21:39

ethused-Earthling

Euklidscher Algorithmus

Hallo Gleichgesinnte,

ich habe folgende Aufgaben zu lösen:

Bestimme alle $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$

1. $\begin{eqnarray*} ggT(n, n+1) \end{eqnarray*}$
2. $\begin{eqnarray*} ggT (n, n+2) \end{eqnarray*}$

Meine Lösungen sind:

zu 1:

Da $\begin{eqnarray*} n+1 = 1 \cdot n + 1 \end{eqnarray*}$ ist $\begin{eqnarray*} ggT (n, n+1)= ggT (n , 1) \end{eqnarray*}$ . Der größte Teiler von 1 ist 1, also ist $\begin{eqnarray*} ggT (n, n+1)=1 \end{eqnarray*}$ .

zu 2:

Da $\begin{eqnarray*} n+2 = 1 \cdot n + 2 \end{eqnarray*}$ ist $\begin{eqnarray*} ggT (n, n+2)= ggT (n, 2) \end{eqnarray*}$ . Nun kann n ungerade oder gerade sein.

1. Fall, $\begin{eqnarray*} n= 2a && ggT (2a, 2) \end{eqnarray*}$ ist gesucht.

Da $\begin{eqnarray*} 2a = a \cdot 2 +0 \end{eqnarray*}$ ist $\begin{eqnarray*} ggT (2a , 2) = ggT (2,0) \end{eqnarray*}$ .
Da der größte Teiler gleich 2 ist, ist $\begin{eqnarray*} ggT (2a, 2)= 2 \end{eqnarray*}$ .

2. Fall ( $\begin{eqnarray*} n=2a-1 && ggT (2a - 1, 2) \end{eqnarray*}$ ist gesucht.
Da $\begin{eqnarray*} 2a-1 = a \cdot 2 - 1 \end{eqnarray*}$ , ist $\begin{eqnarray*} ggT (2a-1, 2) = ggT (2, -1)= 1 \end{eqnarray*}$ .

Also ist $\begin{eqnarray*} ggT(n, n+2)= \left\{\begin{array}{ll} 2 & \rightarrow n= 2a, a \in \mathbb N \\ 1 & \rightarrow n= 2a-1, a \in \mathbb N \end{array}\right. \end{eqnarray*}$

So... hoffe, dass das jemand lesen kann Augenzwinkern

.
Insbesondere bei der zweiten Aufgabe habe ich so meine Zweifel....

26.11.2007, 21:52

tmo

Auf diesen Beitrag antworten »

das ist alles richtig.

allerdings kann man das ganze auch ein bisschen knapper aufschreiben Augenzwinkern

z.b. bei der 2:

$\begin{eqnarray*} ggT(n,2) \end{eqnarray*}$

der größte teiler von 2 ist 2, also ist der ggT 2, wenn 2|n gilt. sonst ist er 1.

26.11.2007, 22:01

ethused-Earthling

Auf diesen Beitrag antworten »

Gut, dann würde ich nur noch folgendes wissen:

1. Ist es von Bedeutung, ob ich bei dem zu suchenden $\begin{eqnarray*} ggT(a,b) \end{eqnarray*}$ den Wert a in der Form $\begin{eqnarray*} a= bq+r \end{eqnarray*}$ oder den Wert b nehme bzw. welche Voraussetzung muss erfüllt sein, damit ich den jeweiligen Wert nehmen kann?

2. In der Form $\begin{eqnarray*} a= bq + r \end{eqnarray*}$ , kann also sehr wohl $\begin{eqnarray*} r<0 \end{eqnarray*}$ gelten?

3. Der Wert q in $\begin{eqnarray*} a= bq + r \end{eqnarray*}$ kann also durchaus undefiniert sein?
Gerade deswegen habe ich gezögert aus $\begin{eqnarray*} ggT (2a, 2)= ggT (2, -1) \end{eqnarray*}$ zu folgern (also $\begin{eqnarray*} 2a= a \cdot 2 \end{eqnarray*}$ , wobei a unbestimmt ist).

26.11.2007, 22:21

ethused-Earthling

Auf diesen Beitrag antworten »

Und damit ich heute auch mit einem guten Gewissen schlafen gehen kann, würde ich abgesehen von den Fragen im vorhergehenden Beitrag, noch um einen kurzen Blick auf folgende Aufgaben bitten... Augenzwinkern

3. $\begin{eqnarray*} ggT (n, 2n-1) \end{eqnarray*}$

Da $\begin{eqnarray*} 2n-1 = 2 \cdot n - 1 \end{eqnarray*}$ ist $\begin{eqnarray*} ggT (n, 2n-1) = ggT (n, -1) = 1 \end{eqnarray*}$ .

4. $\begin{eqnarray*} ggT (2n - 1, 2n^2 - 1) \end{eqnarray*}$

Da $\begin{eqnarray*} 2n^2 - 1 = n \cdot 2n - 1 \end{eqnarray*}$ ist $\begin{eqnarray*} ggT (2n - 1, 2n^2 - 1) = ggT (2n, - 1)=1 \end{eqnarray*}$

Sollten ebenfalls richtig sein...

26.11.2007, 22:23

Auf diesen Beitrag antworten »

Zitat:

Original von ethused-Earthling
4. $\begin{eqnarray*} ggT (2n - 1, 2n^2 - 1) \end{eqnarray*}$

Da $\begin{eqnarray*} 2n^2 - 1 = n \cdot 2n - 1 \end{eqnarray*}$ ist $\begin{eqnarray*} ggT (2n - 1, 2n^2 - 1) = ggT (2n, - 1)=1 \end{eqnarray*}$

Sollten ebenfalls richtig sein...

$\begin{eqnarray*} n \cdot 2n - 1 \end{eqnarray*}$ ist was anderes als $\begin{eqnarray*} n \cdot (2n - 1) \end{eqnarray*}$ . Klammern, Klammern, Klammern ... geschockt

Das Endergebnis ist trotzdem richtig, aber mit etwas anderer Argumentation. Oder habe ich deine Kurzform missverstanden. verwirrt

26.11.2007, 22:54

ethused-Earthling

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
$\begin{eqnarray*} n \cdot 2n - 1 \end{eqnarray*}$ ist was anderes als $\begin{eqnarray*} n \cdot (2n - 1) \end{eqnarray*}$ . Klammern, Klammern, Klammern ... geschockt

Das Endergebnis ist trotzdem richtig, aber mit etwas anderer Argumentation. Oder habe ich deine Kurzform missverstanden. verwirrt

Ich glaube schon: $\begin{eqnarray*} 2n^2 - 1= n \cdot 2n - 1 \neq n \cdot (2n - 1 ) \end{eqnarray*}$ . Den Ausdruck $\begin{eqnarray*} n(2n-1) \end{eqnarray*}$ habe ich übrigens auch nirgends hingeschrieben.

Was ist mit den Fragen in meinem vorherigen Post?

26.11.2007, 22:57

Auf diesen Beitrag antworten »

Das ist doch meine Frage: Ich verstehe deine Argumentation bei 4. überhaupt nicht. unglücklich

Mir wäre sowas wie

$\begin{eqnarray*} \operatorname{ggT}(2n-1,2n^2-1) &=& \operatorname{ggT}(2n-1,2n^2-1-n(2n-1)) = \operatorname{ggT}(2n-1,n-1)\\ &=& \operatorname{ggT}(2n-1-2(n-1),n-1) = \operatorname{ggT}(1,n-1) = 1 \end{eqnarray*}$

wesentlich einleuchtender...

26.11.2007, 23:04

ethused-Earthling

Auf diesen Beitrag antworten »

Bei Aufgabe 4 habe ich doch nach folgendem Schema gearbeitet:

$\begin{eqnarray*} ggT(a,b)=ggT(bq+r, b)=ggT(b,r) \end{eqnarray*}$

26.11.2007, 23:06

Auf diesen Beitrag antworten »

Dann nenne mir mal bitte $\begin{eqnarray*} a,b,q,r \end{eqnarray*}$ , die du da eingesetzt haben willst.

Links $\begin{eqnarray*} b=2n-1 \end{eqnarray*}$ und ab der Mitte dann $\begin{eqnarray*} b=2n \end{eqnarray*}$ ? So geht's nicht, mitten im Rennen (ähm, in der Formel) die Pferde wechseln! Augenzwinkern

Neue Frage »

Antworten »

Euklidscher Algorithmus

Verwandte Themen