Aufgabe zu Primzahlen

11.11.2017, 01:05

Snexx_Math

Aufgabe zu Primzahlen

Fur eine Zahl $\begin{eqnarray*} m\in\mathbb N \end{eqnarray*}$ und eine Primzahl p definieren wir den p-Anteil $\begin{eqnarray*} m_p \end{eqnarray*}$ von m als die
größte natürliche Zahl der Form $\begin{eqnarray*} p^{l} \end{eqnarray*}$ die m teilt.
Seien p eine Primzahl, k $\begin{eqnarray*} \in\mathbb N \end{eqnarray*}$ und n $\begin{eqnarray*} \in\mathbb N \end{eqnarray*}$ , so dass n nicht von p geteilt wird. Zeigen Sie:
a) Es gilt jp =((n-1) $\begin{eqnarray*} p^{k} \end{eqnarray*}$ +j) $\begin{eqnarray*} _p \end{eqnarray*}$ für alle natürlichen Zahlen j = 1, . . . , $\begin{eqnarray*} p^{k} \end{eqnarray*}$ .

b)
Es gilt: p $\begin{eqnarray*} \nmid \end{eqnarray*}$ $\begin{eqnarray*} \begin{pmatrix} p^{k}*n \\ p^{k} \end{pmatrix} \end{eqnarray*}$

11.11.2017, 11:27

HAL 9000

Auf diesen Beitrag antworten »

Schreiben wir zunächst mal a) so auf, wie es wirklich gemeint ist:

Zitat:

a) Es gilt $\begin{align*} j_p =\left( (n-1)p^k+j\right)_p \end{align*}$ für alle natürlichen Zahlen $\begin{align*} j=1,\ldots,p^k \end{align*}$ .

Wie sieht man das?

Klar ist $\begin{align*} j \equiv (n-1)p^k+j \bmod p^k \end{align*}$ und damit auch unmittelbar $\begin{align*} j \equiv (n-1)p^k+j \bmod p^i \end{align*}$ für alle $\begin{align*} i=1,\ldots,k \end{align*}$ . D.h., für diese Exponenten $\begin{align*} i \end{align*}$ ist $\begin{align*} j \end{align*}$ genau dann durch $\begin{align*} p^i \end{align*}$ teilbar, wenn dies auch auf $\begin{align*} (n-1)p^k+j \end{align*}$ zutrifft.

Andererseits können beide Seiten auch nicht durch eine größere Potenz von $\begin{align*} p \end{align*}$ , also durch $\begin{align*} p^{k+1} \end{align*}$ teilbar sein: Für $\begin{align*} 1\leq j\leq p^k \end{align*}$ , und bei $\begin{align*} (n-1)p^k < (n-1)p^k+j < np^k \end{align*}$ für $\begin{align*} j\neq p^k \end{align*}$ ist das offensichtlich. Lediglich im Fall $\begin{align*} j=p^k \end{align*}$ haben wir rechts $\begin{align*} (n-1)p^k+j = np^k \end{align*}$ stehen, was aber auch nicht durch $\begin{align*} p^{k+1} \end{align*}$ teilbar ist wegen der Voraussetzung $\begin{align*} p\not\mid n \end{align*}$ .

Damit gibt es für jedes in Frage kommende $\begin{align*} j \end{align*}$ genau eine Zahl $\begin{align*} r \end{align*}$ mit $\begin{align*} 0\leq r\leq k \end{align*}$ , welche die Eigenschaften $\begin{align*} p^r \mid j \end{align*}$ und $\begin{align*} p^r \mid \left( (n-1)p^k+j \right) \end{align*}$ sowie $\begin{align*} p^{r+1} \not\mid j \end{align*}$ und $\begin{align*} p^{r+1} \not\mid \left( (n-1)p^k+j \right) \end{align*}$ hat, und das bedeutet nichts weiter als $\begin{align*} j_p=r \end{align*}$ und $\begin{align*} \left( (n-1)p^k+j \right)_p = r \end{align*}$ .

b) ist lediglich eine Folgerung von a), basierend auf $\begin{align*} \binom{np^k}{p^k} = \frac{\prod\limits_{i=0}^{p^k-1} \left(np^k-i\right)}{\left(p^k\right)!} = \frac{\prod\limits_{j=1}^{p^k} \left((n-1)p^k+j\right)}{\prod\limits_{j=1}^{p^k} j} \end{align*}$ .

P.S.: Die "Sonderrolle" von $\begin{align*} j=p^k \end{align*}$ machte oben ja die Forderung $\begin{align*} p\not\mid n \end{align*}$ nötig. Unter Verzicht auf letztere Forderung gilt dann aber immer noch $\begin{align*} p \not\mid \binom{np^k-1}{p^k-1} \end{align*}$ . Augenzwinkern