Quadratische Reste mod 100

21.05.2021, 11:04

MaPalui

Auf diesen Beitrag antworten »

Quadratische Reste mod 100

Hallo ihr lieben smile

smile

ich möchte die Anzahl der quadratischen Rest mod 100 möglichst elementar bestimmen, also ohne Legendre-Symbol.
Mein Ansatz:
$\begin{eqnarray*} x^2\pmod{100} = (x\pmod{100})^2 = ((100-x)\pmod{100})^2 \end{eqnarray*}$

Damit kann ich ja zumindest schonmal die Anzahl von 100 auf 51 drücken. Müsste ich ab dieser Stelle ausprobieren? Oder kann ich die restlichen 29 noch ausschließen?

Zweiter Ansatz:
$\begin{eqnarray*} (\sum\limits_{k=0}^n a_k\cdot10^k)^2 \pmod{ 100} = (\sum\limits_{k=0}^n a_k\cdot10^k \mod 100)^2 \pmod {100} = a_0^2 + 20a_0a_1 \pmod {100} \end{eqnarray*}$

Leider weiß ich jetzt nicht mehr weiter.

LG
Maren

21.05.2021, 12:34

Huggy

Auf diesen Beitrag antworten »

RE: Quadratische Reste mod 100
Es ist auch

$\begin{eqnarray*} (50-x)^2 \equiv x^2 \mod 100 \end{eqnarray*}$

21.05.2021, 16:49

MaPalui

Auf diesen Beitrag antworten »

Hi Huggy, danke für deine Zeit.

Super, damit konnte ich das ganze ja nun auf 26 drücken.
Für die einzelnen Fälle kann ich ja folgern:
$\begin{eqnarray*} 10^2 \mod{100} = (10+10)^2\mod{100} = 0 \end{eqnarray*}$ und $\begin{eqnarray*} 15^2 \mod{100}= (15+10)^2\mod{100} = 25 = 5^2\mod{100} \end{eqnarray*}$ . Damit lande ich dann bei den übrigen 22, die alle verschieden sind.

Eigentlich genügt mir das schon und daher will ich mich schonmal ganz herzlich bei dir bedanken smile

smile

Nun frage ich mich: Könnte ich ohne durchrechnen zeigen, dass die restlichen 22 wirklich alle verschieden sind?

21.05.2021, 17:56

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von MaPalui
Nun frage ich mich: Könnte ich ohne durchrechnen zeigen, dass die restlichen 22 wirklich alle verschieden sind?

Da fällt mir kein Argument ein.

22.05.2021, 13:54

MaPalui

Auf diesen Beitrag antworten »

Auf jeden Fall hast du mir sehr geholfen. Vielen Dank dafür smile

smile

28.05.2021, 20:44

MaPalui

Auf diesen Beitrag antworten »

Hallo nochmal,

ich muss diesen Beitrag nochmal ausgraben.
Ich möchte die Aussage etwas allgemeiner formulieren:
Jede Quadratzahl endet auf eines von 22 möglichen Paaren von Endziffern.

Beweis:
Sei $\begin{eqnarray*} Z = n^2 \end{eqnarray*}$ und betrachte $\begin{eqnarray*} Z\pmod{100} \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} Z\pmod{100} = n^2\pmod{100}. \end{eqnarray*}$

Jetzt würde ich ja gerne sagen, dass ist $\begin{eqnarray*} (n\pmod{100})^2 \end{eqnarray*}$ , aber das stimmt ja nicht.
Darf ich aber sagen, dass ist $\begin{eqnarray*} (n\pmod{100})^2\pmod{100} \end{eqnarray*}$ ?

Anzeige

29.05.2021, 07:35

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von MaPalui
Darf ich aber sagen, dass ist $\begin{eqnarray*} (n\pmod{100})^2\pmod{100} \end{eqnarray*}$ ?

Was genau soll das bedeuten? Ich verstehe nicht, was behauptet werden soll.

29.05.2021, 09:46

MaPalui

Auf diesen Beitrag antworten »

Guten Morgen,

also die Behauptung ist Folgende:
Sei Z Quadratzahl. Dann endet Z auf eines von 22 möglichen Paaren von Endziffern.

29.05.2021, 10:23

Huggy

Auf diesen Beitrag antworten »

Das ist richtig und das ist doch schon dadurch gezeigt, dass es mod 100 genau 22 quadratische Reste gibt.

29.05.2021, 11:40

MaPalui

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Das ist richtig und das ist doch schon dadurch gezeigt, dass es mod 100 genau 22 quadratische Reste gibt.

