Προβλήματα Μαθηματικών

Μαΐου 8, 2008

Σχετικά πρώτοι

Filed under: Λυμένα Προβλήματα — Michalis Loulakis @ 8:01 μμ

Επιλέγουμε τυχαία δύο αριθμούς από το σύνολο \{1,2,\cdots,N\} και έστω P_N η πιθανότητα αυτοί να είναι σχετικά πρώτοι. Ποιό είναι το lim_{N\to\infty} P_N; (Το πρόβλημα συνήθως παραφράζεται ως εξής «ποιά είναι η πιθανότητα δύο φυσικοί αριθμοί να είναι σχετικά πρώτοι;»)

Advertisements

3 Σχόλια »

  1. Αν p ένας πρώτος στο \{1,2,...,N\} τότε η πιθανότητα οι δύο αριθμοί που επιλέγουμε να μη διαιρούνται από τον p ταυτόχρονα είναι 1-\frac{\left[\frac{N}{p}\right]\left(\left[\frac{N}{p}\right]-1\right)}{N(N-1)} που καθώς το N τείνει στο άπειρο τείνει στο 1-\frac{1}{p^2}.
    Συνεπώς το ζητούμενο όριο ισούται με
    \displaystyle \lim_{N \to \infty} \prod_{p\ prwtos \le N}\left(1-\frac{1}{p^2}\right)=\prod_{p\ prwtos}\left(1-\frac{1}{p^2}\right)=

    \displaystyle =\left(\sum_{n=1}^{\infty}\frac{1}{n^2}\right)^{-1}=\frac{6}{\pi^2}.

    Μου αρέσει!

    Σχόλιο από steliosdes — Μαΐου 11, 2008 @ 3:31 πμ

  2. Δε βλέπω κάποιο λάθος στην απόδειξη του παιδιού, νομίζω ότι αυτός είναι ο πιο εύκολος τρόπος απόδειξης. Κάτι που είχα σκεφτεί εγώ που απαιτεί πιο περίπλοκους υπολογισμούς είναι να μετρήσεις κατευθείαν όλα τα ζεύγη (m,n) όπου m,n μικρότεροι ή ίσοι του Ν τέτοια ώστε να έχουν μέγιστο κοινό διαιρέτη 1. Αυτό το κάνεις ως εξής: αν τοποθετήσεις σε ένα ΝxN τετράγωνο όλα τα ζεύγη (m,n) στη μορφή
    (1,1) (1,2) … (1,Ν)
    (2,1) (2,2) …
    (2,2)
    ..
    (Ν,1) … (Ν,Ν)

    παρατηρείς ότι η το πλήθος των σχετικά πρώτων ζευγών κάτω από τη διαγώνιο είναι ίσο με αυτό πάνω από τη διαγώνιο, και άρα αρκεί να μετρήσεις αυτό της κάτω διαγωνίου. Γι’αυτό αρκεί να προσθέσεις τα πλήθη των σχετικά πρώτων σε κάθε γραμμή(μετράς από την αρχή της γραμμής μέχρι τη διαγώνιο). Όμως στη γραμμή k αυτό το πλήθος είναι το φ(k) όπου φ η συνάρτηση του Euler, επομένως το συνολικό πλήθος ζευγών είναι \frac{1}{N^2}\sum_{i=1}^N \varphi(k) και το ότι αυτό τείνει στο 6/π^2 καθώς αυξάνει το Ν έπεται από το ότι η μέση τάξη της συνάρτησης του Euler είναι της (6/π^2)Ν, κάτι που μπορεί να δει κανείς σε οποιοδήποτε βιβλίο αναλυτικής θεωρίας αριθμών.

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

    Μου αρέσει!

    Σχόλιο από ikonst — Μαΐου 13, 2008 @ 2:27 πμ

  3. Tο αποτέλεσμα είναι βέβαια σωστό. Μάλλον όμως δεν είναι προφανές γιατί στο επιχείρημα του steliosdes «το ζητούμενο όριο ισούται με ….». Όπως εξηγεί ο ikonst
    \displaystyle P_N=\frac{1+2\sum_{k=2}^N\varphi(k)}{N^2}
    (υποθέτoντας ότι επαναλήψεις επιτρέπονται- έτσι κι αλλιώς στο όριο η επιλογή με ή χωρίς επανάληψη δίνει το ίδιο αποτέλεσμα). Από την αρχή εγκλεισμού αποκλεισμού μπορούμε εναλλακτικά να εκφράσουμε το αποτέλεσμα χρησιμοποιώντας τη συνάρτηση του Möbius:
    \displaystyle \frac{1}{N^2}\sum_{k=1}^N \mu(k)\big[\frac{N}{k}\big]^2
    που συγκλίνει στο
    \displaystyle \sum_k \frac{\mu(k)}{k^2}=\prod_{p}(1-\frac{1}{p^2}).
    Αυτή είναι και η συνηθισμένη απόδειξη του αποτελέσματος του επικαλείται ο ikonst.

    Μου αρέσει!

    Σχόλιο από loulakis — Μαΐου 13, 2008 @ 6:06 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Blog στο WordPress.com.

Αρέσει σε %d bloggers: