Satz von Euler Anwendungsproblem

16.09.2014, 00:21

Benni91

Satz von Euler Anwendungsproblem

Meine Frage:
Hallo, ich knobele derzeit an folgender Aufgabe:

Verwende den Satz von Euler, um zu zeigen, dass 341 ein Teiler von $\begin{eqnarray*} 2^{341} - 2 \end{eqnarray*}$ ist.

Der einzige Satz, den wir bereits aus dem Satz von Euler abgeleitet haben, ist der kleine Satz von Fermat... daher nehme ich an, dass ich auch den verwenden darf.

Nun, wäre 341 eine Primzahl, so hätt sich die Aufgabe mittels Fermat selbst erledigt. Leider ist 341 = 11*31.

Meine Ideen:
Ich nehme an, dass 341 kein Teiler von $\begin{eqnarray*} 2^{341} - 2 \end{eqnarray*}$ ist. Dann ist also 11 oder 31 ebenfalls kein Teiler. Da beides primzahlen sind, ist also der entsprechende nicht-Teiler teilerfremd zu $\begin{eqnarray*} 2^{341} - 2 \end{eqnarray*}$ . Sprich es gilt:

$\begin{eqnarray*} ggt(2^{341} - 2,11) = 1 \end{eqnarray*}$ oder $\begin{eqnarray*} ggt(2^{341} - 2,31) = 1 \end{eqnarray*}$ .

Jetzt kann ich also den Satz von Euler anwenden, dh, es gilt:

$\begin{eqnarray*} (2^{341} - 2)^{10}\equiv 1 (mod 11) \end{eqnarray*}$ oder $\begin{eqnarray*} (2^{341} - 2)^{30}\equiv 1 (mod 31) \end{eqnarray*}$

Nun versuche ich, beide Aussagen zu einem Widerspruch zu führen... allerdings habe ich das gefühl, dass ich den falschen Ansatz habe :/

16.09.2014, 00:42

URL

Auf diesen Beitrag antworten »

RE: Satz von Euler Anwendungsproblem
benutze $\begin{align*} 2^{\varphi(341)} \equiv 1 \bmod 341 \end{align*}$

16.09.2014, 14:32

benni91

Auf diesen Beitrag antworten »

Naja es ist $\begin{eqnarray*} \varphi (341) = \varphi (11) * \varphi (31) = 10 * 30 = 300 \end{eqnarray*}$ , also $\begin{eqnarray*} 2^{300} \equiv 1 mod 341 \end{eqnarray*}$

Nun weiß ich also, dass $\begin{eqnarray*} 341 \mid 2^{300}-1 \end{eqnarray*}$ ... weiß allerdings nicht, in wie fern mir das hilft

16.09.2014, 15:50

HAL 9000

Auf diesen Beitrag antworten »

Nach Fermat ist $\begin{align*} 2^{340}-1 = 2^{34\cdot 10}-1 \end{align*}$ durch 11 teilbar.

Die Teilbarkeit durch 31 ist schon schwieriger, geht aber über einen kleinen "Trick": Es ist $\begin{align*} 2 \equiv 2+2\cdot 31 = 2^6\bmod 31 \end{align*}$ , daher folgt $\begin{align*} 2^{340}-1 \equiv 2^{68\cdot 30}-1\bmod 31 \end{align*}$ , und das ist nach Fermat durch 31 teilbar.

Es kommt also durchaus auch manchmal auf die Basis an: $\begin{align*} 3^{341}-3 \end{align*}$ ist zwar durch 11, aber nicht durch 31, und damit auch nicht durch 341 teilbar... smile

16.09.2014, 16:19

Benni91

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Nach Fermat ist $\begin{align*} 2^{340}-1 = 2^{34\cdot 10}-1 \end{align*}$ durch 11 teilbar.

Inwiefern sagt mir das Fermat? Also wir hatten den kleinen Satz von Fermat wie folgt:
Ist p eine Primzahl, so gilt $\begin{eqnarray*} p \mid (k^{p}-k) \end{eqnarray*}$ füer alle k.

16.09.2014, 16:28

HAL 9000

Auf diesen Beitrag antworten »

Naja, ich meine eine "andere" Formulierung von Fermat, die auch näher am Satz von Euler liegt:

Zitat:

Ist $\begin{align*} p \end{align*}$ eine Primzahl und $\begin{align*} k \end{align*}$ nicht durch $\begin{align*} p \end{align*}$ teilbar, so gilt $\begin{align*} p \mid (k^{p-1}-1) \end{align*}$

Über die Kongruenz

$\begin{align*} k^{n(p-1)} = \left(k^{p-1}\right)^n \equiv 1^n = 1 \bmod p \end{align*}$

lässt sich dann auch unmittelbar folgern

Zitat:

Ist $\begin{align*} p \end{align*}$ eine Primzahl und $\begin{align*} k \end{align*}$ nicht durch $\begin{align*} p \end{align*}$ teilbar, so gilt $\begin{align*} p \mid (k^{n(p-1)}-1) \end{align*}$ für beliebige natürliche Zahlen $\begin{align*} n \end{align*}$ .

Und genau das habe ich einmal für $\begin{align*} p=11,k=2,n=34 \end{align*}$ , sowie dann nochmal für $\begin{align*} p=31,k=2,n=68 \end{align*}$ genutzt.

16.09.2014, 16:38

Benni91

Auf diesen Beitrag antworten »

Ahhhh... damit ist dann alles klar. Nur hatten wir diese andere Formulierung von Fermat (noch) nicht, daher weiß ich nicht, ob ich das benutzen darf. Aber im Primzip ist da doch einfach nur einmal ein k rausgeteilt... also eigentlich sollte das dann in Ordnung sein. Danke dir smile

16.09.2014, 17:06

HAL 9000

Auf diesen Beitrag antworten »

Wie habt ihre denn den Sazu von Euler formuliert? Normalerweise ja ungefähr so:

Zitat:

Sind $\begin{align*} m,k \end{align*}$ teilerfremde natürliche Zahlen, so gilt $\begin{align*} m \mid \left( k^{\varphi(m)}-1 \right) \end{align*}$

Für Primzahlen $\begin{align*} m=p \end{align*}$ ist nur $\begin{align*} \varphi(p)=p-1 \end{align*}$ , und das ist dann genau die von mir zitierte erste Aussage.

16.09.2014, 22:50

URL

Auf diesen Beitrag antworten »

Die Idee war $\begin{align*} 2^{341} \bmod 341 = 2^{41}\bmod 341 \end{align*}$
und dann $\begin{align*} 2^{10} \equiv 1 \bmod 341 \end{align*}$ benutzen

17.09.2014, 08:05

HAL 9000

Auf diesen Beitrag antworten »

Allerdings: Wenn man $\begin{align*} 2^{10}\equiv 1\bmod 341 \end{align*}$ weiß (z.B. durch direkte Berechnung), dann hat man sofort

$\begin{align*} 2^{340} = \left( 2^{10} \right)^{34} \equiv 1\bmod 341 \end{align*}$ ,

und braucht Euler gar nicht mehr zur Argumentation. Augenzwinkern

17.09.2014, 21:39

URL

Auf diesen Beitrag antworten »

Da hast du natürlich sowas von Recht Hammer

Neue Frage »

Antworten »

Satz von Euler Anwendungsproblem

Verwandte Themen