Αριθμοι Carmichael.
Συντονιστής: nkatsipis
Αριθμοι Carmichael.
Καλησπέρα σας, ελπίζω να ποστάρω στο σωστό κομμάτι του φόρουμ αυτού.
Είμαι πρωτοετής φοιτητής στο τμήμα πληροφορικής και τηλεπικοινονιών στο Καποδιστριακό και ενας καθηγητής μας μας είπε να ψάξουμε να καταλάβουμε τι είναι οι αριθμοί Carmichael καθώς θα μας χρηαστούν στην πρώτη εργασία μας.
Ψάχνω στο ίντερνετ αλλα τα περισσότερα άρθρα είναι στα αγγλικά και όσα είναι στα ελληνικά και πάλι δεν τα καταλαβαίνω καθώς δεν ξέρω όλους τους όρους που χρηάζονται.
Θα μπορούσε κάποιος να μου πει τι είναι αυτοί οι αριθμοί στην γλώσσα της 3ης λυκείου? ή τουλάχιστον με πιο απλά λόγια απο αυτα που χρησιμοποιούνται στα επιστημονικά άρθρα.
Ευχαριστά πολύ εκ των προτέρων.
Είμαι πρωτοετής φοιτητής στο τμήμα πληροφορικής και τηλεπικοινονιών στο Καποδιστριακό και ενας καθηγητής μας μας είπε να ψάξουμε να καταλάβουμε τι είναι οι αριθμοί Carmichael καθώς θα μας χρηαστούν στην πρώτη εργασία μας.
Ψάχνω στο ίντερνετ αλλα τα περισσότερα άρθρα είναι στα αγγλικά και όσα είναι στα ελληνικά και πάλι δεν τα καταλαβαίνω καθώς δεν ξέρω όλους τους όρους που χρηάζονται.
Θα μπορούσε κάποιος να μου πει τι είναι αυτοί οι αριθμοί στην γλώσσα της 3ης λυκείου? ή τουλάχιστον με πιο απλά λόγια απο αυτα που χρησιμοποιούνται στα επιστημονικά άρθρα.
Ευχαριστά πολύ εκ των προτέρων.
Re: Αριθμοι Carmichael.
Αν έχω καταλάβει καλά, απο τον τύπο b^(n-1)=1(mod n) όπου = ειναι το σύμβολο με τρείς γραμμές.
Πώς μπορω να βρώ τους αριθμούς Carmichael ξεκινόντας απο τον μικρότερο ανεβαίνοντας?
το b ανήκει στους ακεραιους , υπάρχει άλλος περιορισμός για το b?
Πιστεύω οτι b^(n-1)>(-2n) και b^(n-1)<(2n) μιας και αν b^(n-1) γίνει ίσο με ένα απο αυτά τα "άκρα" το b^(n-1) mod n θα είναι διάφορο του 1.
Πρεπει επίσης οι b και n να είναι σχετικά πρώτοι μεταξύ τους (εύκολο αυτο το κομμάτι).
Τα λέω λίγο μπερδεμένα γιατί ακόμα δεν έχω καταλάβει καλά τι γίνετε!
Θα εκτιμούσα κάθε παραπάνω διευκρύνιση, ευχαριστω.
Πώς μπορω να βρώ τους αριθμούς Carmichael ξεκινόντας απο τον μικρότερο ανεβαίνοντας?
το b ανήκει στους ακεραιους , υπάρχει άλλος περιορισμός για το b?
Πιστεύω οτι b^(n-1)>(-2n) και b^(n-1)<(2n) μιας και αν b^(n-1) γίνει ίσο με ένα απο αυτά τα "άκρα" το b^(n-1) mod n θα είναι διάφορο του 1.
Πρεπει επίσης οι b και n να είναι σχετικά πρώτοι μεταξύ τους (εύκολο αυτο το κομμάτι).
Τα λέω λίγο μπερδεμένα γιατί ακόμα δεν έχω καταλάβει καλά τι γίνετε!
Θα εκτιμούσα κάθε παραπάνω διευκρύνιση, ευχαριστω.
Re: Αριθμοι Carmichael.
Οι αριθμοί Carmichael είναι οι σύνθετοι θετικοί ακέραιοι τέτοιοι ώστε ο
να είναι πολλαπλάσιο του για κάθε θετικό ακέραιο .
Ο πρώτος αριθμός Carmichael είναι ο .
http://www.numericana.com/answer/modular.htm#carmichael
Έπεται από το μικρό θεώρημα του Fermat ότι αν ο είναι πρώτος, τότε ο να είναι πολλαπλάσιο του για κάθε θετικό ακέραιο .
Η ύπαρξη των αριθμών Carmichael καταδεικνύει ότι το αντίστροφο δεν ισχύει.
Οι αριθμοί Carmichael "ξεγελούν" κάποια πιθανοθεωρητικά test για το αν ένας αριθμός είναι πρώτος, και είναι άπειροι στο πλήθος.
Φιλικά,
Αχιλλέας
να είναι πολλαπλάσιο του για κάθε θετικό ακέραιο .
Ο πρώτος αριθμός Carmichael είναι ο .
http://www.numericana.com/answer/modular.htm#carmichael
Έπεται από το μικρό θεώρημα του Fermat ότι αν ο είναι πρώτος, τότε ο να είναι πολλαπλάσιο του για κάθε θετικό ακέραιο .
Η ύπαρξη των αριθμών Carmichael καταδεικνύει ότι το αντίστροφο δεν ισχύει.
Οι αριθμοί Carmichael "ξεγελούν" κάποια πιθανοθεωρητικά test για το αν ένας αριθμός είναι πρώτος, και είναι άπειροι στο πλήθος.
Φιλικά,
Αχιλλέας
Re: Αριθμοι Carmichael.
Ευχαριστώ πολύ για την απάντηση, θα μπορούσες να μου παραθέσεις την απόδειξη ή την μέθοδο εύρεσης των αριθμών αυτών?achilleas έγραψε:Οι αριθμοί Carmichael είναι οι σύνθετοι θετικοί ακέραιοι τέτοιοι ώστε ο
να είναι πολλαπλάσιο του για κάθε θετικό ακέραιο .
Ο πρώτος αριθμός Carmichael είναι ο .
http://www.numericana.com/answer/modular.htm#carmichael
Έπεται από το μικρό θεώρημα του Fermat ότι αν ο είναι πρώτος, τότε ο να είναι πολλαπλάσιο του για κάθε θετικό ακέραιο .
Η ύπαρξη των αριθμών Carmichael καταδεικνύει ότι το αντίστροφο δεν ισχύει.
Οι αριθμοί Carmichael "ξεγελούν" κάποια πιθανοθεωρητικά test για το αν ένας αριθμός είναι πρώτος, και είναι άπειροι στο πλήθος.
Φιλικά,
Αχιλλέας
πως ξέρουμε οτι για n = 561 θα ισχύει η πρόταση για κάθε a στους φυσικούς?
Απο αυτο που λές για το μικρό θεώρημα του Fermat εγώ συμπεραίνω οτι κάθε πρώτος είναι Carmichael, που κάνω λάθος?
Ιάσονας.
Re: Αριθμοι Carmichael.
Απιστευτο!
Γεια σου Ιασονα. Ειμαι συμφοιτητρια σου (πρωτοετης κι εγω) και βρηκα αυτο το τοπικ επειδη ακριβως εψαχνα τι ειναι οι αριθμοι carmichael και δεν καταλαβαινα πολλα απο την αγγλικη wikipedia.
Κι εγω για την εργασια του Σταματοπουλου το εψαχνα το θεμα, αν και ειναι νωρις ακομα.
Χαιρομαι που βρηκα πρωτοετη συμφοιτητη στο mathematica!
Γεια σου Ιασονα. Ειμαι συμφοιτητρια σου (πρωτοετης κι εγω) και βρηκα αυτο το τοπικ επειδη ακριβως εψαχνα τι ειναι οι αριθμοι carmichael και δεν καταλαβαινα πολλα απο την αγγλικη wikipedia.
Κι εγω για την εργασια του Σταματοπουλου το εψαχνα το θεμα, αν και ειναι νωρις ακομα.
Χαιρομαι που βρηκα πρωτοετη συμφοιτητη στο mathematica!
Re: Αριθμοι Carmichael.
J.Pap έγραψε:
Ευχαριστώ πολύ για την απάντηση, θα μπορούσες να μου παραθέσεις την απόδειξη ή την μέθοδο εύρεσης των αριθμών αυτών?
Υπάρχουν αλγόριθμοι εύρεσης αριθμών Carmicael. Αλλά δεν νομίζω να υπάρχει κάποιος τύπος γενικός. Η απόδειξη ότι υπάρχουν άπειροι αιρθμοί Carmichael δόθηκε το 1994.
Αφού αρκεί να τσεκάρεις ότι o διαιρείται με το 3, το 11 και το 17.J.Pap έγραψε: πως ξέρουμε οτι για n = 561 θα ισχύει η πρόταση για κάθε a στους φυσικούς?
Αυτό έπεται από το μικρο θεώρημα του Fermat: δες, π.χ.,
https://nrich.maths.org/discus/messages ... 1198254846
Δες τον παραπάνω ορισμό που έδωσα...τόνισα τη λέξη "σύνθετος".J.Pap έγραψε: Απο αυτο που λές για το μικρό θεώρημα του Fermat εγώ συμπεραίνω οτι κάθε πρώτος είναι Carmichael, που κάνω λάθος?
Ιάσονας.
Φιλικά,
Αχιλλέας
Re: Αριθμοι Carmichael.
Rania έγραψε:Απιστευτο!
Γεια σου Ιασονα. Ειμαι συμφοιτητρια σου (πρωτοετης κι εγω) και βρηκα αυτο το τοπικ επειδη ακριβως εψαχνα τι ειναι οι αριθμοι carmichael και δεν καταλαβαινα πολλα απο την αγγλικη wikipedia.
Κι εγω για την εργασια του Σταματοπουλου το εψαχνα το θεμα, αν και ειναι νωρις ακομα.
Χαιρομαι που βρηκα πρωτοετη συμφοιτητη στο mathematica!
Καλησπέρα Ράνια προσπαθώ να καταλάβω τι είναι αυτοι οι αριθμοί και πως τους βρίσκει κανείς αλλα είναι δύσκολο!
Εχω βρεί πολλές πηγές αλλα και στα ελληνικά δυσκολεύομαι να καταλάβω.Έκανα μια προσπάθια να φτιάξω πρόγραμμα που να βρίσκει αν ενας αριθμός είναι carmichael ή οχι αλλα απέτυχα. Οτι ερώτηση έχεις σχετικη καν' την εδω γιατι πιστεύω ειναι απο τα καλύτερα foroum που θα μπορούσαμε να απευθυνθούμε.
Re: Αριθμοι Carmichael.
achilleas έγραψε:J.Pap έγραψε:
Ευχαριστώ πολύ για την απάντηση, θα μπορούσες να μου παραθέσεις την απόδειξη ή την μέθοδο εύρεσης των αριθμών αυτών?
Υπάρχουν αλγόριθμοι εύρεσης αριθμών Carmicael. Αλλά δεν νομίζω να υπάρχει κάποιος τύπος γενικός. Η απόδειξη ότι υπάρχουν άπειροι αιρθμοί Carmichael δόθηκε το 1994.
Αφού αρκεί να τσεκάρεις ότι o διαιρείται με το 3, το 11 και το 17.J.Pap έγραψε: πως ξέρουμε οτι για n = 561 θα ισχύει η πρόταση για κάθε a στους φυσικούς?
Αυτό έπεται από το μικρο θεώρημα του Fermat: δες, π.χ.,
https://nrich.maths.org/discus/messages ... 1198254846
Δες τον παραπάνω ορισμό που έδωσα...τόνισα τη λέξη "σύνθετος".J.Pap έγραψε: Απο αυτο που λές για το μικρό θεώρημα του Fermat εγώ συμπεραίνω οτι κάθε πρώτος είναι Carmichael, που κάνω λάθος?
Ιάσονας.
Φιλικά,
Αχιλλέας
Αχιλλέα σε ευχαριστώ πολύ, είναι αργα τωρα για να δουλέψει καθαρα το μυαλό μου τώρα, θα τα δω ολα αυτά αύριο
Re: Αριθμοι Carmichael.
Έχε υπόψη σου επίσης ότι οι αριθμοί Carmichael αν και άπειροι, υπάρχουν μόνο 2,163 μικρότεροι από 25,000,000,000.
Αυτοί που είναι μικρότεροι από το 100000 είναι οι
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, και 75361.
Δεν ξέρω πως θα μπορούσε κάποιος να γράψει ένα πρόγραμμα να βρει όλους τους αριθμούς Carmichael (εως ένα άνω φράγμα), αφού πως μπορείς να τσεκάρεις τη συνθήκη διαιρετότητας για κάθε ακέραιο ?
Φιλικά,
Αχιλλέας
Αυτοί που είναι μικρότεροι από το 100000 είναι οι
561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, και 75361.
Δεν ξέρω πως θα μπορούσε κάποιος να γράψει ένα πρόγραμμα να βρει όλους τους αριθμούς Carmichael (εως ένα άνω φράγμα), αφού πως μπορείς να τσεκάρεις τη συνθήκη διαιρετότητας για κάθε ακέραιο ?
Φιλικά,
Αχιλλέας
- nkatsipis
- Επιμελητής
- Δημοσιεύσεις: 778
- Εγγραφή: Κυρ Δεκ 21, 2008 10:26 am
- Τοποθεσία: Σαντορίνη
- Επικοινωνία:
Re: Αριθμοι Carmichael.
Γράφω επίσης μερικές ιδιότητες που έχουν οι συγκεκριμένοι αριθμοί
(1) Είναι περιττοί
(2) Είναι ελεύθεροι τετραγώνου (δηλαδή δεν διαιρούνται από τετράγωνο πρώτου)
(3) Αν ένας πρώτος διαιρεί ένα αριθμό Carmichael τότε ο αριθμός θα διαιρεί τον .
(4) Έχουν τουλάχιστον 3 πρώτους παράγοντες.
Από τα παραπάνω αποδεικνύεται ότι αν ακέραιος ώστε οι αριθμοί να είναι πρώτοι τότε ο ακέραιος είναι αριθμός Carmichael. (Για παράδειγμα για , παίρνουμε τον 1729.)
Φιλικά,
Νίκος Κατσίπης
(1) Είναι περιττοί
(2) Είναι ελεύθεροι τετραγώνου (δηλαδή δεν διαιρούνται από τετράγωνο πρώτου)
(3) Αν ένας πρώτος διαιρεί ένα αριθμό Carmichael τότε ο αριθμός θα διαιρεί τον .
(4) Έχουν τουλάχιστον 3 πρώτους παράγοντες.
Από τα παραπάνω αποδεικνύεται ότι αν ακέραιος ώστε οι αριθμοί να είναι πρώτοι τότε ο ακέραιος είναι αριθμός Carmichael. (Για παράδειγμα για , παίρνουμε τον 1729.)
Φιλικά,
Νίκος Κατσίπης
Re: Αριθμοι Carmichael.
Ευχαριστώ πολυ και εσένα Νίκοnkatsipis έγραψε:Γράφω επίσης μερικές ιδιότητες που έχουν οι συγκεκριμένοι αριθμοί
(1) Είναι περιττοί
(2) Είναι ελεύθεροι τετραγώνου (δηλαδή δεν διαιρούνται από τετράγωνο πρώτου)
(3) Αν ένας πρώτος διαιρεί ένα αριθμό Carmichael τότε ο αριθμός θα διαιρεί τον .
(4) Έχουν τουλάχιστον 3 πρώτους παράγοντες.
Από τα παραπάνω αποδεικνύεται ότι αν ακέραιος ώστε οι αριθμοί να είναι πρώτοι τότε ο ακέραιος είναι αριθμός Carmichael. (Για παράδειγμα για , παίρνουμε τον 1729.)
Φιλικά,
Νίκος Κατσίπης
-
- Δημοσιεύσεις: 2
- Εγγραφή: Τρί Οκτ 12, 2010 6:27 pm
Re: Αριθμοι Carmichael.
Ιάσονα και Ράνια παλεύω και εγώ για την άσκηση του Τάκη και ψάχνω (αν και δευτεροετής...)..Παιδιά ο Τάκης είπε ότι θα χει σχέση με αυτούς τους αριθμούς όχι ότι θα ναι στάνταρ ένα πρόγραμμα που τους εντοπίζει και τους εμφανίζει..Εν πάση περιπτώσει εγώ αυτό που δεν κατάλαβα είναι γιατί επιλέγουμε πχ στο 561 συγκεκριμένα τα 3,11,17..Είναι η ανάλυση του 561 σε πρώτους παράγοντες??Και τι γίνεται αν στην ανάλυση σε πρώτους παράγοντες ο αριθμός αναλύεται σε παράγοντες με δύναμη μεγαλύτερη του ένα?Δηλαδή αν είναι πχ 3*3*11*11*17*23*29*29 (δεν ξέρω καν ποιος είναι ο αριθμός τυχαία το βαλα)
Re: Αριθμοι Carmichael.
Καταρχάς καλώς όρισες στο !!tony_iommi έγραψε:Ιάσονα και Ράνια παλεύω και εγώ για την άσκηση του Τάκη και ψάχνω (αν και δευτεροετής...)..Παιδιά ο Τάκης είπε ότι θα χει σχέση με αυτούς τους αριθμούς όχι ότι θα ναι στάνταρ ένα πρόγραμμα που τους εντοπίζει και τους εμφανίζει..Εν πάση περιπτώσει εγώ αυτό που δεν κατάλαβα είναι γιατί επιλέγουμε πχ στο 561 συγκεκριμένα τα 3,11,17..Είναι η ανάλυση του 561 σε πρώτους παράγοντες??Και τι γίνεται αν στην ανάλυση σε πρώτους παράγοντες ο αριθμός αναλύεται σε παράγοντες με δύναμη μεγαλύτερη του ένα?Δηλαδή αν είναι πχ 3*3*11*11*17*23*29*29 (δεν ξέρω καν ποιος είναι ο αριθμός τυχαία το βαλα)
ναι το είναι ανάλυση του σε πρώτους παράγοντες...
για το ερώτημα που θετεις πρόσεξε παραπάνω τι γράφει ο κύριος Κατσίπης..ένας αριθμός Caramichael είναι ελεύθερος τετραώνου άρα δεν έχει στην αναλυση του σε πρώτους παράγοντες καποιον πρώτο υψωμένο σε μεγαλύτερη δύναμη απο 1...
κι εγώ να γίνει πρόγραμμα υπολογισμού καποιων απ αυτούς τους αριθμούς δύσκολο το βλέπω...
Μάνος Μανουράς
Re: Αριθμοι Carmichael.
Αν έχω καταλάβει καλά οι αριθμοί Carmichael είναι οσα γινόμενα πρώτων αριθμών
x = prime_number1*prime_number2*.....*prime_number(n) , με όλους τους πρώτους αριθμούς διαφορετικούς μεταξύ τους.
(χωρίς να εννοώ όπου prime_number1 τον πρώτο πρώτο αριθμο κ.τ.λ.)
ικανοποίουν την σχέση :
όπου Ν και Ν
ή
mod χ = 0
ας με διορθώσει κάποιος αν κάνω λάθος ή ξεχνάω κάποιο περιορισμό.
x = prime_number1*prime_number2*.....*prime_number(n) , με όλους τους πρώτους αριθμούς διαφορετικούς μεταξύ τους.
(χωρίς να εννοώ όπου prime_number1 τον πρώτο πρώτο αριθμο κ.τ.λ.)
ικανοποίουν την σχέση :
όπου Ν και Ν
ή
mod χ = 0
ας με διορθώσει κάποιος αν κάνω λάθος ή ξεχνάω κάποιο περιορισμό.
-
- Δημοσιεύσεις: 2
- Εγγραφή: Τρί Οκτ 12, 2010 6:27 pm
Re: Αριθμοι Carmichael.
Ναι και εγώ αυτό έχω καταλάβει όμως είναι αδύνατον να ελέγξεις με όλους τους φυσικούς...Δηλαδή δεν υπάρχει περιορισμός για το α?Κανένας?Επί του πρακτέου αυτό καταντά αδύνατη την απόδειξη ότι ένας αριθμός είναι Carmichael..Δεν μιλάω αποκλειστικά για προγραμματιστικό προσδιορισμό αλλά και μαθηματικά αν έχω υποψία ότι κάποιος είναι Carmichael δεν μπορώ να το αποδείξω αφού ο έλεγχος για τα α δε θα σταματήσει ποτέ..
- gbaloglou
- Επιμελητής
- Δημοσιεύσεις: 3331
- Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
- Τοποθεσία: Θεσσαλονικη
- Επικοινωνία:
Re: Αριθμοι Carmichael.
Είχα την τύχη να παρακολουθήσω διάλεξη ενός εκ των πρωτεργατών αυτής της απόδειξης, του Andrew Granville, το 1992 (πριν γίνει η δημοσίευση δηλαδή). [Αλλά και την ακόμη μεγαλύτερη τύχη να δειπνήσω στο ίδιο τραπέζι με τον ομιλητή και να μιλήσω αρκετά μαζί του -- όχι επειδή ήμουν τόσο σπουδαίος, απλώς έτσι έτυχε.] Καταπληκτική ομιλία από έναν καταπληκτικό μαθηματικό!achilleas έγραψε:Υπάρχουν αλγόριθμοι εύρεσης αριθμών Carmicael. Αλλά δεν νομίζω να υπάρχει κάποιος τύπος γενικός. Η απόδειξη ότι υπάρχουν άπειροι αιρθμοί Carmichael δόθηκε το 1994.
Εμπνευσμένος ίσως από την παραπάνω εμπειρία έδωσα -- πέντε χρόνια αργότερα, όταν δίδαξα Θεωρία Αριθμών -- την ονομασία "anti-Carmichael pair" σε κάθε ζεύγος αριθμών a, b που ικανοποιεί τις σχέσεις a|b(b-1) και b|a(a-1): πλήρης χαρακτηρισμός αυτών των ζευγών δόθηκε, μέσω sci.math, από τον 'ερασιτέχνη' μαθηματικό Kevin Brown, δείτε εδώ. (Αξίζει τον κόπο να επισκεφθείτε τις "Μαθηματικές Σελίδες" του (http://www.mathpages.com), όπως και την αριθμοθεωρητική συλλογή που μόλις εντόπισα!)
Γιώργος Μπαλόγλου
Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες