Um zu zeigen, dass $5$ genau dann ein quadratischer Rest modulo $p$ ist, wenn die letzte Ziffer von $p$ entweder $1$ oder $9$ ist, verwenden wir das Legendre-Symbol und das quadratische Reziprozitätsgesetz.

Schritt 1: Bedingung für quadratischen Rest

Die Zahl $5$ ist genau dann ein quadratischer Rest modulo $p$, wenn gilt: $\left(\frac{5}{p}\right) = 1.$ Das Legendre-Symbol $\left(\frac{5}{p}\right)$ gibt an, ob 5 ein Quadrat modulo $p$ ist.

Schritt 2: Quadratisches Reziprozitätsgesetz

Das Reziprozitätsgesetz besagt für ungerade Primzahlen $p \neq 5$:

$\left(\frac{5}{p}\right) \cdot \left(\frac{p}{5}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{5-1}{2}}.$

Da $\frac{5-1}{2} = 2$, vereinfacht sich das Exponent zu $\frac{p-1}{2} \cdot 2 = p-1$, sodass wir erhalten:

$\left(\frac{5}{p}\right) = \left(\frac{p}{5}\right) \cdot (-1)^{p-1}.$

Da $(-1)^{p-1} = 1$ für jede ungerade Primzahl $p$, folgt:

$\left(\frac{5}{p}\right) = \left(\frac{p}{5}\right).$

Schritt 3: Berechnung von $\left(\frac{p}{5}\right)$

Das Legendre-Symbol $\left(\frac{p}{5}\right)$ wird durch die Regel berechnet:

• $\left(\frac{p}{5}\right) = 1$, falls $p \equiv 1,4 \mod 5$.
• $\left(\frac{p}{5}\right) = -1$, falls $p \equiv 2,3 \mod 5$.

Das bedeutet, dass $5$ genau dann ein quadratischer Rest modulo $p$ ist, wenn $p \equiv 1$ oder $4 \mod 5$.

Schritt 4: Letzte Dezimalziffer von $p$

Primzahlen der Form $p \equiv 1 \mod 5$ oder $p \equiv 4 \mod 5$ haben folgende letzte Ziffern:

• Falls $p \equiv 1 \mod 5$, dann ist die letzte Ziffer von $p$ entweder 1 oder 6.
• Falls $p \equiv 4 \mod 5$, dann ist die letzte Ziffer von $p$ entweder 4 oder 9.

Allerdings ist $p$ eine Primzahl, und die einzige Möglichkeit für die letzte Ziffern von $p$, die Primzahlen sind, sind 1 und 9 (denn Zahlen, die auf 6 oder 4 enden, sind durch 2 oder 3 teilbar und somit keine Primzahlen außer $2$, das hier nicht relevant ist).

Fazit:

Daher folgt, dass $5$ genau dann ein quadratischer Rest modulo $p$ ist, wenn die letzte Ziffer von $p$ entweder 1 oder 9 ist.

---

Hast du Fragen dazu oder soll ich weitere Details ausführen?

Hier sind fünf verwandte Fragen:

1. Was ist das Legendre-Symbol und wie wird es berechnet?
2. Welche Primzahlen haben eine bestimmte letzte Ziffer?
3. Wie funktioniert das quadratische Reziprozitätsgesetz?
4. Was sind quadratische Reste und warum sind sie wichtig?
5. Wie kann man die Quadratreste für verschiedene Moduli berechnen?

Tipp:
Quadratische Reste sind nützlich in der Kryptographie, insbesondere in Zahlentheorie-basierten Verschlüsselungsverfahren wie dem RSA-Algorithmus!