Βασική θεωρία αριθμών!

#1

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

Παρακαλώ για πλήρεις και αναλυτικές λύσεις.

1η)

α) Αν $\displaystyle{n}$ θετικός ακέραιος, να αποδειχθεί ότι $\displaystyle{30/(n^5-n),}$ ή, όπως αλλιώς γράφεται $\displaystyle{n^5\equiv n\mod 30.}$

β) Αν μάλιστα, ο $\displaystyle{n}$ είναι περιττός, να αποδειχθεί ότι $\displaystyle{240/(n^5-n),}$ δηλαδή $\displaystyle{n^5\equiv n\mod 240.}$

2η)

Να αποδειχθεί ότι το $\displaystyle{4}$ διαιρεί τον αριθμό $\displaystyle{19^{19}+69^{69}.}$

3η)

Να βρεθούν τα τρία τελευταία ψηφία του αριθμού $\displaystyle{13^{398}.}$

$\displaystyle{\rule{500pt}{2pt}}$

Πηγή: Winning Solutions, Edward Lozansky, Cecil Rousseau, Springer Verlag, 1996

Andreas Dalaoutis · #2

Θάνο πολύ ωραία η πρωτοβουλία σου.
Για την πρώτη.

α) Καταρχάς $n^5\equiv n\,\bmod\,5$ από το Θεώρημα Fermat. Άρα 5|n^5+n

Επίσης είναι: n^5-n=n(n^4-1)=n(n-1)(n^3+n^2+n+1)=(n-1)n(n+1)(n^2+1)

το οποίο διαιρείται από το

.

Επομένως τελικά είναι $n^5\equiv n\,\bmod\,30$ αφού 5|n^5+n

και

.

β) Αφού

περιττός γράφεται στη μορφή: n=2k+1

.

Άρα

το οποίο διαιρείται από το

.

Επομένως 16|n^+n

αλλά και

. Άρα

, με

περιττό.

#3

matha έγραψε:2η)

Να αποδειχθεί ότι το $\displaystyle{4}$ διαιρεί τον αριθμό $\displaystyle{19^{19}+69^{69}.}$

Παρατηρούμε ότι:

$\displaystyle{19^2 \equiv 1(mod20)\Rightarrow (19^{2})^{9}\equiv 1(mod20)\Rightarrow 19^{18}\equiv 1(mod20)\Rightarrow}$

$\displaystyle{19^{18}.19\equiv 1.19(mod20)\Rightarrow 19^{19}\equiv 19(mod20)}$ , ΣΧΕΣΗ (1)

Επίσης:

$\displaystyle{69^2 \equiv 1(mod20)\Rightarrow (69)^{2})^{34}\equiv 1(mod20)\Rightarrow 69^{68}\equiv 1(mod20)\Rightarrow}$

$\displaystyle{69^{68}.69\equiv 69(mod20)\Rightarrow 69^{69}\equiv 69(mod20)}$ , ΣΧΕΣΗ (2)

Προσθέτουμε κατά μέλη τις σχέσεις (1) και (2) και έχουμε:

$\displaystyle{19^{19}+69^{69}\equiv 88(mod20)\Rightarrow 19^{19}+69^{69}-88=}$ πολ

Άρα:

$\displaystyle{19^{19}+69^{69}=20k+88=4(5k+22)=}$ πολ

.

Άρα $\displaystyle{4|19^{19}+69^{69}}$

#4

Ωραία!

Ας γράψω αναλυτικότερα τα θεωρήματα, τα οποία χρησιμοποιήθηκαν παραπάνω:

1ο:

Το γινόμενο $\displaystyle{n}$ διαδοχικών ακεραίων διαιρείται με το $\displaystyle{n!}$

Στην παραπάνω άσκηση εμφανίζεται το γινόμενο $\displaystyle{(n-1)n(n+1),}$ δηλαδή το γινόμενο τριών διαδοχικών ακεραίων. Επομένως, το $\displaystyle{(n-1)n(n+1)}$ διαιρείται με το $\displaystyle{3!=1\cdot 2\cdot 3=6.}$

2ο:

Αν ένας αριθμός διαιρείται από τους $\displaystyle{a,b}$ και αυτοί είναι πρώτοι μεταξύ τους, δηλαδή ο μέγιστος κοινός διαιρέτης τους ισούται με $\displaystyle{1}$ , τότε ο αριθμός διαιρείται και από το γινόμενό τους $\displaystyle{ab.}$

