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

Μαρτίου 16, 2009

Δύναμη του 2

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

Δείξτε ότι υπάρχει k\in\mathbb{N} ώστε τα 2000 τελευταία ψηφία του 2^k (στο δεκαδικό σύστημα) να είναι είτε 1 είτε 2.

Advertisements

2 Σχόλια »

  1. Δεν ξέρω αν υπάρχει πιο απλή λύση. Αρκεί να δείξω

    Λήμμα 1: Υπάρχει θετικός ακέραιος χ με 2000 ψηφία, και όλα τα ψηφία του είτε 1 είτε 2 ώστε x \equiv 0 \bmod 2^{2000}.

    Λήμμα 2: Η ομάδα \left( \mathbb{Z}/5^k\mathbb{Z} \right)^* είναι κυκλική και έχει γεννήτορα το 2.

    Για την λύση του προβλήματος αρκεί να πάρω k \geqslant 2000 ώστε 2^k \equiv x \bmod 5^{2000}. Πράγματι, επειδή 2^k \equiv 0 \equiv x \bmod 2^{2000}, παίρνουμε 2^k \equiv x \bmod 10^{2000}.

    Απόδειξη λήμματος 1: Θα δείξω επαγωγικά ότι για κάθε r, υπάρχει θετικός ακέραιος x_r με r ψηφία, και όλα τα ψηφία του είτε 1 είτε 2 ώστε x_r \equiv 0 \bmod 2^r. Για r = 1 μπορούμε να πάρουμε x_1 = 2. Αν x_r \equiv 0 \bmod 2^{r+1}, τότε παίρνω x_{r+1} = 2 \cdot 10^{r} + x_r. Αν x_r \equiv 2^r \bmod 2^{r+1}, τότε παίρνω x_{r+1} = 10^{r} + x_r.

    Απόδειξη λήμματος 2: Επαγωγή στο κ. Για κ=1, ισχύει. Παρατηρώ ότι η ομάδα έχει 4 \cdot 5^{k-1} στοιχεία και ότι η τάξη του 2 σε αυτήν την ομάδα πρέπει να είναι πολλαπλάσιο του 4. Άρα αρκεί να δείξω ότι 2^{4 \cdot 5^{n-2}} \neq 1 \bmod 5^n. Αλλά 2^{4 \cdot 5^{n-2}} = (1 + 3 \cdot 5)^{5^{n-2}} \equiv 1 + 3 \cdot 5^{n-1} \bmod 5^n.

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Απρίλιος 4, 2009 @ 8:44 μμ

  2. Συγγνώμη για την καθυστερημένη απάντηση. Η λύση σου είναι βέβαια σωστή. Την ξαναγράφω λίγο πιο αναλυτικά για την κατανόηση όλων.

    Έστω G_k=(\mathbb{Z}/5^k\mathbb{Z})^* η πολλαπλασιαστική ομάδα που προκύπτει από το δακτύλιο \mathbb{Z}/5^k\mathbb{Z} αν αφαιρέσουμε τους διαιρέτες του μηδενός. Εύκολα βλέπει κανείς ότι 2^m\in G_k για κάθε k,m\in\mathbb{N}. Έστω τώρα d_k η τάξη του 2 στην G_k.
    Παρατηρήστε ότι αν 2^m\equiv 1 (\bmod 5^k) τότε d_k/m.
    Εφόσον λοιπόν 2^{d_{k+1}}\equiv 1 (\bmod 5^k) έχουμε d_k/d_{k+1} για κάθε k\in\mathbb{N}. Παρατηρήστε επίσης ότι d_1=4 άρα 4/d_k για κάθε k\in\mathbb{N}.
    Τέλος από το μικρό θεώρημα του Fermat έχουμε ότι 2^{4\cdot 5^{k-1}}\equiv 1 (\bmod 5^k) όποτε
    d_k/4\cdot 5^{k-1} και επειδή όπως εξηγεί ο Δημήτρης 2^{4 \cdot 5^{k-2}} \neq 1 (\bmod 5^k)
    έχουμε ότι d_k=4\cdot 5^{k-1}=|G_k| και άρα το 2 είναι γεννήτορας της G_k. Αν πάρουμε τώρα k\ge 2000 ώστε 2^k \equiv x (\bmod 5^{2000}) με το x όπως στο λήμμα 1, έχουμε 2^k-x=5^{2000}j για κάποιο ακέραιο j που επειδή το αριστερό μέλος είναι πολλαπλάσιο του 2^{2000} θα είναι και αυτός πολλαπλάσιο του 2^{2000}. Άρα,
    2^k \equiv x (\bmod 10^{2000}) απ’ όπου προκύπτει το ζητούμενο.

    Μου αρέσει!

    Σχόλιο από Michalis Loulakis — Απρίλιος 7, 2009 @ 12:52 μμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

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

Λογότυπο WordPress.com

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

Φωτογραφία Twitter

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

Φωτογραφία Facebook

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

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

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

Σύνδεση με %s

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

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