Lsg. einer Gl. in Z mod 101

01.12.2012, 11:19

Stefan03

Auf diesen Beitrag antworten »

Lsg. einer Gl. in Z mod 101

Hi,

ich stehe hier vor einem kleinen Problem bei einer Aufgabe:

Frage: gibt es ein x aus Z, sodass

$\begin{eqnarray*} x^{101}-(x+1)^{101}+x^2-47=0 mod 101 \end{eqnarray*}$

Diese Gleichung kann man ja so umformen, dass sich die Frage nach
$\begin{eqnarray*} x^2-47=0 mod 101 \end{eqnarray*}$ ergibt, weil 101 immer ein Teiler von $\begin{eqnarray*} \binom{101}{k} \end{eqnarray*}$ ist für alle k außer 0 und für k=0 fällt das $\begin{eqnarray*} x^{101} \end{eqnarray*}$ raus.

Also:
$\begin{eqnarray*} x^2-47=0 mod 101 \end{eqnarray*}$ , d.h. $\begin{eqnarray*} 101|x^2-47 \end{eqnarray*}$ , d.h. es gibt k aus Z, sodass $\begin{eqnarray*} k*101=x^2-47 \end{eqnarray*}$

Meiner Meinung gibt es kein solches k, aber wie zeige ich das sauber?

01.12.2012, 11:28

tmo

Auf diesen Beitrag antworten »

Ich komme eher auf $\begin{eqnarray*} x^2-48 \equiv 0 \pmod{101} \end{eqnarray*}$ .

Sagt dir das Legendresymbol etwas?

01.12.2012, 13:09

Stefan03

Auf diesen Beitrag antworten »

Hi,
ah, ja, stimmt...wg. dem $\begin{eqnarray*} -1^{101} \end{eqnarray*}$

Nein, das Legendre-Symbol sagt mir nichts...

01.12.2012, 14:45

tmo

Auf diesen Beitrag antworten »

Das macht die Aufgabe natürlich etwas schwieriger.

Zunächst ist die Lösbarkeit von $\begin{eqnarray*} x^2 \equiv 48 \pmod {101} \end{eqnarray*}$ natürlich äquivalent zu der Lösbarkeit von $\begin{eqnarray*} x^2 \equiv 3 \pmod {101} \end{eqnarray*}$ .

Wenn es eine Lösung gibt, dann gibt es eine Lösung in $\begin{eqnarray*} \{1, 2, \dotsc, 50\} \end{eqnarray*}$ .

Wegen $\begin{eqnarray*} 50^2 = 2500 \end{eqnarray*}$ reicht es daher, sich davon zu überzeugen, dass $\begin{eqnarray*} 101k+3 \end{eqnarray*}$ für $\begin{eqnarray*} 0 \leq k \leq 25 \end{eqnarray*}$ keine Quadratzahl ist.

Alternativ berechnest du $\begin{eqnarray*} 3^{50} \pmod {101} \end{eqnarray*}$ .

Wegen $\begin{eqnarray*} 3^8 \equiv -4 \pmod{101} \end{eqnarray*}$ geht das auch noch ganz gut im Kopf.

01.12.2012, 17:04

Stefan03

Auf diesen Beitrag antworten »

Zitat:

Original von tmo

Zunächst ist die Lösbarkeit von $\begin{eqnarray*} x^2 \equiv 48 \pmod {101} \end{eqnarray*}$ natürlich äquivalent zu der Lösbarkeit von $\begin{eqnarray*} x^2 \equiv 3 \pmod {101} \end{eqnarray*}$ .

Wenn es eine Lösung gibt, dann gibt es eine Lösung in $\begin{eqnarray*} \{1, 2, \dotsc, 50\} \end{eqnarray*}$ .

Alternativ berechnest du $\begin{eqnarray*} 3^{50} \pmod {101} \end{eqnarray*}$ .

Hi,

diese Schritte sind mir leider nicht klar...Wie kommst du darauf, dass es das gleiche ist wie $\begin{eqnarray*} 3 mod 101 \end{eqnarray*}$ ? Und warum die Lsg. dann zw. 1 und 50?!?

Zitat:

Original von tmo
Wegen $\begin{eqnarray*} 3^8 \equiv -4 \pmod{101} \end{eqnarray*}$ geht das auch noch ganz gut im Kopf.

Diesen Schritt verstehe ich dann schon wieder..

01.12.2012, 17:20

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Stefan03
Wie kommst du darauf, dass es das gleiche ist wie $\begin{eqnarray*} 3 mod 101 \end{eqnarray*}$ ?

$\begin{eqnarray*} 48 = 3\cdot 4^2 \end{eqnarray*}$

Das bedeutet, dass 48 genau dann quadratischer Rest modulo 101 ist, wenn dies auch auf 3 zutrifft.

Zitat:

Original von Stefan03
Und warum die Lsg. dann zw. 1 und 50?!?

Es gibt modulo 101 ja nur die Reste -50,-49,...,49,50, wobei 0 sicher nicht der gesuchte Rest ist. Und dann ist ja noch $\begin{eqnarray*} (-x)^2 = x^2 \end{eqnarray*}$ .

Anzeige

01.12.2012, 17:50

tmo

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
Wegen $\begin{eqnarray*} 3^8 \equiv -4 \pmod{101} \end{eqnarray*}$ geht das auch noch ganz gut im Kopf.