Στην άσκηση παραπάνω, απεδείχθη ότι ένας αριθμός διαιρείται και από το $\displaystyle{16}$ και από το $\displaystyle{15}$ και επειδή $\displaystyle{MK \Delta (15,16)=1,}$ ο αριθμός θα διαιρείται και από το $\displaystyle{15\cdot 16=240.}$

3ο: (Μικρό θεώρημα του Fermat)

Αν $\displaystyle{p}$ πρώτος αριθμός, ισχύει $\displaystyle{p/(a^p-a),}$ για κάθε ακέραιο $\displaystyle{a.}$

Αυτό γράφεται και ως $\displaystyle{\boxed{a^p\equiv a\mod p}}$

Μάλιστα, ισχύει και κάτι ισχυρότερο:

Αν $\displaystyle{p}$ πρώτος και δεν διαιρεί τον ακέραιο $\displaystyle{a}$ , ισχύει

$\displaystyle{p/(a^{p-1}-1),}$ δηλαδή $\displaystyle{a^{p-1}\equiv 1\mod p}$ .

Το μικρό θεώρημα του Fermat, είναι μερική περίπτωση ενός γενικότερου αποτελέσματος, γνωστού ως

Θεώρημα του Euler:

Αν $\displaystyle{a,m}$ ακέραιοι, πρώτοι μεταξύ τους, ισχύει

$\displaystyle{a^{\phi (m)}\equiv 1\mod m,}$

όπου $\displaystyle{\phi}$ η συνάρτηση Euler.

Αυτή ορίζεται με τον ακόλουθο απλό τρόπο:

Αν $\displaystyle{m}$ είναι ένας θετικός ακέραιος, το $\displaystyle{\phi (m)}$ ισούται με το πλήθος των ακεραίων $\displaystyle{k}$ ( $\displaystyle{1\leq k\leq m}$ ) οι οποίοι είναι πρώτοι ως προς το $\displaystyle{m.}$

π.χ. $\displaystyle{\phi (10)=4,}$ αφού από τους ακεραίους $\displaystyle{1,2,3,4,5,6,7,8,9,10,}$ ακριβώς οι $\displaystyle{1,3,7,9}$ είναι πρώτοι προς το $\displaystyle{10.}$

Αποδεικνύεται ότι αν

$\displaystyle{m=p_1 ^{q_1}p_2 ^{q_2}\cdots p_k^{q_k}}$

είναι η ανάλυση του ακεραίου $\displaystyle{m}$ σε γινόμενο πρώτων παραγόντων, ισχύει

$\displaystyle{\boxed{\phi (m)=m\left(1-\frac{1}{p_1} \right)\left(1-\frac{1}{p_2} \right)\cdots \left(1-\frac{1}{p_k} \right)}}$

irakleios · #5

matha έγραψε: 2η)

Να αποδειχθεί ότι το $\displaystyle{4}$ διαιρεί τον αριθμό $\displaystyle{19^{19}+69^{69}.}$

Ξεφεύγοντας λίγο από την μεθοδολογία .

Αρκεί να αποκλείσω ότι ο φυσικός $\displaystyle{19^{19}+69^{69}}$ δεν είναι της μορφής 4n+1

ή

. Δεν μπορεί να είναι της μορφής 4n+1

ή

αφού το άθροισμα είναι άρτιος αριθμός .
Έστω ότι $\displaystyle{19^{19}+69^{69}} = 4n + 2$ αυτό γράφεται $(19 - 1)(19^{18} + 19^{17} + ...+19 + 1) + 68m = 4n$ ή 18k + 68m = 4n

όπου

περιττός , ή 9k + 34m = 2n

, δηλαδή περιττός = άρτιος , άτοπο .

Τελικά $\displaystyle{19^{19}+69^{69}} = 4n$

#6

matha έγραψε:
2η)

Να αποδειχθεί ότι το $\displaystyle{4}$ διαιρεί τον αριθμό $\displaystyle{19^{19}+69^{69}.}$

Πιο απλά η

η. Από το ανάπτυγμα διωνύμου έχουμε