Also mein Problem ist folgendes.
Sei $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ , also $\begin{eqnarray*} n = \sum\limits_{k=0}^b a_k10^k \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} n^2\pmod{100} = a_0^2 + a_0a_1 \end{eqnarray*}$ .
Aber da kommen ja jetzt z.B. für $\begin{eqnarray*} a_0 = a_1 = 9 \end{eqnarray*}$ Ergebnisse über 100 raus. Aber ich kann sie ja nochmal reduzieren. Nur kriege ich das gerade analytisch nicht hin.

29.05.2021, 11:55

Huggy

Auf diesen Beitrag antworten »

Es gibt mod 100 genau 22 quadratische Reste. Das gilt auch, wenn man als Repräsentanten für das Restsystem die Zahlen von 0 bis 99 wählt. Wenn man eine Zahl $\begin{eqnarray*} \geq 100 \mod 100 \end{eqnarray*}$ in diesem Rstsystem betrachtet, ist das doch gerade die Reduktion auf die beiden Endziffern. Was ist da noch zu beweisen?

29.05.2021, 12:10

MaPalui

Auf diesen Beitrag antworten »

Prinzipiell ist mir das schon klar, ich hänge halt nur daran wie man es als Bachelorstudentin eben "genau genug" aufschreibt. Aber du hast mir schon damit geholfen, ich lasse es einfach so wie ich es habe. Danke sehr für deine hilfe (über die freue ich mich immer wieder smile

smile

)

LG
Maren

29.05.2021, 12:38

Huggy

Auf diesen Beitrag antworten »

Noch ein Anlauf: Sei

$\begin{eqnarray*} n=\sum_{k=0}^c a_k 10^k \end{eqnarray*}$

Dann ist

$\begin{eqnarray*} n^2=\sum_{k=0}^d b_k 10^k \end{eqnarray*}$

und

$\begin{eqnarray*} n^2 \mod 100 =b_1b_0 \end{eqnarray*}$

Du hast gezeigt, dass es genau $\begin{eqnarray*} 22 \end{eqnarray*}$ solcher $\begin{eqnarray*} b_1b_0 \end{eqnarray*}$ gibt.

29.05.2021, 13:22

MaPalui

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy

Dann ist

$\begin{eqnarray*} n^2=\sum_{k=0}^d b_k 10^k \end{eqnarray*}$

und

$\begin{eqnarray*} n^2 \mod 100 =b_1b_0 \end{eqnarray*}$

Sollte es nicht $\begin{eqnarray*} b_0 + 10b_1 \end{eqnarray*}$ sein?

29.05.2021, 13:26

Huggy

Auf diesen Beitrag antworten »

Mit $\begin{eqnarray*} b_1b_0 \end{eqnarray*}$ meinte ich die Ziffernfolge, die den von dir genannten Wert hat.

29.05.2021, 13:28

MaPalui

Auf diesen Beitrag antworten »

Ah ich verstehe.
Ich glaube so finde ich es gut und schreibe es auf! Danke sehr Mit Zunge

Mit Zunge

29.05.2021, 20:28

MaPalui

Auf diesen Beitrag antworten »

Also ich muss nochmal etwas fragen. Ich glaube da liegt der Hase im Pfeffer.

Sei $\begin{eqnarray*} Z \end{eqnarray*}$ ein ganzzahliges Quadrat. Dann gibt es ein $\begin{eqnarray*} n\in\mathbb N \end{eqnarray*}$ , sodass $\begin{eqnarray*} n^2 = Z \end{eqnarray*}$ .
Sei $\begin{eqnarray*} n = \sum\limits_{k=0}^l a_l10^l \end{eqnarray*}$ . Dann ist $\begin{eqnarray*} n^2 = \sum\limits_{l=0}^{2k}10^l\sum\limits_{i=0}^{l}a_ia_{l-i} \end{eqnarray*}$ .

Nun betrachte ich diesen Ausdruck modulo 100. Also bekomme ich ja ein Element zwischen 0 und 99.
Aber es ist doch auch $\begin{eqnarray*} n^2 = \sum\limits_{l=0}^{2k}10^l\sum\limits_{i=0}^{l}a_ia_{l-i} \pmod{100} = a_0+20a_0a_1 \end{eqnarray*}$ . Da kommen ja wiederum auch Ergebnisse $\begin{eqnarray*} \geq 100 \end{eqnarray*}$ raus.
Wo ist mein Fehler?

LG
Maren

29.05.2021, 20:48

Huggy

Auf diesen Beitrag antworten »

