41|(2^20-1)

09.02.2006, 15:10	Brox	Auf diesen Beitrag antworten »
41\|(2^20-1) Wie beweist man 41\|(2^20-1)? Klar ist: 2^40 = 1 mod 41 und deshalb 41\|(2^40-1)=(2^20-1)(2^20+1) D.h. entweder teilt 41 die Zahl 2^20 - 1 oder 2^20 + 1. Beide gleichzeitig kann es nicht teilen denn sonst gilt 41\|2. Aber warum teilt 41 die Zahl 2^20 + 1 _nicht_?
09.02.2006, 17:22	Abakus	Auf diesen Beitrag antworten »
Einfach ausrechnen: $\begin{eqnarray} 2^5 \equiv 9~ mod~ 41 \end{eqnarray}$ , also: $\begin{eqnarray} 2^{10} \equiv~ 40~ mod~ 41 \end{eqnarray}$ , also: $\begin{eqnarray} 2^{20} \equiv 1~ mod~ 41 \end{eqnarray}$ , und das bedeutet ja: $\begin{eqnarray} (2^{20} - 1) \equiv 0~ mod~ 41 \end{eqnarray}$ . Grüße Abakus
09.02.2006, 18:03	AD	Auf diesen Beitrag antworten »
Nach Fermat gilt $\begin{eqnarray} 2^{20}\equiv (2+7\cdot 41)^{20} = 289^{20} = 17^{40} \equiv 1\mod 41 \end{eqnarray}$ Oder weniger geheimnisvoll: Wenn $\begin{eqnarray} a \end{eqnarray}$ quadratischer Rest modulo $\begin{eqnarray} p \end{eqnarray}$ ist (d.h. ein $\begin{eqnarray} b \end{eqnarray}$ mit $\begin{eqnarray} b^2\equiv a\mod p \end{eqnarray}$ existiert - hier a=2 und b=17), dann folgt aus dem kleinen Fermat sogar $\begin{eqnarray} a^{\frac{p-1}{2}} \equiv 1\mod p \end{eqnarray}$

1

Verwandte Themen