$19^{19}=(20-1)^{19} = 20k + (-1)^{19} = 4k' - 1$ και $69^{69}= (68+1)^{69} = 68l + 1^{69} = 4l' +1$ . Προσθέτω τώρα κατά μέλη.

Μ.

irakleios · #7

Mihalis_Lambrou έγραψε:
matha έγραψε:
2η)

Να αποδειχθεί ότι το $\displaystyle{4}$ διαιρεί τον αριθμό $\displaystyle{19^{19}+69^{69}.}$

Πιο απλά η η. Από το ανάπτυγμα διωνύμου έχουμε

$19^{19}=(20-1)^{19} = 20k + (-1)^{19} = 4k' - 1$ και $69^{69}= (68+1)^{69} = 68l + 1^{69} = 4l' +1$ . Προσθέτω τώρα κατά μέλη.

Μ.

#8

matha έγραψε:

3η)

Να βρεθούν τα τρία τελευταία ψηφία του αριθμού $\displaystyle{13^{398}.}$

Καλόόό. Μετά από αρκετή σκέψη ... κατέβηκε η ιδέα.

Θέλουμε το $\displaystyle{13^{398}\mod (1000)}$ . Θα γίνει χρήση των

α) $13 ^ {\phi (1000)} \equiv 1 \mod (1000)$ . Εδώ $\phi (1000 ) = \phi (2^35^3) = 2^35^3\left(1- \frac {1}{2} \right) \left(1- \frac {1}{5}\right) = 400$ , οπότε $3^{400}\equiv 1 \mod (1000)$ .

και, εδώ είναι η ιδέα που μου πήρε κάποια ώρα να σκεφτώ,

β) $77 \cdot 13 = 1001$ (ήξερα εκ των προτέρων ότι $7 \cdot 11 \cdot 13 = 1001$ ).

Έτσι

$\displaystyle{13^{398}\mod (1000) =13^{398} \cdot 1001\cdot 1001 \mod (1000) = 13^{398} \cdot 77^2 \cdot 13^2\mod (1000) }$

$\displaystyle{= 13^{400} \cdot 77^2\mod (1000)= 1 \cdot 77^2\mod (1000) = 6929 \mod (1000)= 929 \mod (1000)}$ .

Άρα τα τρία τελευταία ψηφία είναι 929

.

Φιλικά,

Μιχάλης

#9

Αφού λύθηκαν οι προηγούμενες, ας συνεχίσουμε:

4η)

Αν $\displaystyle{p\color{red}>3}$ πρώτος, να αποδειχθεί ότι $\displaystyle{42p/(3^p-2^p-1)}$

5η)

Αν $\displaystyle{n}$ είναι θετικός, άρτιος ακέραιος, να αποδειχθεί ότι

$\displaystyle{(n^2-1)/(2^{n!}-1).}$

* Προσθήκη. Ευχαριστώ τον Αντρέα Νταλαούτη.

Πηγή: Σημειώσεις Θεωρίας Αριθμών του Αλέξανδρου Συγκελάκη, από το θερινό σχολείο της Ε.Μ.Ε στη Λεπτοκαρυά.

#10

matha έγραψε: 4η)

Αν $\displaystyle{p\color{red}>3}$ πρώτος, να αποδειχθεί ότι $\displaystyle{42p/(3^p-2^p-1)}$

Για $p=5, \, p=7$ άμεσο. Για p>7

, το μικρό θεώρημα Fermat δίνει $\displaystyle{ 3^p-2^p-1 \equiv ( 3 - 2 - 1) \mod p \equiv 0 \mod p }$ . Άρα p | 3^p-2^p-1

.

Μένει να δείξουμε $2 | 3^p-2^p-1 , \, 3 | 3^p-2^p-1 , \, 7 | 3^p-2^p-1$ οπότε και το γινόμενό τους $2\cdot 3 \cdot 7=42$ θα διαιρεί τον

.

