IMC 2020/2/6

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #1

Βρείτε όλους τους πρώτους

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

διαιρεί το
a^3-3a+1

#2

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

Προφανώς ο 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

και έστω

μια ρίζα του x^3 - 3x +1

modulo

. Θα δείξουμε ότι υπάρχει τουλάχιστον ακόμη μία ρίζα modulo

, άρα ο

απορρίπτεται. Πράγματι, αν έχει και δεύτερη ρίζα, τότε σίγουρα θα έχει και τρίτη. Δεν μπορούν να είναι και οι τρεις ίσες με

αφού τότε θα έχουμε (από τον συντελεστή του x^2

) $3a \equiv 0 \bmod p$ άρα και $a \equiv \bmod p$ , άτοπο.

Έχουμε την παραγοντοποίηση x^3 - 3x + 1 = (x-a)(x^2 + ax - 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 \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

είναι ο μοναδικός πρώτος με τη ζητούμενη ιδιότητα.

IMC 2020/2/6

IMC 2020/2/6

Re: IMC 2020/2/6

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