Πρώτοι!!

Διονύσιος Αδαμόπουλος · #1

Να αποδειχθεί ότι για κάθε πρώτο

της μορφής p=4k+1

, ισχύει ότι $k^k \equiv 1 \mod p$

dement · #2

Εργαζόμαστε modulo

.

Γνωρίζουμε ότι το

είναι τετραγωνικό υπόλοιπο. Έστω m^2 = -1

. Το

είναι τετραγωνικό υπόλοιπο αν και μόνο αν ο

είναι της μορφής 8q + 1

και επίσης το

είναι διτετραγωνικό υπόλοιπο στην ίδια περίπτωση. Άρα το

είναι τετραγωνικό υπόλοιπο και $\displaystyle (2m)^{2k} = (-4)^k = 1 \implies \left( - \frac{1}{4} \right) ^k = k^k = 1$ .

Με την ευκαιρία, να υπενθυμίσω από τον κανονισμό του

: "Μη δίνετε ελλιπείς απαντήσεις, υποδείξεις ή μόνο το αποτέλεσμα."

Διονύσιος Αδαμόπουλος · #3

Αφού

, ισχύει η ισοδυναμία:

$k^k\equiv 1 \mod p\Leftrightarrow (4k)^k\equiv 4^k \mod p\Leftrightarrow$ $(p-1)^k \equiv 4^k \mod p$ ή ισοδύναμα:

$(-1)^k \equiv 2^{2k} \mod p \Leftrightarrow (-1)^{\dfrac{p-1}{4}}$ $\equiv 2^{\dfrac{p-1}{2}} \mod p$

Όμως $\dfrac{p^2-1}{8}=\dfrac{p-1}{4}\cdot \dfrac{p+1}{2}$ , όπου $\dfrac{p+1}{2}$ είναι περιττός, άρα έχουμε πως:

$(-1)^{\dfrac{p^2-1}{8}} \equiv (-1)^{\dfrac{p-1}{4}} \mod p$

Άρα αρκεί να αποδείξουμε πως αν

πρώτος της μορφής 4k+1

, ισχύει ότι:

$2^{\dfrac{p-1}{2}} \equiv (-1)^{\dfrac{p^2-1}{8}} \mod p$

Αυτό το έχω συναντήσει ως λήμμα, αν και δεν γνωρίζω την απόδειξη...

edit: Έγινε διόρθωση

dement · #4

Διονύσιος Αδαμόπουλος έγραψε: Τότε .
...
Τότε προφανώς δεν ισχύει ότι , άρα .

Προσοχή, ο

δεν είναι απαραίτητα πρώτος.

Διονύσιος Αδαμόπουλος · #5

dement έγραψε:
Διονύσιος Αδαμόπουλος έγραψε: Τότε .
...
Τότε προφανώς δεν ισχύει ότι , άρα .
Προσοχή, ο δεν είναι απαραίτητα πρώτος.

Νομίζω πως τώρα είναι εντάξει.

dement · #6

Το ίδιο λήμμα χρησιμοποίησα στην ουσία κι εγώ.

Διονύσιος Αδαμόπουλος · #7

Έκανα μια αναζήτηση στο διαδίκτυο και βρήκα την εξής απόδειξη του λήμματος:

Παρατηρούμε τα ακόλουθα $\dfrac{p-1}{2}$ υπόλοιπα:

$p-1 \equiv 1\cdot (-1)^1 \mod p$
$2 \equiv 2\cdot (-1)^2 \mod p$
$p-3 \equiv 3\cdot (-1)^3 \mod p$
$4 \equiv 4\cdot (-1)^4 \mod p$
.
.
.
$k \equiv \dfrac{p-1}{2}\cdot (-1)^{\dfrac{p-1}{2}} \mod p$

όπου $k=\dfrac{p-1}{2}$ αν p=4k+1

ή $k=p-\dfrac{p-1}{2}$ αν p=4k-1

Πολλαπλασιάζοντας τα παραπάνω κατά μέλη προκύπτει ότι:

$2\cdot 4\cdot...\cdot (p-3)(p-1) \equiv (\dfrac{p-1}{2})!\cdot$ $(-1)^{(1+2+3+...+\dfrac{p-1}{2})} \mod p \Leftrightarrow$

$2\cdot 4\cdot...\cdot (p-3)(p-1) \equiv$ $(\dfrac{p-1}{2})!\cdot (-1)^{\dfrac{p^2-1}{8}} \mod p$

Όμως $2\cdot 4\cdot...\cdot (p-3)(p-1)=$ $(2\cdot 1)\cdot (2\cdot 2)\cdot...\cdot (2\cdot \dfrac{p-3}{2})$ $\cdot (2\cdot \dfrac{p-1}{2})=2^{\dfrac{p-1}{2}}\cdot (\dfrac{p-1}{2})!$

Άρα έχουμε πως:

$2^{\dfrac{p-1}{2}}\cdot (\dfrac{p-1}{2})! \equiv (\dfrac{p-1}{2})!\cdot$ $(-1)^{\dfrac{p^2-1}{8}} \mod p$

Όμως $((\dfrac{p-1}{2})!, p)=1$ , άρα προκύπτει ότι:

$2^{\dfrac{p-1}{2}}\equiv (-1)^{\dfrac{p^2-1}{8}} \mod p$

Πρώτοι!!

Πρώτοι!!

Re: Πρώτοι!!

Re: Πρώτοι!!

Re: Πρώτοι!!

Re: Πρώτοι!!

Re: Πρώτοι!!

Re: Πρώτοι!!

Μέλη σε σύνδεση