Divisormatrizen
Von: blindmessenger
Datum: Do. 28. Dezember 2017 13:25:59
Thema: Mathematik


Divisormatrizen:

Für ungerade Zahlen lassen sich Divisormatrizen erzeugen, die eine Struktur aufweisen, aus der man bestimmte Eigenschaften schließen kann. Wie man diese Divisormatrizen erzeugt und was für Eigenschaften man daraus ableiten kann will ich euch in diesem Artikel näher bringen:

Zuerst definieren wir eine Matrix, die ich im folgenden Mersennematrix $M_M$ nennen will.


Definition Mersennematrix $M_M$:

Die Mersennematrix $M_M$ hat folgende Struktur

$\begin{align} M_{M}=
\begin{pmatrix}
1 & 3 & 7 & 15 & ... & \infty\\
5 & 11 & 23 & 47 & ... & \infty\\
9 & 19 & 39 & 79 & ... & \infty\\
13 & 27 & 55 & 111 & ... & \infty\\
\vdots & \vdots & \vdots & \vdots& \ddots& \vdots\\
\infty & \infty & \infty & \infty & ... & \infty\\
\end{pmatrix}\end{align}
$

Wie zu sehen besteht die erste Reihe aus den Mersennezahlen und wird in den weiteren Reihen logisch fortgeführt. Die Elemente der Mersennematrix $M_M$ ($m$-te Reihe und $n$-te Spalte) berechnen sich folgendermaßen:

$M(m,n) = (2m-1)\cdot 2^n - 1 \text{ mit } m,n \in \mathbb{N}_{> 0}$ stehen.

Diese Matrix hat folgende Eigenschaften:

Sie ist unendlich und es kommt jede ungerade Zahl genau einmal vor.

Die Mersenne-Matrix hat demnach den Aufbau

$M_M = \left(M_{mn} \right)_{(\infty \times \infty)}\text{ mit } M_{mn} = M(m,n)$

Nun lässt sich aus dieser Matrix für jede ungerade Zahl eine Divisormatrix $M_{di}$ berechnen.

Definition Divisormatrix $M_{di}$:

Für jede ungerade Zahl lässt sich eine Divisormatrix $M_{di}$ bilden indem man die Mersennematrix durch diese ungerade Zahl teilt. Die Anzahl der Reihen ist immer gleich der ungeraden Zahl. Die Anzahl der Spalten kann maximal gleich der ungeraden Zahl minus 1 sein oder auch weniger. Es richtet sich danach wann in der ersten Reihe das erste Mal eine Zahl durch die betrachtete ungerade Zahl teilbar ist.  

Beispiel Divisormatrix für die Zahl 7:

$\begin{align} M_{di}(7)=M_{M} \cdot \frac{1}{7}=
\begin{pmatrix}
\frac{1}{7} & \frac{3}{7} & \color{red}{1} \\
\frac{5}{7} & \frac{11}{7} & \frac{23}{7} \\
\frac{9}{7} & \frac{19}{7} & \frac{39}{7} \\
\frac{13}{7} & \frac{27}{7} & \frac{55}{7} \\
\frac{17}{7} & \color{red}{5} & \frac{71}{7}\\
\color{red}{3} &\frac{43}{7}  &\frac{87}{7}   \\
\frac{25}{7} & \frac{51}{7} & \frac{103}{7} \\
\end{pmatrix} \end{align}
$

Wie hier zu sehen hat die Divisormatrix von 7 also genau 7 Reihen. Die Anzahl der Spalten ist 3 weil in der ersten Reihe (Man könnte auch sagen "Mersennereihe"...) die dritte Zahl das erste Mal durch 7 teilbar ist.

Die Anzahl der Reihen $m$ und Spalten $n$ kann auch direkt berechnet werden. Es gilt:

Das kleinste $n$ welches diese Gleichung

$\begin{align} 2^n \ mod \ m=1 \end{align} $

erfüllt ist genau die Anzahl der Spalten.

