TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 61

Sei n eine beliebige positive natürliche Zahl und $N=12n-1$. Man zeige, dass die Summe aller Teiler von N durch 12 teilbar ist

Lösungsvorschlag

Ansatz

Als erstes muss man sich überlegen, dass man die Zahl N als Produkt zweier Zahlen $a,b\in \mathbb {N}$ darstellen kann.

D.h. $12n-1=N=a\cdot b$

a und b sind dabei zwei Teiler von N.

Nun kann man dieses Beispiel aber auch als Restklassenrechnung betrachten. Nachdem die Teilbarkeit durch 12 gefragt ist wählen wir den Modul = 12.

daraus folgt:
$12n-1\equiv {\overline {11}}\mod 12$
und andererseits auch
$a\cdot b\equiv {\overline {11}}\mod 12$

Jetzt sehen wir uns einmal die Lösungen für diese Gleichung an. Theoretisch konnte man jetzt einfach von 0 bis 10 für a einsetzen und dann b berechnen. Wenn man aber weiß, dass Gleichungen der Form

$a\cdot x\equiv b\mod m$

nur dann lösbar sind, wenn ggT(a, m) ein Teiler von b ist, muss man nur noch 1, 5, 7, 11 untersuchen.

Lösen der Kongruenz

a = 1

$1\cdot b\equiv {\overline {11}}\mod 12$
es ist in dem Fall leicht zu erkennen, dass hier b = 11 ist

a = 5

$5\cdot b\equiv {\overline {11}}\mod 12\Rightarrow 5\cdot b=12\cdot q+11\Rightarrow 12\cdot q-5\cdot b=-11$
man bemühe hier den Eukliden Algorithmus:

$12=5\cdot 2+2$
$5=2\cdot 2+1$

nun multiplizert man die letzte Zeil mit 11:

$5=2\cdot 2+1\qquad |\cdot 11$
$5\cdot 11=2\cdot 22+11$

aus der ersten Zeile drückt man 2 aus:

$12=5\cdot 2+2\Rightarrow 2=12-5\cdot 2$

und setzt sie ein die vorherige Gleichung ein

$5\cdot 11=(12-5\cdot 2)\cdot 22+11$
$5\cdot 11=12\cdot 22-5\cdot 44+11$
$5\cdot 55-12\cdot 22=11$
$12\cdot (-22)+5\cdot 55=11$

verglichen mit

$12\cdot q-5\cdot b=-11$

folgt $b=55={\overline {7}}\mod 12$

Folgerungen aus den Lösungen der Kongruenz

Wie man gesehen hat, gibt es also genau zwei Lösungen für diese Kongruenz:

$a={\overline {1}}$ und $b={\overline {11}}$ bzw
$a={\overline {5}}$ und $b={\overline {7}}$

D.h. dass alle Teiler von N durch 1, 11, 5 oder 7 teilbar sind, wobei aber auch immer nur die "Teilerpaare" (1,11) und (5,7) (bzw. vielfache von diesen) auftreten. Man beachte dass das hier alles Primzahlen sind und daher auch keine weiteren Teiler zu erwarten sind.

Die Summer des "Teilerpaars" ${\overline {1}}+{\overline {11}}={\overline {12}}={\overline {0}}$ ist was offensichtlich durch 12 teilbar ist.

Deto für ${\overline {5}}+{\overline {7}}={\overline {12}}={\overline {0}}$ ebenfalls durch 12 teilbar.

D.h. wiederum, egal wieviele Teiler die Zahl N hat, die Teiler treten nur in den oben genannten "Teilerpaaren" auf die immer durch 12 teilbar sind.

Daher ist auch die Summe aller Teiler durch 12 teilbar, was zu beweisen war.

Lösungsansatz aus einem früheren Semester

Nur zur Info, und Gedankenanstoß. Man folge diesem Link