Zahlentheorie

Neue Frage »

19.03.2007, 15:53	frustriert	Auf diesen Beitrag antworten »
Zahlentheorie Hallo erstmal! Ich habe bei folgender Aufgabe ein Problem: Wieviele ganze Zahlen n mit $\begin{eqnarray} 1\leq n\leq 180\ und\ 117^{n} \equiv 117 mod (111337) \end{eqnarray}$ existieren? Ich habe dies umgeformt: $\begin{eqnarray} 7^{n} \equiv 7 mod 11 \end{eqnarray}$ $\begin{eqnarray} 117^{n} \equiv 0 mod 13 \end{eqnarray}$ $\begin{eqnarray} 6^{n} \equiv 6 mod 37 \end{eqnarray}$ Leider weiß ich jetzt nicht mehr weiter. Kann mir bitte jemand helfen?
19.03.2007, 18:47	AD	Auf diesen Beitrag antworten »
Du hast vollkommen richtig angefangen, bevor dich dann leider der Mut verlassen hast. Also: Ein Exponent $\begin{eqnarray} n \end{eqnarray}$ muss alle drei Bedingungen erfüllen, damit die Anfangskongruenz erfüllt ist. Fangen wir mit der einfachsten Teilkongruenz an, der zweiten: Die ist wegen $\begin{eqnarray} 13 \| 117 \end{eqnarray}$ offensichtlich für alle $\begin{eqnarray} n\geq 1 \end{eqnarray}$ erfüllt, ist also im eigentlichen Sinn keine Einschränkung. Zur ersten, umgeformt $\begin{eqnarray} 7^{n-1} \equiv 1\mod 11 \end{eqnarray}$ . Nach dem kleinen Fermat gilt ja $\begin{eqnarray} 7^{10}\equiv 1\mod 11 \end{eqnarray}$ , allerdings kann es auch schon für kleinere Exponenten passieren, insbesondere sind da die Teiler von 10 zu untersuchen, als da wären 2 und 5. $\begin{eqnarray} 7^2 = 49 \equiv 5\mod 11 \end{eqnarray}$ scheidet aus, $\begin{eqnarray} 7^5 \equiv 5^2\cdot 7 \equiv -1\mod 11 \end{eqnarray}$ ebenfalls. Also ist $\begin{eqnarray} d=10 \end{eqnarray}$ tatsächlich die kleinste positive Lösung von $\begin{eqnarray} 7^d\equiv 1\mod 10 \end{eqnarray}$ , und alle anderen Lösungen wie z.B. $\begin{eqnarray} (n-1) \end{eqnarray}$ müssen Vielfache davon sein. Beim dritten verhält es sich so ähnlich, also $\begin{eqnarray} 6^{36}\equiv 1\mod 37 \end{eqnarray}$ , nur dass man hier bei einem viel kleineren $\begin{eqnarray} d \end{eqnarray}$ für $\begin{eqnarray} 6^d\equiv 1\mod 37 \end{eqnarray}$ fündig wird. EDIT: Rechtschreibfehler...
19.03.2007, 20:49	frustriert	Auf diesen Beitrag antworten »
Ach so, Danke für den Tip! Bei $\begin{eqnarray} 6^{d} \end{eqnarray}$ gilt dies schon für d = 4 und deren Vielfachen. Stimmt es dann, dass laut chin. Restsatz 1818045 Lösungen ganzer Zahlen existieren?
19.03.2007, 20:51	AD	Auf diesen Beitrag antworten »
Wie kommst du denn darauf? Hier geht es doch konkret um die Lösungen innerhalb des Intervalls $\begin{eqnarray} 1\leq n\leq 180 \end{eqnarray}$ , und das können ja wohl maximal 180 sein.
19.03.2007, 20:58	frustriert	Auf diesen Beitrag antworten »
Ach so, ja klar. Hatte für jede Kongruenz $\begin{eqnarray} 1 \leq n \leq 180 \end{eqnarray}$ Lösungen bestimmt und dann zusammengesetzt. Dann können es aber somit nur 180 Lösungen sein, oder?
19.03.2007, 21:14	AD	Auf diesen Beitrag antworten »
Für ein konkretes $\begin{eqnarray} n \end{eqnarray}$ gibt es doch nur die Möglichkeiten "Ist Lösung" oder "Ist keine Lösung" - insofern verstehe ich dich nicht so recht... Zurück zum Problem, wo wir gerade stehen geblieben waren: $\begin{eqnarray} 7^{n-1}\equiv 1\mod 11 \end{eqnarray}$ hat die Lösungen $\begin{eqnarray} n-1\equiv 0\mod 10 \end{eqnarray}$ , und $\begin{eqnarray} 6^{n-1}\equiv 1\mod 37 \end{eqnarray}$ entsprechend $\begin{eqnarray} n-1\equiv 0\mod 4 \end{eqnarray}$ . Was ist dann die gemeinsame Lösung?
Anzeige

19.03.2007, 21:50	frustriert	Auf diesen Beitrag antworten »
Kann sein, dass ich gerade auf der Leitung stehe... Es heisst doch aber in der Aufgabenstellung "wieviele ganze Zahlen n existieren" Ist gemeinsame Lösung n = k*21?
19.03.2007, 21:57	AD	Auf diesen Beitrag antworten »
Nein, sondern $\begin{eqnarray} n=20k+1 \end{eqnarray}$ , das ist was anderes. Jetzt musst du nur noch zählen, wieviele dieser Zahlen im Intervall $\begin{eqnarray} [1,180] \end{eqnarray}$ liegen.
19.03.2007, 22:02	frustriert	Auf diesen Beitrag antworten »
Danke! Das müssten dann 8 Zahlen sein! Schönen Abend noch!

Neue Frage »

Antworten »

Zahlentheorie

Verwandte Themen