θεωρια αριθμών

irakleios · #1

Πως μπορούμε να βρούμε τα 3 τελευταία ψηφία του αριθμού : $79^{39^{29}}$ ;

#2

Ηράκλειε καλωσόρισες στο mathematica.

Να σε παρακαλέσω αν μπορείς να γράφεις στα ελληνικά αντί σε greeklish.

Για την άσκηση τώρα ας προσπαθήσουμε πρώτα να λύσουμε μια πιο εύκολη άσκηση. Μπορείς να βρεις το τελευταίο ψηφίο του αριθμού;

irakleios · #3

Eυχαριστώ για το καλωσόρισμα!!!
λοιπόν το τελευταίο ψηφίο πρέπει να είναι το 9.
έχουμε υψώσει το 79 σε περιττή δύναμη...
αλλά τα 3 ψηφία δεν τα βρίσκω ...

#4

Ωραία. Ας βρούμε τώρα τα τελευταία δύο ψηφία.

Η βασική παρατήρηση για το τελευταίο ψηφίο ήταν ότι αυτό είναι 9 αν η δύναμη είναι περιττή και 1 αν η δύναμη είναι άρτια. Κάτι παρόμοιο αλλά πιο πολύπλοκο συμβαίνει και για τα δυο τελευταία ψηφία.

Ας πολλαπλασιάσουμε το 79 με τον εαυτό του συνέχεια και ας γράψουμε κάτω τα δυο τελευταία ψηφία. Με την βοήθεια μιας υπολογιστικής βρίσκω ότι τα δυο τελευταία ψηφία είναι

79,41,39,81,99,21,59,61,19,01

και μετά ξαναρχίζει από την αρχή.

Άρα τα δυο τελευταία ψηφία θα είναι 79 αν το τελευταίο ψηφίο του $39^{29}$ είναι 1, 41 αν το τελευταίο ψηφίο του $39^{29}$ είναι 2, ... , 01 αν το τελευταίο ψηφίο του $39^{29}$ είναι 0.

Γνωρίζουμε ότι το τελευταίο ψηφίο του $39^{29}$ είναι 9 άρα τα δυο τελευταία ψηφία του $79^{39^{29}}$ είναι 19.

Η ίδια διαδικασία μπορεί να ακολουθηθεί και για τα τρία τελευταία ψηφία κ.τ.λ.

Απέφυγα πιο πάνω να αναφερθώ σε ισοϋπόλοιπα (modulo) η γνώση των οποίων δεν είναι απαραίτητη για να λυθεί η άσκηση αλλά ευκολύνουν κατά πολύ την όποια λύση και σε βάζουν στον σωστό τρόπο σκέψης. Τα έχεις ξανασυναντήσει ή όχι;

irakleios · #5

ναι τα mod τα γνωρίζω
δοκίμασα και μέσω αυτών αλλά μάταια
θα με ενδιέφερε πολύ η λύση με τα modulo
ευχαριστώ πολύ για το ενδιαφέρον

Eagle · #6

Το αποτέλεσμα αν δεν έχω κάνει λάθος στις πράξεις είναι:319.

Αρχικά θέτουμε $\displaystyle\alpha = 39^{29}$ .Άρα αρκεί να βρούμε τα 3 τελευταία ψηφία του αριθμού $\displaystyle79^{\alpha}$ .Όμως
$\displaystyle\alpha = 39^{29}=\left( 39^2\right)^{14}\cdot39\equiv 521^{14}\cdot39\equiv 441^7\cdot39\equiv 481^3\cdot199\equiv 361\cdot719\equiv 559\left( \mod 10^3\right)$ .
Επομένως τα 3 τελευταία ψηφία του αριθμού $\displaystyle\alpha$ είναι 559.Τώρα αρκεί να βρούμε τα 3 τελευταία ψηφία του αριθμού $\displaystyle79^{559}$ .Όμως
$\displaystyle79^{559}=\left( 79^2\right)^{279}\cdot79\equiv 241^{279}\cdot79\equiv 521^{93}\cdot79\equiv \left( 521^2\right)^{46}\cdot159\equiv 441^{46}\cdot159\equiv 481^{23}\cdot159\equiv 361^{11}\cdot479\equiv 321^5\cdot919\equiv 41^2\cdot999\equiv 681\cdot999\equiv 319\left(\mod 10^3 \right)$ .
Συνεπώς τα 3 τελευταία ψηφία του αριθμού $\displaystyle79^{39^{29}}$ είναι 319

Δημήτρης

ΥΓ.Δεν έγραψα λεπτομερώς τις πράξεις διότι είναι αρκετές αλλά εύκολες(απλοί πολλαπλασιασμοί)

