Διαφορετικά υπόλοιπα

#1

Να προσδιορίσετε όλους τους ακέραιους αριθμούς $n, \ n\geq 2$ , για τους οποίους οι αριθμοί $1!,2!,3!,\cdots, (n-1)!$ διαιρούμενοι δια

αφήνουν διαφορετικά υπόλοιπα.

#2

Χρησιμοποιήστε το θεώρημα Wilson.

Stavroulitsa · #3

Καλησπέρα! Και εγώ σκεφτηκα το θεώρημα Wilson, αλλα το πως το εφάρμωσα είναι άλλο θέμα...

Με μια πρώτη ματιά βλέπουμε πως ο αριθμός n δεν είναι σύνθετος γιατί πολύ απλά οι διαιρέτες του αριθμού θα περιέχονται τουλάχιστον μια φορά στα παραγοντικά, επομένως θα έχουμε αρκετούς αριθμούς που θα είναι πολλαπλάσια του n... Στα τέλεια τετράγωνα όπου μπορεί να υπάρχει μόνο ένας ουσιαστικός διαιρέτης αυτός θα επαναλαμβάνεται σε αριθμούς διπλάσιούς τους αφού $n\geq 2$ .
Άρα έχουμε και τους πρώτους αριθμούς όπου γνωρίζουμε πως ισχύει το θεώρημα Wilson, δηλαδή $\left(n-1 \right)!\equiv -1modn$ , άρα αρκεί να αποδείξουμε για κάθε ακέραιο αριθμό κ ισχυει $\left(n-k \right)!\equiv -kmodn$ ώστε να έχουμε διαγορετικά υπολοιπα.
Υποοθέτουμε ότι: $\left(n-k \right)!\equiv -kmodn$
Θα πρέπει να ισχύει και : $\left(n-k+1 \right)!\equiv -k+1modn$
έχουμε:
$A=\left(n-k+1 \right)!\equiv \left(n-k+1 \right)!modn\Rightarrow A\equiv \left(n-k \right)!\left(n-k+1 \right)modn\Rightarrow A\equiv -k\left(n-k+1 \right)modn\Rightarrow A\equiv -k\left(-k+1 \right)modn$
και πρέπει για να ισχύει αυτό να είναι $-k+1=-k\left(-k+1 \right)\Leftrightarrow -k+1=k^2-k\Leftrightarrow k^2-1=0\Leftrightarrow \left(k-1 \right)\left(k+1 \right)=0$ ,
άρα κ=1 ή κ=-1, κρατάμε το κ=1 διότι τα παραγοντικά ισχύουν μόνο για θετικούς ακέραιους και άρα το ζητούμενο της ασκησης αφού κ=1 ισχύει μόνο για τους πρώτους n=2 και n=3 ...

ΥΓ. Ελπίζω να μην έχω πολλά λάθη...

Ωmega Man · #4

Άρα έχουμε και τους πρώτους αριθμούς όπου γνωρίζουμε πως ισχύει το θεώρημα Wilson, δηλαδή $\left(n-1 \right)!\equiv -1mod(n)$ , άρα αρκεί να αποδείξουμε για κάθε ακέραιο αριθμό κ ισχύει $\left(n-k \right)!\equiv -kmod(n)$ ώστε να έχουμε διαφορετικά υπόλοιπα.

!!!!!!!!!!!!!!!!!!!!!!! Στην ηλικία σου δεν είχα ιδέα τι θα πει mod..... αλλά ίσως τότε δεν υπήρχε mathematica.

#5

Σταυρουλίτσα, σωστά δείχνεις ότι ο

πρέπει να είναι πρώτος. Μετά όμως τα χαλάς. Το μόνο που απέδειξες μετά είναι ότι δεν μπορεί να ισχύει $(n-k)! \equiv -k \bmod n$ για κάθε

. (Εκτός αν n=2

.) Αν ίσχυε, σωστά λες ότι θα είχαμε διαφορετικά υπόλοιπα. Δεν ισχύει όμως. Από αυτό δεν μπορούμε να συμπεράνουμε ότι τα υπόλοιπα δεν θα είναι διαφορετικά.

Πρόσθεσα ένα «δεν» που όπως πολύ σωστά παρατήρησε η Σταυρουλίτσα έλειπε.

Βάζω ακόμη μια κρυμμένη απόδειξη. Αν θες μπορείς να την αγνοήσεις.

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Ωmega Man έγραψε: !!!!!!!!!!!!!!!!!!!!!!! Στην ηλικία σου δεν είχα ιδέα τι θα πει mod

Ούτε κι' εγώ.

#6

Επαναφορά!

#7

Ας συνοψίσουμε αφού ουσιαστικά έχει λυθεί.

Για n=2

και

οι αριθμοί όντως αφήνουν διαφορετικά υπόλοιπα. Θα δείξουμε ότι δεν υπάρχουν άλλοι.

Ας υποθέσουμε λοιπόν ότι $n \geqslant 4$ .

Αν ο

είναι σύνθετος τότε τα υπόλοιπα δεν είναι όλα διαφορετικά. Πράγματι έστω n = ab

με $1 < a \leqslant b < n$ . Τότε έχουμε $b! \equiv (b+1)! \bmod n$ αφού $(b+1)! - b! = b \times b!$ το οποίο είναι πολλαπλάσιο του n = ab

. Επίσης είναι $b \leqslant n/2$ άρα $b+1 \leqslant n/2 +1< n$ (για $n \geqslant 4$ ). Άρα όντως δύο από τους αριθμούς $1!,2!,\ldots,(n-1)!$ αφήνουν το ίδιο υπόλοιπο $\bmod n$ .

Αν ο

είναι πρώτος τότε από το θεώρημα Wilson έχουμε $(n-1)! \equiv -1 \bmod n$ . Άρα $(n-1) \times (n-2)! \equiv -1 \bmod n$ . Οπότε $(-1) \times (n-1) \times (n-2)! \equiv 1 \bmod n$ και άρα $(n-2)! \equiv 1 \bmod n$ αφού $(-1)(n-1) \equiv 1 \bmod n$ . Οπότε οι

και

αφήνουν το ίδιο υπόλοιπο $\bmod n$ . (Είναι n-2 > 1

αφού $n \geqslant 4$ .)

Διαφορετικά υπόλοιπα

Διαφορετικά υπόλοιπα

Re: Διαφορετικά υπόλοιπα

Re: Διαφορετικά υπόλοιπα

Re: Διαφορετικά υπόλοιπα

Re: Διαφορετικά υπόλοιπα

Re: Διαφορετικά υπόλοιπα

Re: Διαφορετικά υπόλοιπα

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