Πράγματι, προφανώς ο 3^p-2^p-1=(

περιττός

άρτιος

περιττός

άρτιος, που δείχνει το πρώτο. Επίσης
$3^p-2^p-1 \equiv 0-2^p - 1 \mod 3 \equiv -(-1)^p - 1 \mod 3 \equiv 0 \mod 3$ που δείχνει το δεύτερο. Μένει το τελευταίο, για το οποίο θα κάνουμε χρήση του γεγονότος ότι οι πρώτοι αριθμοί από τον

και πέρα είναι της μορφής 6k+1

ή

(απλό και γνωστό). Για p=6k+1

είναι

$3^p-2^p-1 = 3 ^{6k+1} - 2^{6k+1}-1 = 3 \cdot 729^k - 2 \cdot 64 ^k-1$
$\equiv 3 \cdot 1^k - 2 \cdot 1 ^k-1 \mod 7 \equiv 0 \mod 7$

και όμοια για p=6k+5

είναι

$3^p-2^p-1 = 3 ^{6k+5} - 2^{6k+5}-1 = 3^5 \cdot 729^k - 2^5 \cdot 64 ^k-1$
$\equiv 243 \cdot 1^k - 32 \cdot 1 ^k-1 \mod 7 \equiv 210 \mod 7 \equiv 0 \mod 7$ , όπως θέλαμε.

Φιλικά,

Μιχάλης

Γιώτα · #11

Μια ακομά λύση για την άσκηση 2:

$19\equiv -1(mod4)\Leftrightarrow 19^{19}\equiv -1(mod4)$
$69\equiv 1(mod4)\Leftrightarrow 69^{69}\equiv 1(mod4)$
προσθέτω κατά μέλη
$19^{19}+ 69^{69}\equiv 0(mod4)$

Mikesar · #12

matha έγραψε: 5η)

Αν $\displaystyle{n}$ είναι θετικός, άρτιος ακέραιος, να αποδειχθεί ότι

$\displaystyle{(n^2-1)/(2^{n!}-1).}$

Επειδή ο

είναι άρτιος, οι αριθμοί n-1,n+1,2

είναι ανά δύο πρώτοι μεταξύ τους.
Επιπλέον, $\phi(k)\leq k-1$ (με την ισότητα να ισχύει για

πρώτο) το οποίο είναι προφανές από τον ορισμό της συνάρτησης.
Από το θεώρημα του Euler έχω:
$2^{\phi(n-1)}\equiv1(mod \ n-1)$
Υψώνοντας στην $\displaystyle\frac{n!}{\phi(n-1)}$ (το οποίο είναι ακέραιος) έχω ότι $2^{n!}-1\equiv0(mod \ n-1)\Leftrightarrow n-1|2^{n!}-1$
Απολύτως όμοια αποδεικνύω πως $n+1|2^{n!}-1$
Επειδή οι αριθμοί n-1,n+1

είναι πρώτοι μεταξύ τους και διαιρούν τον ίδιο αριθμό, έπεται ότι $n^2-1|2^{n!}-1$
Εύχομαι να μην έχω σφάλμα

#13

Mikesar έγραψε:
matha έγραψε: 5η)

Αν $\displaystyle{n}$ είναι θετικός, άρτιος ακέραιος, να αποδειχθεί ότι

$\displaystyle{(n^2-1)/(2^{n!}-1).}$
Επειδή ο είναι άρτιος, οι αριθμοί είναι ανά δύο πρώτοι μεταξύ τους.
Επιπλέον, $\phi(k)\leq k-1$ (με την ισότητα να ισχύει για πρώτο) το οποίο είναι προφανές από τον ορισμό της συνάρτησης.
Από το θεώρημα του Euler έχω:
$2^{\phi(n-1)}\equiv1(mod \ n-1)$
Υψώνοντας στην $\displaystyle\frac{n!}{\phi(n-1)}$ (το οποίο είναι ακέραιος) έχω ότι $2^{n!}-1\equiv0(mod \ n-1)\Leftrightarrow n-1|2^{n!}-1$
Απολύτως όμοια αποδεικνύω πως $n+1|2^{n!}-1$
Επειδή οι αριθμοί είναι πρώτοι μεταξύ τους και διαιρούν τον ίδιο αριθμό, έπεται ότι $n^2-1|2^{n!}-1$
Εύχομαι να μην έχω σφάλμα

Μια χαρά είναι!

#14

Και μια ακόμα, πάνω στην θεωρία που έχει αναφέρει ο Θάνος (με την επί πλέον παρατήρηση, ότι αν ένας αριθμός

, είναι πρώτος, τότε οι αριθμοί $\displaystyle{1 , 2 , 3 , . . . , p-1}$ , είναι πρώτοι με τον

.)

6η)

Αν

είναι πρώτος αριθμός, διάφος του