Nun könnte man fragen warum diese Matrizen genau für diese Anzahl an Reihen und Spalten definiert sind. Hierfür schauen wir uns die Divisormatrix von 7 nochmal an, aber wir verdoppeln die Anzahl der Reihen und Spalten und highlighten die Zahlen die ganz bleiben:

$\begin{align}
\begin{pmatrix}
\frac{1}{7} & \frac{3}{7} & \color{red}{1} &|&\frac{15}{7} & \frac{31}{7} &  \color{red}{9}\\
\frac{5}{7} & \frac{11}{7} & \frac{23}{7} &|&\frac{47}{7} & \frac{95}{7} & \frac{191}{7} \\
\frac{9}{7} & \frac{19}{7} & \frac{39}{7} &| &\frac{79}{7} & \frac{159}{7} & \frac{318}{7}\\
\frac{13}{7} & \frac{27}{7} & \frac{55}{7} &|&\frac{111}{7} & \frac{223}{7} & \frac{447}{7} \\
\frac{17}{7} &  \color{red}{5} & \frac{71}{7} &|&\frac{143}{7} &  \color{red}{41} & \frac{575}{7}\\
 \color{red}{3} &\frac{43}{7}  &\frac{87}{7}  &| & \color{red}{25} &\frac{351}{7}  &\frac{703}{7} \\
\frac{25}{7} & \frac{51}{7} & \frac{103}{7} &|& \frac{207}{7} & \frac{415}{7} & \frac{831}{7}\\
--& -- & -- &| &-- & -- & -- \\
\frac{29}{7} & \frac{59}{7} &  \color{red}{17} &| &\frac{239}{7} & \frac{479}{7} &  \color{red}{137}\\
\frac{33}{7} & \frac{67}{7} & \frac{135}{7} &| &\frac{271}{7} & \frac{543}{7} & \frac{1087}{7}\\
\frac{37}{7} & \frac{75}{7} & \frac{151}{7} &| &\frac{303}{7} & \frac{607}{7} & \frac{1215}{7} \\
\frac{41}{7} & \frac{83}{7} & \frac{167}{7} &| &\frac{335}{7} & \frac{671}{7} & \frac{1343}{7}\\
\frac{45}{7} &  \color{red}{13} & \frac{183}{7} &|&\frac{367}{7} &  \color{red}{105} & \frac{1471}{7}\\
 \color{red}{7} &\frac{99}{7}  &\frac{199}{7}  &| & \color{red}{57} &\frac{799}{7}  &\frac{1599}{7} \\
\frac{53}{7} & \frac{107}{7} & \frac{215}{7} &|& \frac{431}{7} & \frac{863}{7} & \frac{1727}{7}\\
\end{pmatrix} \end{align}
$

Wie zu sehen ergibt sich bei Verdoppelung der Spalten und Reihen ein sich wiederholendes Muster an ganzen Zahlen. Das "Ganzzahlmuster" (also der sich wiederholende Bereich) ist dann genau die Divisormatrix. Man kann die Divisormatrizen also nach der obigen Defintion berechnen oder auch grafisch ermitteln...



Eigenschaften der Divisormatrizen:

An der Anzahl der Reihen und Spalten einer Divisormatrix lässt sich leicht erkennen, ob es sich bei der betrachteten Zahl um eine Primzahl oder fermatsche Pseudoprimzahl zur Basis 2 handelt. Es gilt folgendes:

Wenn für die Anzahl der Reihen $m$ und die Anzahl der Spalten $n$ gilt

$\begin{align} (m-1) \ mod \ n=0 \end{align} $

dann ist $m$ eine Primzahl oder eine Pseudoprimzahl zur Basis 2.

Beispiel 7:

$\begin{align} m=7, n=3 \end{align} $

$\begin{align}  (7-1) \ mod \ 3=0  \end{align}  $

An manchen Divisormatrizen lässt sich direkt ablesen ob es sich um eine Primzahl handelt. Wenn gilt

$\begin{align}  \frac{m-1}{n}=1  \end{align}  $

