fermat kongruenz

Neue Frage »

04.05.2007, 13:32

chrissi

Auf diesen Beitrag antworten »

fermat kongruenz

ich soll die letzte ziffer von 3^100 berechnen mit hilfe der fermat kongruenz
wie muss ich den ansatz machen?

04.05.2007, 13:38

therisen

Auf diesen Beitrag antworten »

Hallo,

es ist doch $\begin{eqnarray*} \varphi(10) = 4 \end{eqnarray*}$ und $\begin{eqnarray*} 3^{100} = (3^{25})^4 \end{eqnarray*}$ . Darauf wende den Satz von Fermat-Euler an.

Gruß, therisen

04.05.2007, 13:43

sqrt4

Auf diesen Beitrag antworten »

Oder mit der Holzhackermethode (weniger elegant aber auch wirkungsvoll Big Laugh

).

$\begin{eqnarray*} 3^{100}=(3^2)^{50} \equiv (-1)^{50} \equiv -1 \equiv 9 \mod 10 \end{eqnarray*}$

04.05.2007, 13:54

therisen

Auf diesen Beitrag antworten »

Zitat:

Original von sqrt4
$\begin{eqnarray*} (-1)^{50} \equiv -1 \equiv 9 \mod 10 \end{eqnarray*}$

Was war doch gleich $\begin{eqnarray*} (-1)^{50} \end{eqnarray*}$ Big Laugh

04.05.2007, 13:58

chrissi

Auf diesen Beitrag antworten »

...
also ich bin so ran gegangen
$\begin{eqnarray*} \phi(10)=4 \end{eqnarray*}$
$\begin{eqnarray*} (3,10)=1 \end{eqnarray*}$
$\begin{eqnarray*} 3^4\equiv 1 mod 10 \end{eqnarray*}$
Da
$\begin{eqnarray*} 100 \equiv 0 mod4 \end{eqnarray*}$
$\begin{eqnarray*} \Rightarrow 3^{100} \equiv 3^0 \equiv 1 mod 10 \end{eqnarray*}$

04.05.2007, 14:04

therisen

Auf diesen Beitrag antworten »

Joa, ist OK so.

04.05.2007, 14:08

chrissi

Auf diesen Beitrag antworten »

und hier hab ich dann auch wirklich die farmat kongruenz mit eingebracht?
weil das is ja der spezialfall von der eulerschen kongruenz
und nur die eulersche kann ich sehen

04.05.2007, 14:33

sqrt4

Auf diesen Beitrag antworten »

Zitat:

Original von therisen

Zitat:

Original von sqrt4
$\begin{eqnarray*} (-1)^{50} \equiv -1 \equiv 9 \mod 10 \end{eqnarray*}$

Was war doch gleich $\begin{eqnarray*} (-1)^{50} \end{eqnarray*}$ Big Laugh

Sich einmischen und dann auch noch was falsches Schreiben Hammer

*schäm*
sorry war natürlich blödsinn was ich geschrieben hab. Da hat mich wohl der 5er am anfang irgenwie verwirrt Big Laugh

04.05.2007, 15:51

chrissi

Auf diesen Beitrag antworten »

eine andere aufgabe
hich habe zu zeigen dass

$\begin{eqnarray*} a^{13}= a \mod 273 \end{eqnarray*}$

04.05.2007, 16:42

sqrt4

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 273=13\cdot 7 \cdot 3 \end{eqnarray*}$

04.05.2007, 17:05

chrissi

Auf diesen Beitrag antworten »

tja das wusst ich au sind zwei 13 aber kann da nix mit anfangen

04.05.2007, 17:17

sqrt4

Auf diesen Beitrag antworten »

Zeige nacheinander die Teilbarkeit von $\begin{eqnarray*} a^{13}-a \end{eqnarray*}$ durch die jeweiligen Fakotren. Die Teilbarkeit durch 13 sollte dabei leicht fallen. (Kleiner Fermat)
Die anderen Fälle würde ich einfach durchprobieren. (Also die einzelenen Reste immer einsetzen und überprüfen ob es stimmt.)

