Σύνθετος!

Ορέστης Λιγνός · #1

Να δείξετε ότι υπάρχουν άπειροι φυσικοί αριθμοί

, ώστε ο αριθμός A=10^n+3

να είναι σύνθετος.

#2

Ορέστης Λιγνός έγραψε:Να δείξετε ότι υπάρχουν άπειροι φυσικοί αριθμοί , ώστε ο αριθμός να είναι σύνθετος.

Την καλησπέρα μου στον Ορέστη.

Ένας τέτοιος αριθμός είναι ο 10^4+3=10003

που διαιρείται με το

. Επίσης, αφού από το μικρό Fermat είναι $10^6=1 \mod 7$ , εύκολα βλέπουμε ότι οι αριθμοί

$10^{4+6n}+3$

είναι πολλαπλάσια του

.

Άλλη τέτοια οικογένεια είναι η $10^{3+16n}+3$ που είναι πολλαπλάσια του

. Η αρχή γίνεται από τον $10^3+3=1003=17\cdot 59$ , και συνεχίζουμε ως άνω.

Φιλικά,

Μιχάλης

Ορέστης Λιγνός · #3

Mihalis_Lambrou έγραψε:
Ορέστης Λιγνός έγραψε:Να δείξετε ότι υπάρχουν άπειροι φυσικοί αριθμοί , ώστε ο αριθμός να είναι σύνθετος.
Την καλησπέρα μου στον Ορέστη.

Ένας τέτοιος αριθμός είναι ο που διαιρείται με το . Επίσης, αφού από το μικρό Fermat είναι $10^6=1 \mod 7$ , εύκολα βλέπουμε ότι οι αριθμοί

$10^{4+6n}+3$

είναι πολλαπλάσια του .

Φιλικά,

Μιχάλης

Κύριε Μιχάλη καλησπέρα.

Ίδια λύση έχω και εγώ.

#4

Λόγω του μικρού θεωρήματος του Fermat έχουμε $10^6\equiv 1 \pmod{7} \ (\star)$

Άρα τα υπόλοιπα των δυνάμεων του

όταν διαιρεθούν διά

επαναλαμβάνονται κάθε το πολύ

βήματα (για την ακρίβεια ακριβώς

βήματα λόγω του ότι ord_7(10)=6

, βλέπε παρακάτω).

Συνεπώς αν διαιρέσουμε το

με το

και ο αριθμός 10^n+3

διαιρείται με το

τότε έχουμε βρει απειρία τέτοιων δυνάμεων.

Παρατηρούμε ότι $10^{6k+4}+3 = \left(10^6\right)^k\cdot 10^4+3\equiv 4+3\equiv0\pmod{7}$ κι έτσι όλοι οι αριθμοί της μορφής $10^{6k+4} + 3$ διαιρούνται με το

άρα είναι σύνθετοι.

$(\star)$ Ο μικρότερος θετικός ακέραιος

για τον οποίο $a^k\equiv 1 \pmod{p}$ όπου

πρώτος, ονομάζεται τάξη του $a \mod{p}$ και συμβολίζεται με $ord_p{a}$ . Προφανώς λόγω του μικρού θεωρήματος του Fermat αποκλείεται ο αριθμός αυτός να ξεπεράσει τον αριθμό p-1

αφού αυτός έχει την παραπάνω ιδιότητα. Αποδεικνύεται ότι $ord_p{a}|p-1$ . Συνεπώς αν θέλουμε να βρούμε την τάξη ενός αριθμού $a \mod{p}$ αρκεί να την αναζητήσουμε ανάμεσα στους διαιρέτες του p-1

. π.χ. στο παράδειγμά μας επειδή $10^{6}\equiv 1 \pmod{7}$ άρα $ord_7{10}|6$ κι επειδή $10^1, 10^2, 10^3\not\equiv 1\pmod{7}$ άρα τελικά $ord_7{10}=6$ ). Η έννοια της τάξης γενικεύεται και στην περίπτωση που ο αριθμός

δεν είναι πρώτος και τότε κάνουμε χρήση του θεωρήματος του Euler και την αντίστοιχης συνάρτησης Euler.

Edit: Με πρόλαβε ο κ. Μιχάλης παραπάνω με την ίδια λύση. Το αφήνω για τον κόπο και την αντίστοιχη μικρή θεωρία για την τάξη ενός αριθμού $\mod{p}$ στο τέλος.

Αλέξανδρος

#5

Ορέστη, όσο έγραφες πρόσθεσα στο προηγούμενο ποστ μου και άλλη τέτοια οικογένεια. Τα μηνύματα διασταυρώθηκαν.

#6

Ας το γενικεύσουμε.

Έστω πρώτοι μεταξύ τους φυσικοί a,b

με

. Να δειχθεί ότι υπάρχουν άπειρα

για τα οποία ο a^n+b

είναι σύνθετος.

#7

Demetres έγραψε:Ας το γενικεύσουμε.

Έστω πρώτοι μεταξύ τους φυσικοί με . Να δειχθεί ότι υπάρχουν άπειρα για τα οποία ο είναι σύνθετος.

Έστω

πρώτος διαιρέτης του a+b

. Τότε ο

δεν διαιρεί τον

αφού

οπότε $a^{p-1} = 1 \mod p$ . Άρα

$a^{1+(p-1)k}+b = a\cdot 1+b = 0 \mod p$ , και τελιώσαμε.

Σχόλιο: Στην λύση που έδωσα παραπάνω, στο αρχικό πρόβλημα του Ορέστη, το πρώτο βήμα (στο πρόχειρό μου) ήταν να βρω έναν σύνθετο της μορφής $13, \, 103, \, 1003, \, 10003, \,...$ . Τέτοιοι είναι οι $10003=7\cdot 1429$ και $1003=17 \cdot 59$ . Τα υπόλοιπα βήματα κτιζόντουσαν από αυτό.
Η άσκηση του Δημήτρη ουσιαστικά λέει "ξέχνα αυτό το βήμα αφού δεν μπορείς να ξέρεις αν τα $a+b, \, a^2+b, a^3+b,\, ...$ είναι σύνθετοι. Κάνε κάτι λιγότερο." Και έχει δίκιο.
Θέλω να πω ότι, αν στην αρχική άσκηση του Ορέστη ξεκινούσαμε με τον

(αδιαφορώντας αν είναι σύνθετος ή όχι), θα βρίσκαμε τους σύνθετους της μορφής $10^{1+12k}+3$ (όλοι πολλαπλάσια του

). Αυτοί βέβαια υπερτερούν σε απλότητα από τους $10^{4+6k} +3$ και $10^{3+16k}+3$ που έγραψα αρχικά, ως πολλαπλάσια του

και του

, αντίστοιχα. Κάτι ήξερε ο Δημήτρης όταν έθεσε το ερώτημα.

#8

Demetres έγραψε:Ας το γενικεύσουμε.

Έστω πρώτοι μεταξύ τους φυσικοί με . Να δειχθεί ότι υπάρχουν άπειρα για τα οποία ο είναι σύνθετος.

Να σχολιάσω εδώ το εξής. Μπορούμε να δείξουμε ότι οι πρώτοι διαιρέτες που είναι τέτοιοι ώστε $p\mid x_n$ για κάποιο

, όπου

, είναι άπειροι. Έχω μία απόδειξη υπόψη μου αλλά δεν είναι στοιχειώδης.

Σύνθετος!

Σύνθετος!

Re: Σύνθετος!

Re: Σύνθετος!

Re: Σύνθετος!

Re: Σύνθετος!

Re: Σύνθετος!

Re: Σύνθετος!

Re: Σύνθετος!

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