Zahlendreieck

17.01.2019, 18:11

Ukex

Zahlendreieck

Meine Frage:
Man nimmt Zwei zahlen. Einmal p (irgendeine Primzahl) und n = p?s + 1 .
Nun schreibt man n Reste modulo p in eine Reihe. Darunter werden n-1 Zahlen nach der folgenden vorschrift geschrieben: unter die Reste x, y kommt die Zahl
(p-x)+(p-y)modulo p. Danach eine Reihe aus n-2 Zahlen usw. bis sich nach der Gerechnung von n-1 neuen Reihen ein Dreieck gebildet hat.

Ein Beispiel währe mit p=5 und n=6:
4 4 1 1 3 1
2 0 3 1 1
3 2 1 3
0 2 1
3 2
0

Um auf die unterste Zahl zu kommen muss man sich nur die beiden äußeren Zahlen anschauen also (5-4)+(5-1)mod5 = 0

D.h. die anderren Zahlen fallen alle weg. Nun zu meiner Frage.

In dem Buch aus dem ich das habe steht

"Und die Zahlen dazwischen, also die an den Positionen 2 bis n-1, fallen weg. Nach der Reise hat die k-te Zahl nähmlich den Faktor (n-1 über k-1)"

Wie kommt man darauf bzw. was genau bedeutet das?

Vielen Dank im Voraus

Meine Ideen:
Ich habe keine Ahnung wie man darauf kommt.

18.01.2019, 06:36

Ukex

Auf diesen Beitrag antworten »

RE: Zahlendreieck
Ich meine n=p hoch s + 1

18.01.2019, 08:10

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Ukex
"Und die Zahlen dazwischen, also die an den Positionen 2 bis n-1, fallen weg. Nach der Reise hat die k-te Zahl nähmlich den Faktor (n-1 über k-1)"

Im Klartext:

Stehen in der Kopfzeile die $\begin{eqnarray*} n \end{eqnarray*}$ Zahlen $\begin{eqnarray*} a_0,a_1,\ldots,a_{n-1} \end{eqnarray*}$ , so bekommt man über den beschriebenen Bildungsprozess $\begin{eqnarray*} x,y\mapsto (p-x)+(p-y)\bmod p = -(x+y)\bmod p \end{eqnarray*}$ am Ende den Wert $\begin{eqnarray*} (-1)^{n-1}\sum_{k=0}^{n-1} \binom{n-1}{k} a_k\bmod p \end{eqnarray*}$ .

Im Fall $\begin{eqnarray*} n=p^s+1 \end{eqnarray*}$ sind aber die Koeffizienten $\begin{eqnarray*} \binom{n-1}{k} = \binom{p^s}{k} \end{eqnarray*}$ für $\begin{eqnarray*} k=1,2,\ldots,p^s-1 \end{eqnarray*}$ sämtlich durch $\begin{eqnarray*} p \end{eqnarray*}$ teilbar (versuch das zu beweisen!), damit hat man am Ende nur noch $\begin{eqnarray*} (-1)^{n-1}\left(a_0+a_{n-1}\right)\bmod p \end{eqnarray*}$ stehen. Für ungerade Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$ ist $\begin{eqnarray*} (-1)^{n-1} = (-1)^{p^s} = -1 \end{eqnarray*}$ , und für $\begin{eqnarray*} p=2 \end{eqnarray*}$ gilt sowie immer $\begin{eqnarray*} a\equiv -a\bmod 2 \end{eqnarray*}$ , daher ist das Ergebnis stets $\begin{eqnarray*} -\left(a_0+a_{n-1}\right)\bmod p = \left(p-a_0\right)+\left(p-a_{n-1}\right)\bmod p \end{eqnarray*}$ .

P.S.: $\begin{eqnarray*} m=p^s \end{eqnarray*}$ sind übrigens die einzigen Zahlen, die diese Eigenschaft haben, dass für sämtliche $\begin{eqnarray*} k=1,2,\ldots,m-1 \end{eqnarray*}$ die Teilbarkeit $\begin{eqnarray*} p\mid \binom{m}{k} \end{eqnarray*}$ besteht, für alle anderen $\begin{eqnarray*} m \end{eqnarray*}$ mit dann $\begin{eqnarray*} p^s < m < p^{s+1} \end{eqnarray*}$ ist z.B. $\begin{eqnarray*} k=p^s \end{eqnarray*}$ ein Gegenbeispiel, d.h., es gilt $\begin{eqnarray*} p\nmid\binom{m}{p^s} \end{eqnarray*}$ .

Neue Frage »

Antworten »

Zahlendreieck

Verwandte Themen