Ich hätte übrigens eher schreiben sollen, dass man das ganz gut mit Stift und Papier in kurzer Zeit hinkriegt. Das nur im Kopf zu machen bedarf schon sehr sehr großer Konzentration.

01.12.2012, 19:06

Stefan03

Auf diesen Beitrag antworten »

Hi,

so, also verstehe ich das richtig:

da $\begin{eqnarray*} 3^8 \equiv -4 \pmod{101} \end{eqnarray*}$ ist $\begin{eqnarray*} 3^{50}={3^{8}}^{6} \cdot 3^2 \equiv (-4)^{6}\cdot 3^2 \pmod{101} \equiv 1 \pmod{101} \end{eqnarray*}$

Und weil $\begin{eqnarray*} 1 \ne 0 \end{eqnarray*}$ in mod 101 hat die Gleichung keine Lösung?

Nochmal zum Verständis: Ich rechne $\begin{eqnarray*} 3^{50} = 48^{50} \pmod {101} \end{eqnarray*}$ , weil die Lsg. irgendwas zw. 1 und 50 sein muss und ich rechne deshalb mit der höchsten Potenz, weil wenn es eine "niedrigere" Lsg. geben würde. wäre sie ja da enthalten?!?

01.12.2012, 19:10

tmo

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 3^{50} \equiv 1 \pmod {101} \end{eqnarray*}$ ist falsch.

Wenn du richtig rechnest, erhältst du $\begin{eqnarray*} 3^{50} \equiv -1 \pmod {101} \end{eqnarray*}$ .

Aber abgesehen davon scheinst du diesen Ansatz völlig missverstanden haben: Der war eher so gedacht:

Wäre $\begin{eqnarray*} x^2 \equiv 3 \pmod{101} \end{eqnarray*}$ , so wäre nach dem kleinen Fermat $\begin{eqnarray*} 3^{50} = x^{100} \equiv 1 \pmod{101} \end{eqnarray*}$ .

D.h. durch das Nachrechnen von $\begin{eqnarray*} 3^{50} \equiv -1 \pmod {101} \end{eqnarray*}$ kann man zeigen, dass es eben keine Lösung gibt.

01.12.2012, 19:21

Stefan03

Auf diesen Beitrag antworten »

Ah, ok, ja, jetzt versteh ich das auch smile

smile

Ein paar Sätze zu kennen ist immer sehr hilfreich smile

smile

Stimmt das zumidenst?

$\begin{eqnarray*} 3^{50}={3^{8}}^{6} \cdot 3^2 \equiv (-4)^{6}\cdot 3^2 \pmod{101} \end{eqnarray*}$

edit: habs doch geschafft, es richtig nachzurechnen...PC Taschenrechner wollte meine Klammer nicht, aber man hätte es auch merken können, dass (-4)^6 positiv sein muss....

01.12.2012, 19:23

tmo

Auf diesen Beitrag antworten »

Die Zeile stimmt.

Ich vermute ja fast, dass du fälschlicherweise sowas wie $\begin{eqnarray*} (-4)^6 = - 4^6 \end{eqnarray*}$ gemacht hast verwirrt

verwirrt

01.12.2012, 19:24

Stefan03

Auf diesen Beitrag antworten »

Hi,
ja, siehe letzten editierten Beitrag smile

smile

01.12.2012, 19:28

HAL 9000

Auf diesen Beitrag antworten »

Wobei man allerdings nicht $\begin{eqnarray*} {3^8}^6 \end{eqnarray*}$ schreiben sollte, das kann optisch nämlich leicht mit $\begin{eqnarray*} 3^{8^6} = 3^{\left( 8^6 \right)} \end{eqnarray*}$ verwechselt werden.

Besser wäre die Notation $\begin{eqnarray*} \left(3^8\right)^6 \end{eqnarray*}$ , denn das ist hier ja schließlich gemeint.

01.12.2012, 19:36

Mystic

Auf diesen Beitrag antworten »

Nach dem quadratischen Reziprozitaetsgesetz gilt, das 3 genau dann quadratischer Rest mod p für eine Primzahl p von der Form 4k+1 ist, wenn p mod 3 quadratischer Rest mod 3 ist... Damit muss man also hier nur mehr die (sehr viel leichtere) Frage beantworten, ob 2 quadratischer Rest mod 3 ist...

01.12.2012, 21:03

tmo

Auf diesen Beitrag antworten »

@Mystic: Ich bin davon ausgegangen, dass das quadratische Reziprozitätsgesetz dem Fragesteller kaum bekannt ist, weil es ja zumeist in Verbindung mit dem Legendre-Symbol gelehrt wird.

Daher auch:

Zitat:

Original von tmo
Das macht die Aufgabe natürlich etwas schwieriger.

Dass die Aufgabe mit dem Reziprozitätsgesetz trivial wird, war mir schon klar Augenzwinkern

Augenzwinkern

01.12.2012, 21:17

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von tmo
@Mystic: Ich bin davon ausgegangen, dass das quadratische Reziprozitätsgesetz dem Fragesteller kaum bekannt ist, weil es ja zumeist in Verbindung mit dem Legendre-Symbol gelehrt wird.

Ja, das hab ich durchaus mitbekommen... Ich wollte nur den Threadersteller darauf hinweisen unter "welcher Überschrift" das einzuordnen ist, falls er sich das Wissen dazu "ergooglen" will... Big Laugh

Big Laugh

1

Verwandte Themen