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

Ιουλίου 16, 2008

Γραμμικός συνδυασμός με φυσικούς αριθμούς ως συντελεστές

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 11:48 μμ

Έστω a, b \ge 1 δύο φυσικοί αριθμοί με μέγιστο κοινό διαιρέτη (a,b)=1. Δείξτε ότι υπάρχει φυσικός αριθμός N τ.ώ. κάθε n \ge N γράφεται ως

n = xa+yb

με x, y φυσικούς αριθμούς.

Advertisements

5 Σχόλια »

  1. Εστω N = x*a + y*b . Θα εξετάσουμε σε
    ποια περίπτωση ο n+1 γράφεται με παρόμοιο
    τρόπο.

    Αρχικα έχουμε N+1 = x*a + y*b + 1. Αυτή
    είναι και η πρώτη σχέση.

    Υποθέτουμε τώρα ότι:
    N+1 = (x – x0)*a + (y+y0)*b
    με x0, y0 φυσικούς και x > x0 είτε
    N+1 = (x + x0)*a + (y-y0)*b
    με x0, y0 φυσικούς και y > y0.
    Ευκολα διαπιστώνει κανείς ότι μόνο έτσι
    είναι δυνατόν να γράψουμε τον N+1.
    Αυτή είναι η δεύτερη σχέση την οποία
    εξισώνουμε με την πρώτη. Καταλήγουμε
    λοιπόν σε μία από τις παρακάτω συνθήκες.
    -x0*a + y0*b = 1 είτε στην
    x0*a – y0*b = 1

    Τώρα εφόσον ο ΜΚΔ των a,b είναι το 1
    είναι φανερό ότι υπάρχουν πράγματι
    x0 και y0 τ.ω να ισχύει μία από τις
    παραπάνω συνθήκες. Χωρίς βλάβη έστω
    ότι ισχύει η πρώτη απ’ αυτές.
    Αρα δείξαμε ότι
    αν ο N γράφεται ως γραμμικός
    συνδυασμός των a,b με x αρκετά
    μεγάλο τ.ω x > x0, τότε
    και ο N+1 γράφεται με παρόμοιο τρόπο.
    Επαγωγικά λοιπόν αυτό ισχύει για κάθε n > N.

    Μένει να βρούμε ένα τέτοιο Ν. Ενα τέτοιο
    εύκολα φαίνεται ότι είναι το a*(x0 + 1) + 1*b.

    Μου αρέσει!

    Σχόλιο από xatzial — Ιουλίου 17, 2008 @ 8:01 πμ

  2. Μου φαίνεται ότι υπάρχει λάθος στο συλλογισμό μου.
    Ναι μεν βρήκα ένα Ν, αλλά η επαγωγή δε μπορεί
    να συνεχιστεί για παραπάνω από 2 βήματα με αυτό
    το Ν. Ωστόσο φαίνετε αρχικά ότι όσο πιο μεγάλο είναι το x σε σχέση
    με το x0, τόσο πιο πολλά βήματα μπορούμε να
    κάνουμε.

    Μου αρέσει!

    Σχόλιο από xatzial — Ιουλίου 17, 2008 @ 10:26 πμ

  3. Υπόδειξη:

    Αφού οι a, b είναι μεταξύ τους πρώτοι τότε κάθε ακέραιος c γράφεται ως c=xa+yb, με x, y ακεραίους, που μπορεί να είναι και αρνητικοί.

    Εξετάστε τον τρόπο γραφής όπως παραπάνω όλων των αριθμών 1,2,\ldots,a+b-1 και έστω M το μέγιστο x ή y που εμφανίζεται, κατ’ απόλυτη τιμή. Χρησιμοποιείστε το M με κάποιο τρόπο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Ιουλίου 17, 2008 @ 7:45 μμ

  4. Κάθε n γράφεται σαν n=k(a+b)+r με 0\leq r \leq a+b-1. Παίρνοντας k=M+1 πχ. κάθε αριθμός μεγαλύτερος του (M+1)(a+b) γράφεται όπως ζητείται, αφού το r=ax+by,|a|,|b|\leq M. Δηλ. n=(k+x)a+(k+y)b και αφού k>x,y οι συντελεστές είναι θετικοί.

    Μου αρέσει!

    Σχόλιο από ikonst — Σεπτεμβρίου 15, 2008 @ 11:03 μμ

  5. Πολύ σωστά.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Σεπτεμβρίου 15, 2008 @ 11:11 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

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