Ακριβώς κ διαφορετικοί μέγιστοι κοινοί διαιρέτες

#1

Έστω ακέραιος $n \geq 3$ . Να δειχθεί ότι για κάθε

, με $1 \leq k \leq \binom{n}{2}$ , υπάρχει ένα σύνολο

από

διακεκριμένους θετικούς ακεραίους ώστε το σύνολο

$\displaystyle B = \{\gcd(x, y): x, y \in A, x \neq y \}$

να περιέχει ακριβώς

στοιχεία.

dement · #2

Ονομάζουμε A_k

το ζητούμενο σύνολο έτσι ώστε το αντίστοιχο

να έχει

στοιχεία. Θα αποδείξουμε επαγωγικά ότι υπάρχει το A_1

και, αν $\displaystyle 1 \leqslant k < \binom{n}{2}$ και υπάρχει το σύνολο A_k

, τότε υπάρχει και το σύνολο $A_{k+1}$ .

Το A_1

αρκεί να αποτελείται από

διακεκριμένους πρώτους (το αντίστοιχο $B = \{ 1 \}$ ).

Έστω ότι υπάρχει το A_k

με $\displaystyle 1 \leqslant k < \binom{n}{2}$ . Τότε (αρχή περιστερώνα) θα υπάρχουν $n_1, n_2, n_3, n_4 \in A_k$ με $n_1 \neq n_2 \wedge n_3 \neq n_4 \wedge \gcd(n_1,n_2) = \gcd(n_3, n_4)$ . Έστω

πρώτος που δεν διαιρεί κανένα από τα στοιχεία του A_k

. Κατασκευάζουμε σύνολο

αντικαθιστώντας τα n_1, n_2

με τα $n_1' \equiv pn_1, n_2' \equiv pn_2$ ενώ για κάθε άλλο στοιχείο n_k

αφήνουμε $n_k' \equiv n_k$ . Παρατηρούμε ότι για κάθε $\{n_q, n_r \} \neq \{n_1, n_2 \}$ ισχύει $\gcd(n_q', n_r') = \gcd(n_q, n_r)$ ενώ επίσης $\gcd(n_1', n_2') = p \gcd(n_1, n_2)$ . Έτσι, το σύνολο των ανά δύο ΜΚΔ του

έχει

στοιχεία και η επαγωγή ολοκληρώθηκε με $C = A_{k+1}$ .

#3

Ωραία. Το πήρα από εδώ. Η δική μου λύση ήταν αρκετά κοντινή σε αυτήν που δόθηκε εκεί.

Ακριβώς κ διαφορετικοί μέγιστοι κοινοί διαιρέτες

Ακριβώς κ διαφορετικοί μέγιστοι κοινοί διαιρέτες

Re: Ακριβώς κ διαφορετικοί μέγιστοι κοινοί διαιρέτες

Re: Ακριβώς κ διαφορετικοί μέγιστοι κοινοί διαιρέτες

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