dement · #7

Eagle έγραψε:Το αποτέλεσμα αν δεν έχω κάνει λάθος στις πράξεις είναι:319.

Αρχικά θέτουμε $\displaystyle\alpha = 39^{29}$ .Άρα αρκεί να βρούμε τα 3 τελευταία ψηφία του αριθμού $\displaystyle79^{\alpha}$ .Όμως
$\displaystyle\alpha = 39^{29}=\left( 39^2\right)^{14}\cdot39\equiv 521^{14}\cdot39\equiv 441^7\cdot39\equiv 481^3\cdot199\equiv 361\cdot719\equiv 559\left( \mod 10^3\right)$ .
Επομένως τα 3 τελευταία ψηφία του αριθμού $\displaystyle\alpha$ είναι 559.Τώρα αρκεί να βρούμε τα 3 τελευταία ψηφία του αριθμού $\displaystyle79^{559}$ .

Προσοχη, η συλλογιστικη εδω δεν ειναι σωστη. Υποθετει οτι, αν $m \equiv n \mod p$ τοτε $a^m \equiv a^n \mod p$ . Αυτο ομως δεν ισχυει, π.χ. $2^0 = 1 \mod 10, \ 2^{10} = 4 \mod 10$ .

Δημητρης

#8

Βάζω μια προσέγγιση μιας και έμεινε άλυτο. (Ελπίζω οι πράξεις να είναι σωστές.)

Θέλουμε να βρούμε το $79^{39^{29}} \bmod 8$ και το $79^{39^{29}} \bmod 125$ . Αυτά τα δύο θα μας δώσουν το $79^{39^{29}} \bmod 1000$ που είναι και η απάντηση που ζητάμε.

Έχουμε $79^{39^{29}} \equiv (-1){39^{29}} \equiv -1 \bmod 8$ αφού ο $39^{29}$ είναι περιττός.

Για το $\bmod 125$ βοηθάει να γνωρίζουμε το θεώρημα του Euler που λέει ότι αν τα a,n

είναι πρώτοι μεταξύ τους, τότε $a^{\phi(n)} \equiv 1 \bmod n$ . Άρα $79^{100} \equiv 1 \bmod 125$ .

Θέλουμε λοιπόν να υπολογίσουμε το $39^{29} \bmod 100$ . Έχουμε $39^{29} \equiv (-1)^{29} \equiv -1 \bmod 4$ και $39^{29} \equiv 14^{29} \equiv 14^{9} \bmod 25$ , όπου στην τελευταία ισοτιμία χρησιμοποιήσαμε το θεώρημα του Euler.

Έχουμε $14^2 = 196 \equiv -4 \bmod 25, 14^4 \equiv 16 \bmod 25, 14^8 \equiv 81 \equiv 6 \bmod 25$ και άρα $14^9 \equiv 84 \equiv 9 \bmod 25$ .

Άρα $39^{29} \equiv 59 \bmod 100$ και άρα $79^{39^{29}} \equiv 79^{59} \bmod 125$ .

Θα υπολογίσουμε διαδοχικά τα $79^2,79^3,79^6,7^7,79^{14},79^{28},79^{29},79^{58}$ και $79^{59} \bmod 125$ .

$79^2 = (75 + 4)^2 \equiv -400 + 16 \equiv 116 \equiv -9 \bmod 125$
$79^3 \equiv -711 \equiv 39 \bmod 125$
$79^6 \equiv (50 - 11)^2 \equiv -1100 + 121 \equiv 21 \bmod 125$
$79^7 \equiv (75 + 4)(25-4) \equiv -200 - 16 \equiv 34 \bmod 125$
$79^{14} \equiv (25+9)^2 \equiv 450 + 81 \equiv 31 \bmod 125$
$79^{28} \equiv (25+6)^2 \equiv 300 + 36 \equiv 86 \bmod 125$
$79^{29} \equiv (75 + 4)(75 + 11) \equiv 44 \bmod 125$
$79^{58} \equiv (50-6)^2 \equiv -600 + 36 \equiv 61 \bmod 125$
και τέλος
$79^{59} \equiv (50+11)(75+4) \equiv 200 + 75 + 44 \equiv 69$

Άρα $79^{39^{29}} \equiv 69 \bmod 125$ και άρα $79^{39^{29}} \equiv 319 \bmod 1000$

θεωρια αριθμών

θεωρια αριθμών

Re: θεωρια αριθμών

Re: θεωρια αριθμών

Re: θεωρια αριθμών

Re: θεωρια αριθμών

Re: θεωρια αριθμών

Re: θεωρια αριθμών

Re: θεωρια αριθμών

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