Zahlentheorie¶
Restsysteme¶
Erläutere
Wolke-Skript (s.o.) S. 9
Bei Division durch eine feste Zahl m bilden die kleinsten nichtnegativen Reste eine m–periodische Folge.
Beispiele
$ 4 \mod 3 = 1 $
Kongruenzrelation
bzw.
$ a $ und $ b $ sind kongruent modulo m, wenn $ m|b-a $ bzw. wenn $ b = a+gm $ ist (für irgend ein $ g $ ).
Beispiele
$ 14 \equiv 2 (12) $
$ 17 \equiv 2(3) $
Folgerungen
Falls $ m = p $ eine Primzahl ist, gilt
Hinweise für den Beweis
Unter den Voraussetzungen $ a \equiv a'(m) $ und $ b \equiv b' (m) $ folgt $ ab \equiv a'b'(m) $.
Und für die andere Richtung gilt $ ca \equiv cb(m) \Rightarrow a \equiv b(\frac{m}{(c,m)} ) $, wofür man gut $ c|ab $ und $ (c,b)=1 \Rightarrow c|a $ gebrauchen kann.
Teilbarkeitsregeln¶
Zehnersystem
Wir stellen unsere Zahlen üblicherweise im 10er-System dar, was bedeutet, dass wir uns dafür 10 Ziffern $ 0 \leq a_v < 10 $ nehmen, und sie mit einem Vielfachen von $ 10 $ multiplizieren und diese $ k+1 $ Produkte summieren.
Mit Hilfe der Kongruenzrelation können wir jetzt Teilbarkeitsregeln beweisen.
Zum Beispiel ist eine (natürliche) Zahl durch $ 11 $ teilbar, wenn ihre alternierende Summe durch $ 11 $ teilbar ist.
Teilbar durch 11
$ 11|n \Leftrightarrow 11|a_0-a_1+a_2-...+(-1)^k a_k $
Lösung
$ 11|n \Leftrightarrow n \equiv 0(11) $ (Def. Kongruenzrelation)
$ \Leftrightarrow a_0 + 10 a_1 + ... + 10^k a_k \equiv 0(11) $ (Def. 10er-System)
$ \Leftrightarrow a_0-a_1+a_2-...+(-1)^k a_k \equiv 0(11) $
Der letzte Schritt folgt aus
$ 10^{2v} \equiv 1(11) $ und $ 10^{2v+1} \equiv -1 (11)$
Und das wiederum können wir begründen mit
$ 10 \equiv -1 (11) $ und obiger Folgerung (von links nach rechts genügt):
$ 100 = 10 \cdot 10 \equiv 10 \cdot (-1) \equiv (-1)(-1) = 1 (11) $ usw.
Spiegelzahlen
$ n^{ \star} $ heiße Spiegelzahl, also z.B. $ 123^{ \star} = 321 $.
Sei n eine Zahl eine 3-stellige natürliche Zahl mit paarweise verschiedenen Ziffern, $ n^{ \star} < n $ und $ m := n-n^{ \star} $. Dann gilt $ m + m^{ \star} = 1089 $.
RSA-Verfahren¶
S. 19