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

Συντονιστές: cretanman, silouan, rek2

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7793
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Δεκ 09, 2017 6:05 pm

Έστω ακέραιος n \geq 3. Να δειχθεί ότι για κάθε k, με 1 \leq k \leq \binom{n}{2}, υπάρχει ένα σύνολο A από n διακεκριμένους θετικούς ακεραίους ώστε το σύνολο

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

να περιέχει ακριβώς k στοιχεία.



Λέξεις Κλειδιά:
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1366
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

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

#2

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Δεκ 14, 2017 12:00 pm

Ονομάζουμε A_k το ζητούμενο σύνολο έτσι ώστε το αντίστοιχο B να έχει k στοιχεία. Θα αποδείξουμε επαγωγικά ότι υπάρχει το A_1 και, αν \displaystyle 1 \leqslant k < \binom{n}{2} και υπάρχει το σύνολο A_k, τότε υπάρχει και το σύνολο A_{k+1}.

Το A_1 αρκεί να αποτελείται από n διακεκριμένους πρώτους (το αντίστοιχο 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). Έστω p πρώτος που δεν διαιρεί κανένα από τα στοιχεία του A_k. Κατασκευάζουμε σύνολο C αντικαθιστώντας τα 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 έχει k+1 στοιχεία και η επαγωγή ολοκληρώθηκε με C = A_{k+1}.


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7793
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Δεκ 14, 2017 1:24 pm

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


Απάντηση

Επιστροφή σε “Θεωρία Αριθμών - Επίπεδο Αρχιμήδη (Seniors)”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης