IMC 2020/2/6

Συντονιστής: Demetres

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 3231
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

IMC 2020/2/6

#1

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Κυρ Αύγ 02, 2020 10:48 am

Βρείτε όλους τους πρώτους p για τους οποίους υπάρχει
μοναδικό a\in \left \{ 1,2,...,p \right \}
με την ιδιότητα .
Το p διαιρεί το
a^3-3a+1



Λέξεις Κλειδιά:
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8520
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: IMC 2020/2/6

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Αύγ 03, 2020 3:02 pm

Ας το δούμε. Μοιάζει λίγο με τη δεύτερη επίσημη λύση στη σκέψη αλλά διαφέρει στην εκτέλεση.

Προφανώς ο p=2 απορρίπτεται αφού ο a^3 - 3a + 1 είναι πάντα άρτιος. Επίσης ο p = 3 είναι δεκτός αφού a^3 - 3a + 1 \equiv a+1 \bmod 3 άρα 3|a^3 - 3a + 1 \iff a \equiv 2 \bmod 3.

Υποθέτουμε τώρα ότι p > 3 και έστω a μια ρίζα του x^3 - 3x  +1 modulo p. Θα δείξουμε ότι υπάρχει τουλάχιστον ακόμη μία ρίζα modulo p, άρα ο p απορρίπτεται. Πράγματι, αν έχει και δεύτερη ρίζα, τότε σίγουρα θα έχει και τρίτη. Δεν μπορούν να είναι και οι τρεις ίσες με a αφού τότε θα έχουμε (από τον συντελεστή του x^2) 3a \equiv 0 \bmod p άρα και a \equiv \bmod p, άτοπο.

Έχουμε την παραγοντοποίηση x^3 - 3x + 1 = (x-a)(x^2 + ax - b) όπου b τέτοιο ώστε ab \equiv 1 \bmod p και a^2 + b \equiv 3 \bmod p.

Θέλουμε να δείξουμε ότι η x^2 + ax - b \equiv 0 έχει ρίζα. Ισοδύναμα θέλουμε (2x+a)^2 \equiv (a^2 + 4b) να έχει ρίζα. Δηλαδή θέλω το a^2+4b να είναι τέλειο τετράγωνο modulo p αφού τότε εύκολα βρίσκουμε τη ρίζα (είναι p \neq 2).

Είναι a^2 + 4b \equiv 3+3b \equiv 3(b+1) \equiv 3b(1+a) \bmod p. Επίσης (1+a)(2a-1)^2 \equiv (a+1)(4a^2 - 4a+1) \equiv 4a^3 - 3a + 1 \equiv 9a - 3 \equiv 3(3a-1) \bmod p και ba^4 \equiv a^3 \equiv 3a-1 \bmod p.

Άρα (a^2+4b)(2a-1)^2a^4 \equiv 3^2(3a-1)^2 \bmod p.

Επομένως αποδείξαμε το ζητούμενο εκτός ίσως στην περίπτωση όπου 2a \equiv 1 \bmod p ή a \equiv 0 \mod p. Τότε όμως θα έχουμε και 3a \equiv 1 \bmod p (αφού p \neq 3). Σε κάθε περίπτωση έχουμε a \equiv 0 \bmod p που είναι αδύνατο αφού a^3 - 3a + 1 \equiv 0 \bmod p.

Επομένως ο p=3 είναι ο μοναδικός πρώτος με τη ζητούμενη ιδιότητα.


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης