Σχετικά πρώτοι σε ακολουθία

#1

Έστω $a_1\in\mathbb{Z}$ . Ορίζουμε αναδρομικά a_2=a_1^2-a_1-1

, $\dots$ , $a_{n+1}=a_n^2-a_n-1$ . Να αποδειχθεί ότι ο $a_{n+1}$ και ο 2n+1

είναι σχετικά πρώτοι.

DrStrange · #2

Έστω

ένας πρώτος που διαιρεί το $(a_{n+1},2n+1)$ . Προφανώς p>2

. Αν ο

διαιρεί κάποιο a_i

με index

τότε με παρατήρηση προκύπτει ότι για κάθε $n+1 \ge j>i$ $a_j \equiv 1 or -1 \mod p$ άτοπο. Άρα το

δεν διαιρεί κανένα άλλο όρο. Από την άλλη αυτό σημαίνει πως p>n

αφού διαφορετικά τα υπόλοιπα έρχονται από pigy σε κύκλους και άρα το

θα είχε ξαναπροκύψει, άτοπο. Επομένως αφού p|2n+1

πρέπει αναγκαστικά p=2n+1

και όλα τα $a_1,...,a_{\dfrac{p+1}{2}}$ να δίνουν διαφορετικά υπόλοιπα $\mod p$ και τα

,

να μην είναι σε αυτά που είναι άτοπο αφού το πλήθος των υπολοίπων που λαμβάνει η παράσταση x^2-x-1

είναι ίσο με το πλήθος των τετραγωνικών residues + 1 (όταν μηδενίζεται το συμπληρωμένο τετράγωνο) δηλαδή $\dfrac{p+1}{2}$ όμως στερούμαστε την

και την

(προφανές) άρα στους $a_2,...,a_\dfrac{p+1}{2}$ αναγκαστικά δυο θα είναι ίσοι $\mod p$ άτοπο από πριν.

-Strange