, να αποδείξετε ότι:

$\displaystyle{1^{p-1}+2^{p-1}+3^{p-1}+ . . . +(p-1)^{p-1}\equiv (-1)(mod p)}$

ΣΗΜ: Διόρθωσα ένα τυπογραφικό λάθος στην εκφώνηση.

#15

ΔΗΜΗΤΡΗΣ έγραψε:
6η)

Αν είναι πρώτος αριθμός, διάφος του , να αποδείξετε ότι:

$\displaystyle{1^{p-1}+2^{p-2}+3^{p-3}+ . . . +(p-1)^{p-1}\equiv (-1)(mod p)}$

Δημήτρη,

πρώτα από όλα υποθέτω ότι έχεις τυπογραφικό σφάλμα: Γράφε $(p-1)^{1}$ αντί $(p-1)^{p-1}$ .

Αλλά έτσι και αλλιώς δεν μου βγαίνει. Π.χ. για p=3

είναι $1^2 + 2^1 = 3 \ne -1 \mod 3$ . Όμοια, για p=5

είναι
$1^4+2^3+3^2+4^1= 22\ne -1 \mod 5$ .

Σωστά;

Φιλικά,

Μιχάλης

#16

Mihalis_Lambrou έγραψε:
ΔΗΜΗΤΡΗΣ έγραψε:
6η)

Αν είναι πρώτος αριθμός, διάφος του , να αποδείξετε ότι:

$\displaystyle{1^{p-1}+2^{p-2}+3^{p-3}+ . . . +(p-1)^{p-1}\equiv (-1)(mod p)}$
Δημήτρη,

πρώτα από όλα υποθέτω ότι έχεις τυπογραφικό σφάλμα: Γράφε $(p-1)^{1}$ αντί $(p-1)^{p-1}$ .

Αλλά έτσι και αλλιώς δεν μου βγαίνει. Π.χ. για είναι $1^2 + 2^1 = 3 \ne -1 \mod 3$ . Όμοια, για είναι
$1^4+2^3+3^2+4^1= 22\ne -1 \mod 5$ .

Σωστά;

Φιλικά,

Μιχάλης

Σε βιβλίο έχω δει την άσκηση χωρίς να αλλάζουν οι εκθέτες:

$\displaystyle{1^{p-1}+2^{p-1}+3^{p-1}+ \cdots +(p-2)^{p-1}+(p-1)^{p-1}\equiv -1\pmod{p}}$

Φιλικά,

Αχιλλέας

#17

achilleas έγραψε:
Σε βιβλίο έχω δει την άσκηση χωρίς να αλλάζουν οι εκθέτες:

$\displaystyle{1^{p-1}+2^{p-1}+3^{p-1}+ \cdots +(p-2)^{p-1}+(p-1)^{p-1}\equiv -1\pmod{p}}$

Αν είναι έτσι (*), τότε λέμε: Από το θεώρημα Fermat είναι $a^ {p-1} \equiv 1 \mod (p), \, 1\le a \le p-1$ . Με πρόσθεση κατά μέλη των p-1

αυτών σχέσεων, εύκολα καταλήγουμε στο ζητούμενο.

Φιλικά,

Μιχάλης

(*) που σίγουρα ο Αχιλλέας ξέρει την λύση αλλά μας την χάρισε.

#18

Δική μου απροσεξία, κατά την πληκτρολόγιση!! Πράγματι το σωστό είναι με όλους τους εκθέτες ίσους με $\displaystyle{p-1}$ .

Μιχάλη και Αχιλλέα και όσοι άλλοι ασχοληθήκατε, ζητώ συγνώμη.

#19

7η
Να βρείτε τους φυσικούς αριθμούς n>0

για τους οποίους ισχύει n+2/n^2+2

.

#20

xr.tsif έγραψε:7η
Να βρείτε τους φυσικούς αριθμούς για τους οποίους ισχύει .

Είναι

, οπότε $n+2\mid n^2+2$ αν και μόνο αν $n+2\mid 6$ ,

δηλαδή αν και μόνο αν $n+2\in \{1,2,3,6\}$ .

Αφού n>0

, παίρνουμε n=1

ή

.

Φιλικά,

Αχιλλέας

mathematica.gr

Βασική θεωρία αριθμών!

Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

Re: Βασική θεωρία αριθμών!

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