Zum Inhalt

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

a \equiv b(m)

bzw.

a \equiv b \bmod m

$ 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

a \equiv b (p) \Leftrightarrow ca \equiv cb (p)
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.

n = \sum_{v = 0}^{k} a_v 10^v

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.

Teilbarkeitsregeln

Beweise einige Teilbarkeitsregeln

Manche Beweise

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 $.

Beweis

RSA-Verfahren

S. 19