Μέγιστος κοινός διαιρέτης διωνυμικών

Tolaso J Kos · #1

Έστω $n \geq 2$ . Να υπολογιστεί ο $\displaystyle{d_n:=\gcd \left\{\binom{n}{1}, \binom{n}{2}, \dots , \binom{n}{n-1}\right\}}$ .

stranger · #2

Tolaso J Kos έγραψε: ↑
Κυρ Ιούλ 17, 2022 2:26 pm
Έστω $n \geq 2$ . Να υπολογιστεί ο $\displaystyle{d_n:=\gcd \left\{\binom{n}{1}, \binom{n}{2}, \dots , \binom{n}{n-1}\right\}}$ .

προφανώς.

#3

stranger έγραψε: ↑
Σάβ Αύγ 06, 2022 11:10 pm

Tolaso J Kos έγραψε: ↑
Κυρ Ιούλ 17, 2022 2:26 pm
Έστω $n \geq 2$ . Να υπολογιστεί ο $\displaystyle{d_n:=\gcd \left\{\binom{n}{1}, \binom{n}{2}, \dots , \binom{n}{n-1}\right\}}$ .
προφανώς.

Δεν νομίζω να είναι προφανές. Μάλιστα, ως απάντηση είναι λάθος.

Π.χ. για n=4

, η απάντηση είναι

.

Καλό θα είναι να δίνονται πλήρεις λύσεις, σύμφωνα με τον κανονισμό του forum, ακόμα και για αποτελέσματα που φαίνονται προφανή.

Tolaso J Kos · #4

Το αποτέλεσμα είναι

οταν ο

είναι ο μοναδικός πρώτος διαιρέτης του

και

αλλιώς.

#5

Tolaso J Kos έγραψε: ↑
Κυρ Αύγ 07, 2022 12:30 pm
Το αποτέλεσμα είναι οταν ο είναι ο μοναδικός πρώτος διαιρέτης του και αλλιώς.

Τι νόημα έχει να δοθεί η απάντηση χωρίς λύση;

Αναρτήσεις που περιέχουν μόνο απαντήσεις, είτε σωστές είτε λανθασμένες είναι εκτός του πνεύματος του forum.

stranger · #6

achilleas έγραψε: ↑
Σάβ Αύγ 06, 2022 11:58 pm

stranger έγραψε: ↑
Σάβ Αύγ 06, 2022 11:10 pm

Tolaso J Kos έγραψε: ↑
Κυρ Ιούλ 17, 2022 2:26 pm
Έστω $n \geq 2$ . Να υπολογιστεί ο $\displaystyle{d_n:=\gcd \left\{\binom{n}{1}, \binom{n}{2}, \dots , \binom{n}{n-1}\right\}}$ .
προφανώς.
Δεν νομίζω να είναι προφανές. Μάλιστα, ως απάντηση είναι λάθος.

Π.χ. για , η απάντηση είναι .

Καλό θα είναι να δίνονται πλήρεις λύσεις, σύμφωνα με τον κανονισμό του forum, ακόμα και για αποτελέσματα που φαίνονται προφανή.

Έκανα λάθος.
Αν το

είναι πρώτος η απάντηση είναι

.
Αυτό γιατί το $\binom{n}{k}$ είναι $\frac{n!}{k!(n-k)!}$ το οποίο είναι ακέραιος, οπότε $k!(n-k)! \mid n! = (n-1)!n$ . Τώρα το

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

, αφού το

είναι πρώτος, οπότε $k!(n-k)! \mid (n-1)!$ από το οποίο έπεται ότι $n \mid \binom{n}{k}$ .
Άρα αφού $\binom{n}{1} = n$ , το συμπέρασμα έπεται.

#7

Λήμμα 1: Έστω φυσικός

και πρώτος

. Αν ο

δεν είναι δύναμη του

, τότε $p \nmid d_n$ .

Απόδειξη λήμματος 1: Έστω n = p^k r

όπου

. Πρέπει

. Τότε $\displaystyle \binom{n}{p^k} = \frac{(p^kr)!}{(p^k)!(p^k(r-1))!}$ . Ο εκθέτης της μεγαλύτερης δύναμης του

που διαιρεί το $\binom{n}{p^k}$ είναι ίσος με

$\displaystyle \sum_{i=1}^{\infty} \left(\left\lfloor p^{k-i}r\right\rfloor - \left\lfloor p^{k-i}\right\rfloor - \left\lfloor p^{k-i}(r-1)\right\rfloor \right) = 0$

αφού για $i \leqslant k$ έχουμε $\displaystyle \left\lfloor p^{k-i}r\right\rfloor - \left\lfloor p^{k-i}\right\rfloor - \left\lfloor p^{k-i}(r-1)\right\rfloor = p^{k-i}r - p^{k-i} - p^{k-i}(r-1) = 0$ ενώ για i > k

έχουμε

$\displaystyle \left\lfloor p^{k-i}r\right\rfloor - \left\lfloor p^{k-i}\right\rfloor - \left\lfloor p^{k-i}(r-1)\right\rfloor = \left\lfloor \frac{r}{p^{i-k}}\right\rfloor - \left\lfloor \frac{r-1}{p^{i-k}}\right\rfloor = 0$ αφού $p \nmid r$ . $\square$

Λήμμα 2: Αν n = p^k

όπου

πρώτος, τότε $p^2 \nmid d_n$ .

Απόδειξη λήμματος 2: Έχουμε $\displaystyle \binom{n}{p^{k-1}} = \frac{(p^k)!}{(p^{k-1})!(p^{k-1}(p-1))!}$ . Ο εκθέτης της μεγαλύτερης δύναμης του

που διαιρεί το $\binom{n}{p^{k-1}}$ είναι ίσος με

$\displaystyle \begin{aligned} \sum_{i=1}^{\infty} \left(\left\lfloor p^{k-i}\right\rfloor - \left\lfloor p^{k-1-i}\right\rfloor - \left\lfloor p^{k-1-i}(p-1)\right\rfloor\right) &= \sum_{i=1}^{k} \left(\left\lfloor p^{k-i}\right\rfloor - \left\lfloor p^{k-1-i}\right\rfloor - \left\lfloor p^{k-1-i}(p-1)\right\rfloor\right) \\ &= \sum_{i=1}^{k-1} \left(\left\lfloor p^{k-i}\right\rfloor - \left\lfloor p^{k-1-i}\right\rfloor - \left\lfloor p^{k-1-i}(p-1)\right\rfloor\right) + 1 = 1. \, \square\\ \end{aligned}$

Λήμμα 3: Αν n = p^k

όπου

πρώτος, τότε $p \mid d_n$ .

Απόδειξη λήμματος 2: Για $1 \leqslant r \leqslant n-1$ εκθέτης της μεγαλύτερης δύναμης του

που διαιρεί το $\binom{n}{r}$ είναι ίσος με

$\displaystyle \sum_{i=1}^{\infty} \left(\left\lfloor p^{k-i}\right\rfloor - \left\lfloor \frac{r}{p^i}\right\rfloor - \left\lfloor \frac{p^k-r}{p^i}\right\rfloor\right)$

Κάθε όρος του πιο πάνω αθροίσματος είναι μη αρνητικός ενώ για i=k

ο όρος ισούται με

. $\square$

Από τα πιο πάνω λήμματα εύκολα προκύπτει ότι d_n = 1

αν ο

δεν είναι δύναμη πρώτου και d_n = p

αν ο

είναι δύναμη του πρώτου

.

Μέγιστος κοινός διαιρέτης διωνυμικών

Μέγιστος κοινός διαιρέτης διωνυμικών

Re: Μέγιστος κοινός διαιρέτης διωνυμικών

Re: Μέγιστος κοινός διαιρέτης διωνυμικών

Re: Μέγιστος κοινός διαιρέτης διωνυμικών

Re: Μέγιστος κοινός διαιρέτης διωνυμικών

Re: Μέγιστος κοινός διαιρέτης διωνυμικών

Re: Μέγιστος κοινός διαιρέτης διωνυμικών

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