sot arm έγραψε: ↑Κυρ Ιαν 27, 2019 9:09 pm
Πρόβλημα 5:
Θεωρούμε

πίνακες

με στοιχεία ακέραιους αριθμούς, τέτοιους ώστε

και

, και θέτουμε

. Δείξτε ότι υπάρχει θετικός ακέραιος k
για τον οποίο όλα τα στοιχεία του πίνακα

είναι ακέραιοι αριθμοί.
Έστω

το χαρακτηριστικό πολυώνυμο του

. Το

έχει ακέραιους συντελεστές.
Λήμμα: Για κάθε θετικό ακέραιο

μπορούμε να γράψουμε
όπου οι ακολουθίες ακεραίων

ικανοποιούν την αναδρομική σχέση
μαζί με τις αρχικές συνθήκες

και

για

με

.
Απόδειξη λήμματος: Θα το δείξουμε με ισχυρή επαγωγή. Ο ισχυρισμός είναι άμεσος για

. Έστω λοιπόν ότι ισχύει για

. Θα δείξουμε ότι ισχύει και για

.
Επειδή

έχουμε

άρα και

. Άρα από την επαγωγική υπόθεση
όπου
Δηλαδή ο ισχυρισμός ισχύει και για

.
Κοιτάμε τώρα κάθε μία από τις ακολουθίες

modulo

. (Αγνοούμε την

.) Κάθε μια από αυτές ικανοποιεί την αναδρομική σχέση

οπότε είναι περιοδική. (
Δείτε στην τελευταία παράγραφο γιατί.) Έστω ότι η

είναι περιοδική με περίοδο

. Τότε θα έχουμε

για κάθε

πολλαπλάσιο του

. Θέτουμε

και παρατηρούμε ότι

για κάθε

.
Από το λήμμα έχουμε
άρα και
Ο πίνακας

έχει ακέραια στοιχεία επειδή το ίδιο ισχύει για κάθε ένα από τους

. Για

όλα τα στοιχεία είναι πολλαπλάσια του

. Το ίδιο όμως ισχύει και για

αφού ο πίνακας θα είναι ο

.
Άρα όλα τα στοιχεία του

είναι ακέραια πολλαπλάσια του

και άρα όλα τα στοιχεία του

είναι ακέραια.
Σημείωση: Δεν χρησιμοποιήσαμε πουθενά το γεγονός ότι
.
Προσθήκη αργότερα: Όπως με ενημέρωσε με π.μ. ο Αντώνης Ζητρίδης, χρειάζεται τελικά το

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

modulo κάποιον φυσικό

. Από περιστερώνα θα υπάρχουν δύο υπακολουθίες

συνεχόμενων όρων οι οποίες θα είναι ακριβώς οι ίδιες. Δηλαδή θα υπάρχουν

ώστε

. Επαγωγικά είναι απλό ότι

για κάθε φυσικό

. Για να δείξουμε όμως

για κάθε φυσικό

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

. Αυτό γίνεται αν το

είναι αντιστρέψιμο modulo

διότι τότε θα έχουμε

. Στην περίπτωσή μας, λόγω του

ο συγκεκριμένος συντελεστής ισούται με

ή

οπότε παίρνουμε την περιοδικότητα της ακολουθίας.