Elementare Zahlentheorie Musterl¨osungen Zettel 4 …ktent/elemloes04.pdf · Elementare...

Elementare Zahlentheorie

Musterlosungen Zettel 4

Aufgabe 1.

a) Zunachst gilt 10 ≡ −1 (mod 11). Wegen der Vertraglichkeit der Kongru-enzen mit Multiplikation folgt 10k ≡ (−1)k (mod 11) und aufgrund derVertraglichkeit mit der Addition folgt die Behauptung:

dk·10k+dk−1·10

k−1+· · ·+d1·10+d0 ≡ dk·(−1)k+· · ·+d1·(−1)+d0 (mod 11).

Ist nun a ∈ Z eine Zahl und ihre Darstellung im Zehnersystem gegebendurch a = dk ·10

k + · · ·+d1 ·10+d0 mit 0 ≤ di ≤ 9. (Hierbei wurde a ≥ 0angenommen, da das Vorzeichen fur die Teilbarkeit durch 11 keine Rollespielt.)

Definiere die alternierende Quersumme von a durch folgende Regel:

Qalt(a) := d0 − d1 + d2 − · · · + (−1)kdk.

Dann gilt nach obiger Kongruenz stets a ≡ Qalt(a) (mod 11) und da-her ist die Zahl a genau dann durch 11 teilbar, wenn ihre alternierendeQuersumme durch 11 teilbar ist.

b) Sei b ein Palindrom mit einer geraden Anzahl an Ziffern. Formal bedeutetdies fur die Darstellung von b im Zehnersystem:

b = d2k−1 · 102k−1 + d2k−2 · 10

2k−2 + · · · + d1 · 10 + d0,

mit 0 ≤ di ≤ 9 fur alle i und di = dj falls i + j = 2k − 1. Betrachte diealternierende Quersumme von b:

QAlt(b) = d0−d1+d2−· · ·+(−1)2k−1d2k−1 = (d0−d2k−1)+(d2k−2−d1)+· · · = 0.

Aufgrund der Palindromeigenschaft ist jede der Klammern gleich 0, dieZiffern

”heben sich auf“.

Aufgabe 2.

Betrachte zu n ∈ N die Darstellung von N zur Basis b = 1000, also

n = tk · 1000k + tk−1 · 1000

k−1 + · · · + t1 · 1000 + t0 0 ≤ ti ≤ 999.

Definiere dann f : N→ Z durch

f(n) := t0 − t1 + · · · + (−1)k · tk.

Dies ist analog zur alternierenden Quersumme, nur dass hier die Basis 1000gewahlt ist, d.h. es werden gewissermaßen

”3er Packs“ von Ziffern in diese al-

ternierende Quersumme aufgenommen. Der Betrag stellt sicher, dass der Werteine naturliche Zahl ist, fur Teilbarkeitsaussagen ist das Vorzeichen ja unerheb-lich.

Es gilt 7 ·11 ·13 = 1001 und daraus folgen die Kongruenzen 1000 ≡ −1 (mod 7),1000 ≡ −1 (mod 11) und 1000 ≡ −1 (mod 13). Analog zu Aufgabe 1a) folgtnun n ≡ f(n) (mod m) fur m ∈ {7, 11, 13} und daraus folgen die Teile a) bisc).

Sei nun n := 118.050.660. Dann ist n durch 2 und 5 teilbar, weil die letzteZiffer durch 2 und 5 teilbar ist. Zur Teilbarkeit durch 3 betrachte man dieQuersumme:

Q(n) = 1 + 1 + 8 + 0 + 5 + 0 + 6 + 6 + 0 = 27.

Da Q(n) durch 3 teilbar ist, gilt dies auch fur n. Fur die Teilbarkeit durch 7,11 und 13 betrachte die Funktion f :

f(n) = 660 − 50 + 118 = 728.

Es gilt 728 = 7 · 104 = 66 · 11 + 2 = 56 · 13, also ist n durch 7 und 13 teilbar,aber nicht durch 11.

Aufgabe 3.

a) Aus der ersten Gleichung folgt, dass x von der Form x = 1 + 2 · k1 mitk1 ∈ Z ist. Setze dies in der zweiten Gleichung ein und erhalte:

1 + 2k1 ≡ 1 (mod 3) ⇐⇒ 2k1 ≡ 0 (mod 3) ⇐⇒ k1 ≡ 0 (mod 3).

Damit folgt k1 = 3 ·k2 fur k2 ∈ Z und zusammen ergibt sich x = 1+2k1 =1 + 2 · (3k2) = 1 + 6k2. Daraus folgt, dass jedes x ∈ Z mit x ≡ 1 (mod 6)die Kongruenzgleichungen lost und dass dies die einzigen Losungen sind.

b) Verfahre wie in a):

2x ≡ 1 (mod 5) ⇐⇒ x ≡ 3 (mod 5) ⇐⇒ x = 3 + 5k1, k1 ∈ ZSetze dies in die nachste Gleichung ein:

3(3 + 5k1) ≡ 2 (mod 7)

⇐⇒ 15k1 ≡ −7 (mod 7)

⇐⇒ k1 ≡ 0 (mod 7)

⇐⇒ k1 = 7 · k2, k2 ∈ Z⇐⇒ x = 3 + 5 · (7k2) = 3 + 35k2

Und dies wiederum in die dritte Gleichung:

4(3 + 35k2) ≡ 1 (mod 11)

⇐⇒ 140k2 ≡ −11 (mod 11)

⇐⇒ 8k2 ≡ 0 (mod 11)

⇐⇒ k2 ≡ 0 (mod 11)

⇐⇒ k2 = 11 · k3, k3 ∈ Z⇐⇒ x = 3 + 35 · (11k3) = 3 + 385k3

Die Losungsmenge ist also die Restklasse der 3 modulo 385 = 5 · 7 · 11.

c) Die erste Gleichung heißt x = 31 + 41 · k1 mit k1 ∈ Z. Setze wieder ein:

31 + 41k1 ≡ 59 (mod 26)

⇐⇒ 41k1 ≡ 28 (mod 26)

⇐⇒ 15k1 ≡ 2 (mod 26)

Um das Inverse von 15 modulo 26 zu bestimmen, wenden wir den Eukli-dischen Algorithmus an:

26 = 1 · 15 + 11

15 = 1 · 11 + 4

11 = 2 · 4 + 3

4 = 1 · 3 + 1

Also gilt:

1 = 3 · 15 − 4 · 11 = 3 · 15 − 4 · (26 − 15) = 7 · 15 − 4 · 26.

Modulo 26 ergibt sich also 7 · 15 ≡ 1 (mod 26), also muss die obige Glei-chung mit 7 multipliziert werden:

15k1 ≡ 2 (mod 26) ⇐⇒ k1 ≡ 14 (mod 26) ⇐⇒ k1 = 14+26k2, k2 ∈ Z.

Setze dies ein:

x = 31 + 41 · (14 + 26k2) = 605 + 1066k2.

Also sind alle x ∈ Z mit x ≡ 605 (mod 1066) Losungen und dies sindauch die einzigen.

Aufgabe 4.

a) Wegen a|b ⇐⇒ b ≡ 0 (mod a) ist folgendes System von Kongruenzen zubetrachten:

n ≡ 0 (mod 9), n + 1 ≡ 0 (mod 16), n + 2 ≡ 0 (mod 25).

Lose dies wie in Aufgabe 3: Zunachst gilt n = 9 ·k1 fur k1 ∈ Z. Eingesetztliefert das:

9k1 ≡ −1 (mod 16) ⇐⇒ k1 ≡ −9 ≡ 7 (mod 16) ⇐⇒ k1 = 7+16k2, k2 ∈ Z.

Also n = 9 · (7 + 16k2) = 63 + 144k2. Eingesetzt folgt

63 + 144k2 ≡ −2 (mod 25)

⇐⇒ 19k2 ≡ 10 (mod 25)

⇐⇒ k2 ≡ 40 ≡ 15 (mod 25)

⇐⇒ k2 = 15 + 25k3, k3 ∈ Z⇐⇒ n = 63 + 144 · (15 + 25k3) = 2223 + 3600k3

Eine Moglichkeit ware also n := 2223.

b) Da die auftretenden Kongruenzen (hier 4, 9 und 16) nicht paarweise teiler-fremd sind, lasst sich der chinesische Restsatz nicht anwenden. In diesemFall sieht man recht leicht, dass es keine Losung gibt: Aus 16|(n+2) folgtn ≡ 14 (mod 16) bzw. n = 14 + 16k1. Betrachtet man dies modulo 4, soergibt sich:

n = 14 + 16k1 ≡ 2 (mod 4).

Daher kann ein n, welches die letzte Bedingung erfullt nie die erste erfullenund umgekehrt. Es gibt also kein n ∈ N, welches beide, geschweige dennalle drei, erfullt.