Berechnen Sie die größten gemeinsamen Teiler

Question

Beispiel :
Berechnen Sie die größten gemeinsamen Teiler
(a) ggT(15, 2⁴⁴⁵ + 7) und
(b) ggT(3k + 2,10k + 6) für alle k ∈ ℤ.

Danke im Voraus

Comments

ggT(3k+2,10k+6) = ggT(3k+2,k) = ggT(2,k).

Answer 1

(a) ggT(15, 2⁴⁴⁵ + 7)

Der ist \(15\), \(5\), \(3\) oder \(1\).

Es gilt \(n|2^{445}+7\iff n-7\equiv 2^{445} \mod n\).

Prüfe für jedes \(n\in \{15,5,3,1\}\), ob \(n-7\equiv 2^{445} \mod n\) gilt.

Answer 2

2^445 + 7 = 2·4^222 + 7

Vermutlich siehst du jetzt bereits anhand der Umformung, dass die 3 den Term teilt, die 5 allerdings nicht. Wenn du es nicht auf Anhieb siehst, dann denke daran das du die Basis einer Potenz modulo nehmen kannst.

Comments

3 ist also mein ggT

---

3 ist also mein ggT

richtig. Und dann kannst du das mit wolframalpha prüfen.

---

Vielen Dank und muss ich bei b) Polynomdivision machen, um den ggT zu bestimmen ?

---

Vielen Dank und muss ich bei b) Polynomdivision machen, um den ggT zu bestimmen ?

Genau. Du solltest dann auf einen ggT von 1 kommen.

Answer 3

euklidischer Algorithmus:

10k + 6-3·(3k + 2)=k

3k + 2-3·k=2

3k+2-2=3k

3k teilt weder 3k + 2 noch 10k + 6.

3k + 2 und 10k + 6 sind teilerfremd.

Comments

Dann wären auch 2 und 6 teilerfremd.

---

aber nicht für jedes k∈ℕ.