Διαιρετότητα με πρώτους

Διονύσιος Αδαμόπουλος · #1

Για κάθε πρώτο αριθμό

να αποδειχτεί πως $\displaystyle{p|\binom{2p}{p}-2}$

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

Διονύσιος Αδαμόπουλος έγραψε:Για κάθε πρώτο αριθμό να αποδειχτεί πως $\displaystyle{p|\binom{2p}{p}-2}$

Ωραίο.

Εστω $A=\binom{2p}{p}-2}$ .

Μετά από πράξεις έχουμε

$A=\dfrac{(p+1)..2p-2p!}{p(p-1)!}$

Αρκεί να αποδείξουμε ότι ο

διαιρεί το (p+1)...(2p-1)2-2(p-1)!=2((p+1)...(2p-1)-(p-1)!)

Αλλά είναι (p+1).....(2p-1)=(2p-1)(2p-2)......(2p-(p-1))=kp+(p-1)!

και έτσι παίρνουμε το ζητούμενο

#3

Για

είναι άμεσο οπότε υποθέτω ότι

περιττός. Παρατηρώ ότι το

είναι πολλαπλάσιο του $\displaystyle{\binom{2p}{k} = \frac{(2p)!}{k!(2p-k)!}}$ για κάθε $k \in \{1,2,\ldots,2p-1\}$ εκτός από την περίπτωση k = p

. Άρα

$\displaystyle{ 2^{2p} = (1+1)^{2p} = \sum_{k=0}^{2p} \binom{2p}{k} \equiv 2 + \binom{2p}{p} \bmod p}$

Αλλά $2^{2p} = 4^p \equiv 4 \bmod p$ . Άρα $\displaystyle{ \binom{2p}{p} \equiv 2 \bmod p}$ όπως είναι και το ζητούμενο.

#4

Έχουμε ότι $\displaystyle\binom{2p}{p}=\binom{p}{0}^2+\binom{p}{1}^2+\ldots+\binom{p}{p}^2$ .

Είναι εύκολο να δούμε ότι $p\mid\binom{p}{k}$ για κάθε $1\leq k\leq p-1$ οπότε το ζητούμενο είναι άμεσο.

#5

Και ένα σχετικό ερώτημα:

Έστω

πρώτος. Να βρεθεί με πόσους τρόπους μπορούμε να χρωματίσουμε τις μισές κορυφές ενός κανονικού

-γώνου κόκκινες και τις άλλες μισές μπλε. Δυο χρωματισμοί θεωρούνται ίδιοι αν ο ένας προκύπτει από τον άλλο με περιστροφή του πολυγώνου.

Γιάννης Μπόρμπας · #6

Επίσης, από Θ.Wolstenholme's: $\displaystyle{\binom{2p-1}{p-1}\equiv 1 (\mod p^3)}$
Για πρώτους μεγαλύτερους ή ίσους του

#7

Demetres έγραψε:Και ένα σχετικό ερώτημα:

Έστω πρώτος. Να βρεθεί με πόσους τρόπους μπορούμε να χρωματίσουμε τις μισές κορυφές ενός κανονικού -γώνου κόκκινες και τις άλλες μισές μπλε. Δυο χρωματισμοί θεωρούνται ίδιοι αν ο ένας προκύπτει από τον άλλο με περιστροφή του πολυγώνου.

Το απαντάω για να μην ξεχαστεί. Θα υποθέσω ότι ο

είναι περιττός.

Αν δεν λάβουμε υπόψη τις περιστροφές υπάρχουν ακριβώς $\binom{2p}{p}$ τρόποι να κάνουμε τον χρωματισμό.

Λαμβάνοντας υπόψη τις περιστροφές, τους περισσότερους από τους χρωματισμούς τους μετρήσαμε

φορές τον κάθε ένα. Υπάρχουν όμως κάποιοι χρωματισμοί τους οποίους μετρήσαμε λιγότερες φορές. Συγκεκριμένα αυτοί για τους οποίους υπάρχει κάποια περιστροφή που μας δίνει τον ίδιο χρωματισμό.

Έστω $v_0,v_1,\ldots,v_{2p-1}$ οι κορυφές και έστω ότι η περιστροφή που στέλνει την v_0

στην

δίνει τον ίδιο χρωματισμό. Δηλαδή οι $v_0,v_k,v_{2k},\ldots$ έχουν το ίδιο χρώμα.

Αν (k,2p)=1

τότε όλες οι κορυφές έχουν το ίδιο χρώμα.
Αν p|k

αλλά $2 \nmid k$ τότε οι κορυφές χωρίζονται σε

ζεύγη ιδίου χρώματος, τα $\{v_0,v_p\},\{v_1,v_{p+1}\},\ldots,\{v_{p-1},v_{2p-1}\}$ . Αυτό είναι άτοπο αφού

περιττός και οι μισές κορυφές πρέπει να είναι μπλε και οι άλλες μισές κόκκινες.
Αν 2|k

αλλά $p \nmid k$ τότε οι «περιττές» κορυφές πρέπει να έχουν το ένα από τα δύο χρώματα και οι «άρτιες» το άλλο. Υπάρχουν ακριβώς δύο τέτοιοι χρωματισμοί και είναι οι μόνοι που δεν μετρήθηκαν από

φορές.

Άρα το πλήθος των χρωματισμών είναι

$\displaystyle{ \frac{\binom{2p}{p}-2}{2p} + 1}$

Το αρχικό ζητούμενο είναι τώρα άμεσο.

Διαιρετότητα με πρώτους

Διαιρετότητα με πρώτους

Re: Διαιρετότητα με πρώτους

Re: Διαιρετότητα με πρώτους

Re: Διαιρετότητα με πρώτους

Re: Διαιρετότητα με πρώτους

Re: Διαιρετότητα με πρώτους

Re: Διαιρετότητα με πρώτους

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