Πρώτος

Ορέστης Λιγνός · #1

Να βρείτε όλους τους θετικούς ακεραίους

, ώστε ο αριθμός $A=n^{10}+n^5+1$ να είναι πρώτος.

harrisp · #2

Αρκεί να το παραγοντοποιήσουμε και να πούμε οτι ενας όρος πρεπει να ειναι 1.

$n^{10}+n^5+1=n^{10}+n^9-n^9+n^8-n^8+n^7-n^7+n^6-n^6+n^5+n^4-n^4+n^3-n^3+n^2-n^2+n-n+1=(n^2+n+1)(n^8-n^7+n^5-n^4+n^3-n+1)$
Οπου ο πρωτος παράγοντας ειναι ενα μονο αν n=0 (άτοπο) ενώ ο δεύτερο μονο αν το n^2|1

δηλαδή n=1 που δίνει τον 3 που ειναι πρωτος

#3

Γράφω κάποια σχόλια τα οποία δεν χρειάζονται μεν για την λύση της άσκησης αλλά βοηθάνε αρκετά αν κάποιος τα γνωρίζει.

Υποψιαζόμαστε ότι το πολυώνυμο $x^{10} + x^5 + 1$ παραγοντοποιείται (στους ακεραίους). Θα ήταν ποιο εύκολο βέβαια να παραγοντοποιήσουμε το y^2 + y+1

και μετά να θέσουμε x = y^5

. Μόνο που είναι απλό να δειχθεί ότι το y^2+y+1

είναι ανάγωγο (δηλαδή δεν παραγοντοποιείται στους ακεραίους). Ξέρουμε όμως κάτι αρκετά χρήσιμο για αυτό το πολυώνυμο. Ισχύει ότι

$\displaystyle{ y^2+y+1 = \frac{y^3-1}{y-1}}$

Άρα είναι και

$\displaystyle{ x^{10} + x^5 + 1 = \frac{x^{15}-1}{x^5-1}}$

Αυτό είναι όντως εξαιρετικά χρήσιμο γιατί ξέρουμε πλήρως πως παραγοντοποιούνται πολυώνυμα της μορφής x^n-1

.

Η διαδικασία είναι η εξής:

Αν

θετικός ακέραιος ορίζουμε $\displaystyle{\omega_n = e^{2\pi i/n}.}$ Ορίζουμε επίσης

$\displaystyle{ \Phi_n(x) = \prod_{\stackrel{k \in \{0,1,\ldots,n\}}{(k,n)=1}} (x - \omega_n^k)}$

Αν και δεν είναι προφανές, το πολυώνυμο $\Phi_n(x)$ έχει ακέραιους συντελεστές και μάλιστα είναι ανάγωγο. Ονομάζεται το νιοστό κυκλοτομικό πολυώνυμο. Από τον ορισμό ο βαθμός του ισούται με $\varphi(n)$ . Στην πράξη δεν υπολογίζουμε το πολυώνυμο από τον πιο πάνω τύπο αλλά αναδρομικά από τον σημαντικό τύπο που ακολουθεί:

$\displaystyle{ x^n - 1 = \prod_{d|n} \Phi_d(x)}$

Π.χ. είναι

$\displaystyle{ x^{10}-1 = \Phi_1(x) \Phi_2(x)\Phi_5(x)\Phi_{10}(x)}$

Οπότε έχοντας ήδη υπολογίσει τα $\Phi_1(x), \Phi_2(x),\Phi_5(x)$ μπορούμε να κάνουμε την διαίρεση για να βρούμε το $\Phi_{10}(x)$ . [Τα πρώτα τέσσερα κυκλοτομικά πολυώνυμα είναι τα $\Phi_1(x) = x-1,\Phi_2(x)=x+1,\Phi_3(x)=x^2+x+1$ και $\Phi_4(x) = x^2+1$ .]

Γιατί είναι χρήσιμα όλα αυτά; Διότι τώρα μπορούμε να πούμε

$\displaystyle{ x^{10} + x^5 + 1 = \frac{x^{15}-1}{x^5-1} = \frac{\Phi_1(x) \Phi_3(x)\Phi_5(x)\Phi_{15}(x)}{\Phi_1(x) \Phi_5(x)} = \Phi_3(x)\Phi_{15}(x)}$

Σχεδόν τελειώσαμε τώρα. Δεν χρειάζεται καν να υπολογίσουμε το $\displaystyle{ \Phi_{15}(x)}$ το οποίο είναι το $\displaystyle{ x^8 - x^7 + x^5 - x^4 + x^3 - x + 1}$ που βρήκε ο Χάρης πιο πάνω.

Μας αρκεί ότι το $\Phi_3(x) = x^2 + x + 1$ είναι παράγοντας του πολυωνύμου και η προφανής παρατήρηση ότι για n > 1

έχουμε

$\displaystyle{ 1 < n^2 + n + 1 < n^{10} + n^5 + 1}$

[Παρεμπιπτόντως, για n=1

δεν καταλήγουμε σε άτοπο. Ο αριθμός

είναι όντως πρώτος.]

Al.Koutsouridis · #4

Όμορφη παρέμβαση

. Για μια παραγοντοποίση πολυωνύμων αυτής της μορφής δείτε και εδώ την λύση του κ.Παπαδόπουλου.

Πρώτος

Πρώτος

Re: Πρώτος

Re: Πρώτος

Re: Πρώτος

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