4
Elementare Zahlentheorie Musterl¨ osungen Zettel 4 Aufgabe 1. a) Zun¨ achst gilt 10 ≡-1 (mod 11). Wegen der Vertr¨ aglichkeit der Kongru- enzen mit Multiplikation folgt 10 k (-1) k (mod 11) und aufgrund der Vertr¨ aglichkeit mit der Addition folgt die Behauptung: d k ·10 k +d k-1 ·10 k-1 +···+d 1 ·10+d 0 d k ·(-1) k +···+d 1 ·(-1)+d 0 (mod 11). Ist nun a eine Zahl und ihre Darstellung im Zehnersystem gegeben durch a = d k · 10 k + ··· + d 1 · 10 + d 0 mit 0 d i 9. (Hierbei wurde a 0 angenommen, da das Vorzeichen f¨ ur die Teilbarkeit durch 11 keine Rolle spielt.) Definiere die alternierende Quersumme von a durch folgende Regel: Q alt (a) := d 0 - d 1 + d 2 -··· +(-1) k d k . Dann gilt nach obiger Kongruenz stets a Q alt (a) (mod 11) und da- her ist die Zahl a genau dann durch 11 teilbar, wenn ihre alternierende Quersumme durch 11 teilbar ist. b) Sei b ein Palindrom mit einer geraden Anzahl an Ziffern. Formal bedeutet dies f¨ ur die Darstellung von b im Zehnersystem: b = d 2k-1 · 10 2k-1 + d 2k-2 · 10 2k-2 + ··· + d 1 · 10 + d 0 , mit 0 d i 9 f¨ ur alle i und d i = d j falls i + j =2k - 1. Betrachte die alternierende Quersumme von b: Q Alt (b)= d 0 -d 1 +d 2 -· · ·+(-1) 2k-1 d 2k-1 =(d 0 -d 2k-1 )+(d 2k-2 -d 1 )+··· =0. Aufgrund der Palindromeigenschaft ist jede der Klammern gleich 0, die Ziffern heben sich auf“. Aufgabe 2. Betrachte zu n die Darstellung von zur Basis b = 1000, also n = t k · 1000 k + t k-1 · 1000 k-1 + ··· + t 1 · 1000 + t 0 0 t i 999. Definiere dann f : durch f (n) := t 0 - t 1 + ··· +(-1) k · t k . Dies ist analog zur alternierenden Quersumme, nur dass hier die Basis 1000 gew¨ ahlt ist, d.h. es werden gewissermaßen 3er Packs“ von Ziffern in diese al- ternierende Quersumme aufgenommen. Der Betrag stellt sicher, dass der Wert eine nat¨ urliche Zahl ist, f¨ ur Teilbarkeitsaussagen ist das Vorzeichen ja unerheb- lich.

Elementare Zahlentheorie Musterl¨osungen Zettel 4 …ktent/elemloes04.pdf · Elementare Zahlentheorie Musterl¨osungen Zettel 4 Aufgabe 1. a) Zun¨achst gilt 10 ≡ −1 (mod 11)

  • Upload
    vantram

  • View
    214

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Elementare Zahlentheorie Musterl¨osungen Zettel 4 …ktent/elemloes04.pdf · Elementare Zahlentheorie Musterl¨osungen Zettel 4 Aufgabe 1. a) Zun¨achst gilt 10 ≡ −1 (mod 11)

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.

Page 2: Elementare Zahlentheorie Musterl¨osungen Zettel 4 …ktent/elemloes04.pdf · Elementare Zahlentheorie Musterl¨osungen Zettel 4 Aufgabe 1. a) Zun¨achst gilt 10 ≡ −1 (mod 11)

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.

Page 3: Elementare Zahlentheorie Musterl¨osungen Zettel 4 …ktent/elemloes04.pdf · Elementare Zahlentheorie Musterl¨osungen Zettel 4 Aufgabe 1. a) Zun¨achst gilt 10 ≡ −1 (mod 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.

Page 4: Elementare Zahlentheorie Musterl¨osungen Zettel 4 …ktent/elemloes04.pdf · Elementare Zahlentheorie Musterl¨osungen Zettel 4 Aufgabe 1. a) Zun¨achst gilt 10 ≡ −1 (mod 11)

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.