dann ist $m$ sicher prim. Es handelt sich dann um Primzahlen der Form A001122 (3,5,11,13,19,...).

Beispiel 11:

$\begin{align}
M_{di}(11)=\begin{pmatrix}
\frac{1}{11} & \frac{3}{11} & \frac{7}{11} &\frac{15}{11} & \frac{31}{11} &  \frac{63}{11}& \frac{127}{11} &\frac{255}{11} & \frac{511}{11} &  \color{red}{93}\\
\frac{5}{11} & \color{red}{1} & \frac{23}{11} &\frac{47}{11} & \frac{95}{11} & \frac{191}{11} & \frac{383}{11} &\frac{767}{11} & \frac{1535}{11} & \frac{3071}{11}\\
\frac{9}{11} & \frac{19}{11} & \frac{39}{11}  &\frac{79}{11} & \frac{159}{11} & \color{red}{29}& \frac{639}{11}  &\frac{1279}{11} & \frac{2559}{11} & \frac{5119}{11}\\
\frac{13}{11} & \frac{27}{11} & \color{red}{5} &\frac{111}{11} & \frac{223}{11} & \frac{447}{11} & \frac{895}{11} &\frac{1791}{11} & \frac{3583}{11} & \frac{7167}{11}\\
\frac{17}{11} & \frac{35}{11} & \frac{71}{11} &\color{red}{13} &  \frac{287}{11} & \frac{575}{11} & \frac{1151}{11} &\frac{2303}{11} & \frac{4607}{11} & \frac{9215}{11}\\
 \frac{21}{11} &\frac{43}{11}  &\frac{87}{11}   & \frac{175}{11}   &\frac{351}{11}  &\frac{703}{11}  &\frac{1407}{11}   & \frac{2815}{11} &\frac{5631}{11}  &\frac{11263}{11} \\
\frac{25}{11} & \frac{51}{11} & \frac{103}{11} & \frac{207}{11} & \frac{415}{11} & \frac{831}{11}& \frac{1663}{11} & \frac{3327}{11}  & \color{red}{605} & \frac{13311}{11}\\
\frac{29}{11} & \frac{59}{11} & \frac{119}{11}  &\frac{239}{11} & \frac{479}{11} &  \frac{959}{11}& \frac{1919}{11}  &\color{red}{349} & \frac{7679}{11} & \frac{15359}{11}\\
\color{red}{3} & \frac{67}{11} & \frac{135}{11}  &\frac{271}{11} & \frac{543}{11} & \frac{1087}{11}& \frac{2175}{11}  &\frac{4351}{11} & \frac{8703}{11} & \frac{17407}{11}\\
\frac{37}{11} & \frac{75}{11} & \frac{151}{11}  &\frac{303}{11} & \frac{607}{11} & \frac{1215}{11}& \color{red}{221}  &\frac{4863}{11} & \frac{9727}{11} & \frac{19455}{11} \\
\frac{41}{11} & \frac{83}{11} & \frac{167}{11} &\frac{335}{11} & \color{red}{61} & \frac{1343}{11}& \frac{2687}{11} &\frac{5375}{11} & \frac{10751}{11} & \frac{21503}{11}\\

\end{pmatrix} \end{align}
$

Auch bei Divisormatrizen der Form

$\begin{align}  \frac{m-1}{n}=2  \end{align}  $

ist $m$ immer prim. Es handelt sich dann um Primzahlen der Form A115591 (7,17,23,41,...).

Beispiel 17:

$\begin{align}
M_{di}(17)=\begin{pmatrix}
\frac{1}{17}  & \frac{3}{17}   & \frac{7}{17}    & \frac{15}{17}   & \frac{31}{17}   & \frac{63}{17}   & \frac{127}{17}   & \color{red}{15} \\
\frac{5}{17}  & \frac{11}{17}   & \frac{23}{17}   & \frac{47}{17}   & \frac{95}{17}   & \frac{191}{17}  & \frac{383}{17}   & \frac{767}{17}  \\
\frac{9}{17}  & \frac{19}{17}  & \frac{39}{17}   & \frac{79}{17}   & \frac{159}{17}  & \frac{319}{17}  & \frac{639}{17}   & \frac{1279}{17} \\
\frac{13}{17} & \frac{27}{17}  & \frac{55}{17}   & \frac{111}{17}  & \frac{223}{17}  & \frac{447}{17}  & \frac{895}{17}   & \frac{1791}{17} \\
\color{red}{1} & \frac{35}{17}  & \frac{71}{17}   & \frac{143}{17}   & \frac{287}{17}  & \frac{575}{17}  & \frac{1151}{17}  & \frac{2303}{17} \\
\frac{21}{17} & \frac{43}{17}  & \frac{87}{17}   & \frac{175}{17}  & \frac{351}{17}  & \frac{703}{17}  & \frac{1407}{17}  & \frac{2815}{17} \\
\frac{25}{17} & \color{red}{3}  & \frac{103}{17}  & \frac{207}{17}  & \frac{415}{17}  & \frac{831}{17}  & \frac{1663}{17}  & \frac{3327}{17} \\
\frac{29}{17} & \frac{59}{17}  & \color{red}{7}  & \frac{239}{17}  & \frac{479}{17}  & \frac{959}{17}  & \frac{1919}{17}  & \frac{3839}{17} \\
\frac{33}{17} & \frac{67}{17}  & \frac{135}{17}  & \frac{271}{17}  & \frac{543}{17}  & \frac{1087}{17} & \frac{2175}{17}  & \frac{4351}{17} \\
\frac{37}{17} & \frac{75}{17}  & \frac{151}{17}  & \frac{303}{17}  & \frac{607}{17}  & \frac{1215}{17} & \color{red}{143}  & \frac{4863}{17} \\
\frac{41}{17} & \frac{83}{17}  & \frac{167}{17}  & \frac{335}{17}  & \frac{671}{17}  & \color{red}{79} & \frac{2687}{17}  & \frac{5375}{17} \\
\frac{45}{17} & \frac{91}{17}  & \frac{183}{17}   & \frac{367}{17}  & \frac{735}{17}  & \frac{1471}{17}  & \frac{2943}{17}  & \frac{5887}{17} \\
\frac{49}{17} & \frac{99}{17}  & \frac{199}{17}  & \frac{399}{17}  & \color{red}{47}  & \frac{1599}{17}  & \frac{3199}{17}  & \frac{6399}{17} \\
\frac{53}{17} & \frac{107}{17}  & \frac{215}{17}  & \frac{431}{17}  & \frac{863}{17}  & \frac{1727}{17}  & \frac{3455}{17}  & \frac{6911}{17} \\
\frac{57}{17} & \frac{115}{17}  & \frac{231}{17}  & \frac{463}{17}  & \frac{927}{17}  & \frac{1855}{17} & \frac{3711}{17}  & \frac{7423}{17} \\
\frac{61}{17} & \frac{123}{17}  & \frac{247}{17}  & \frac{495}{17}  & \frac{991}{17}  & \frac{1983}{17} & \frac{3967}{17}  & \frac{7935}{17} \\
\frac{65}{17} & \frac{131}{17}  & \frac{263}{17}  & \color{red}{31}  & \frac{1055}{17}  & \frac{2111}{17} & \frac{4223}{17}  & \frac{8447}{17} \\

\end{pmatrix} \end{align}
$

Auch wenn das für den einen oder anderen nichts neues ist (Also warum diese Divisormatrizen genau so strukturiert sind...), finde ich es doch lohnenswert sich weiter mit diesen Matrizen zu beschäftigen. Wenn man weiß, dass für bestimmte Primzahlen immer die gleichen Divisormatrizenmuster auftreten, dann kann man daraus vielleicht Primzahltests entwickeln.


Dieser Artikel kommt von Matroids Matheplanet
http://matheplanet.com

Die Url für diesen Artikel ist:
http://matheplanet.com/default3.html?article=1816