Bsp: mit 3
$\begin{eqnarray*} a^{13}-a \end{eqnarray*}$

Wenn $\begin{eqnarray*} a \equiv 0 \mod 3 \end{eqnarray*}$ ist es einfach.
Wenn $\begin{eqnarray*} a \equiv 1 \mod 3 \end{eqnarray*}$ dann ist $\begin{eqnarray*} 1^{13}-1=0 \end{eqnarray*}$
und $\begin{eqnarray*} a \equiv 2 \equiv -1 \mod 3 \end{eqnarray*}$ also ist $\begin{eqnarray*} (-1)^{13}-(-1)=0 \end{eqnarray*}$

04.05.2007, 17:28

Auf diesen Beitrag antworten »

Zitat:

Original von sqrt4
Die anderen Fälle würde ich einfach durchprobieren.

Oder auch Fermat:

$\begin{eqnarray*} a^{13} = a^7\cdot a^6\equiv a\cdot a^6 = a^7\equiv a\mod 7 \end{eqnarray*}$

Allgemein ist leicht durch Induktion über $\begin{eqnarray*} k \end{eqnarray*}$ nachweisbar:

$\begin{eqnarray*} a^{k(p-1)+1} \equiv a\mod p \end{eqnarray*}$ für alle ganzen $\begin{eqnarray*} k\geq 1 \end{eqnarray*}$ und Primzahlen $\begin{eqnarray*} p \end{eqnarray*}$

04.05.2007, 17:35

sqrt4

Auf diesen Beitrag antworten »

Wie immer äußerst elegant.
Wieder was dazugelernt Big Laugh

04.05.2007, 17:56

chrissi

Auf diesen Beitrag antworten »

kapier den sinn nicht

04.05.2007, 18:01

sqrt4

Auf diesen Beitrag antworten »

Von was? Das man 273 zerlegt und die Teilbarkeit für die einzelnen Faktoren nachweist ?

04.05.2007, 18:23

Auf diesen Beitrag antworten »

Zitat:

Original von chrissi
kapier den sinn nicht

Das ist jammerschade, denn hier geht es um elementarste Grundlagen der Zahlentheorie, nämlich die Eindeutigkeit der Primfaktorzerlegung:

Wenn $\begin{eqnarray*} n = p_1^{e_1} \cdot \ldots \cdot p_r^{e_r} \end{eqnarray*}$ diese eindeutige Zerlegung von $\begin{eqnarray*} n \end{eqnarray*}$ ist, dann folgt wiederum auch aus der Eindeutigkeit der Primfaktorzerlegung:

Zitat:

Eine ganze Zahl $\begin{eqnarray*} z \end{eqnarray*}$ ist genau dann durch $\begin{eqnarray*} n \end{eqnarray*}$ teilbar, wenn $\begin{eqnarray*} z \end{eqnarray*}$ durch alle $\begin{eqnarray*} p_k^{e_k} \end{eqnarray*}$ für $\begin{eqnarray*} k=1,\ldots,r \end{eqnarray*}$ teilbar ist.

Und wenn man für $\begin{eqnarray*} z=x-y \end{eqnarray*}$ einsetzt und das ganze in Modulschreibweise formuliert, heißt das nix weiter als

Zitat:

$\begin{eqnarray*} x\equiv y\mod n \end{eqnarray*}$ gilt genau dann, wenn $\begin{eqnarray*} x\equiv y\mod p_k^{e_k} \end{eqnarray*}$ für $\begin{eqnarray*} k=1,\ldots,r \end{eqnarray*}$ gilt.

Ich würde sagen, erste oder maximal zweite Vorlesungsstunde Zahlentheorie.

Neue Frage »

Antworten »

fermat kongruenz

Verwandte Themen