Man kann doch jedes Ergebnis $\begin{eqnarray*} \geq 100 \end{eqnarray*}$ weiter auf ein Ergebnis im Bereich $\begin{eqnarray*} 0, \ldots 99 \end{eqnarray*}$ reduzieren. Zwar beweisen Beispiele nichts, aber manchmal lösen sie den Knoten im Gehirn. Sei also

$\begin{eqnarray*} n=1789=100 \cdot 17 +89 \end{eqnarray*}$

Dann haben wir schon mal

$\begin{eqnarray*} n^2 \equiv 89^2 =7921 \mod 100 \end{eqnarray*}$

Und weiter ist

$\begin{eqnarray*} 7921=100 \cdot 79 +21 \equiv 21 \mod 100 \end{eqnarray*}$

29.05.2021, 20:51

MaPalui

Auf diesen Beitrag antworten »

Und genau das ist mein Problem aus der Frage von gestern.
Rechne ich $\begin{eqnarray*} n^2 \pmod{100} = 20a_0a_1 + a_0^2 \end{eqnarray*}$ oder eben $\begin{eqnarray*} 20a_0a_1 + a_0^2 \pmod{100} \end{eqnarray*}$ , worauf ich ja eigentlich hinauswill. Aber das wäre ja $\begin{eqnarray*} (n^2\pmod{100})\pmod{100} \end{eqnarray*}$ , also zweimal den mod angewendet.

29.05.2021, 20:51

Leopold

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy
Zwar beweisen Beispiele nichts, aber manchmal lösen sie den Knoten im Gehirn.

Den Spruch finde ich didaktisch hervorragend. Muß ich mir merken. Spontan drauf gekommen?

29.05.2021, 21:06

Huggy

Auf diesen Beitrag antworten »

@MaPalui

Allmählich weiß ich nicht mehr weiter. Aus

$\begin{eqnarray*} a \equiv b \mod m \end{eqnarray*}$

und

$\begin{eqnarray*} b \equiv c \mod m \end{eqnarray*}$

folgt doch

$\begin{eqnarray*} a \equiv c \mod m \end{eqnarray*}$

Ich weiß auch gar nicht, weshalb du dauernd versuchst, aus der Dezimaldarstellung von $\begin{eqnarray*} n \end{eqnarray*}$ die Dezimaldarstellung $\begin{eqnarray*} n^2 \mod 100 \end{eqnarray*}$ zu gewinnen. Das ist für das Problem doch völlig unerheblich. Es genügt zu wissen, dass man das Ergebnis immer in den Bereich $\begin{eqnarray*} 0, \ldots 99 \end{eqnarray*}$ bringen kann.

@Leopold

Den Spruch habe ich bei der Nachhilfe gelegentlich benutzt. Manchmal hat ein Beispiel genutzt, aber durchaus nicht immer.

29.05.2021, 21:14

MaPalui

Auf diesen Beitrag antworten »

Also mein Verständnisproblem war/ist folgendes:

$\begin{eqnarray*} n^2\pmod{100} = b_0b_1 \end{eqnarray*}$ ist etwas anderes als $\begin{eqnarray*} n^2\pmod{100} = b_0b_1 \pmod{100} \end{eqnarray*}$ .

Aber ich denke das hat sich geklärt, danke euch!

30.05.2021, 08:22

Huggy

Auf diesen Beitrag antworten »

Du klingst noch nicht besonders überzeugt. Noch mal die Anwendung der Transitivität der Kongruenzrelation auf das Beispiel: Wegen

$\begin{eqnarray*} (a \equiv b \mod m) \land (b \equiv c \mod m) \rightarrow (a \equiv c \mod m) \end{eqnarray*}$

folgt

$\begin{eqnarray*} (1789^2 \equiv 89^2 \mod 100) \land (89^2 \equiv 21 \mod 100) \rightarrow (1789^2 \equiv 21 \mod 100) \end{eqnarray*}$

Transitivität, Symmetrie und Reflexivität sind elementare Eigenschaften der Kongruenzrelation. Deine dich offenbar verwirrende doppelte mod-Schreibweise wird nicht benötigt.

30.05.2021, 14:09

MaPalui

Auf diesen Beitrag antworten »

Hallo nochmal, Huggy,

meistens liegt mein Problem darin dass ich mich dermaßen tief in ein Problem verbeisse und mich das dann den ganzen Tag nicht loslässt. Mit den kongruenten und insbesondere der transitivität hab ich es aber nachvollzogen. Mein Problem lag darin dass ich den "Mod" Operator nur auf einer Seite der Gleichung angesehen habe. Aber nun bin ich wirklich überzeugt und das Dank deiner wirklich geduldigen Hilfe.

Vielen dank nochmal an dieser Stelle smile

smile

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »