mathematica.gr

Καλησπέρα σας, ελπίζω να ποστάρω στο σωστό κομμάτι του φόρουμ αυτού.
Είμαι πρωτοετής φοιτητής στο τμήμα πληροφορικής και τηλεπικοινονιών στο Καποδιστριακό και ενας καθηγητής μας μας είπε να ψάξουμε να καταλάβουμε τι είναι οι αριθμοί Carmichael καθώς θα μας χρηαστούν στην πρώτη εργασία μας.
Ψάχνω στο ίντερνετ αλλα τα περισσότερα άρθρα είναι στα αγγλικά και όσα είναι στα ελληνικά και πάλι δεν τα καταλαβαίνω καθώς δεν ξέρω όλους τους όρους που χρηάζονται.
Θα μπορούσε κάποιος να μου πει τι είναι αυτοί οι αριθμοί στην γλώσσα της 3ης λυκείου? ή τουλάχιστον με πιο απλά λόγια απο αυτα που χρησιμοποιούνται στα επιστημονικά άρθρα.
Ευχαριστά πολύ εκ των προτέρων.

Αν έχω καταλάβει καλά, απο τον τύπο 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 είναι οι σύνθετοι θετικοί ακέραιοι τέτοιοι ώστε ο

να είναι πολλαπλάσιο του για κάθε θετικό ακέραιο .

Ο πρώτος αριθμός Carmichael είναι ο .

http://www.numericana.com/answer/modular.htm#carmichael

Έπεται από το μικρό θεώρημα του Fermat ότι αν ο είναι πρώτος, τότε ο να είναι πολλαπλάσιο του για κάθε θετικό ακέραιο .

Η ύπαρξη των αριθμών Carmichael καταδεικνύει ότι το αντίστροφο δεν ισχύει.

Οι αριθμοί Carmichael "ξεγελούν" κάποια πιθανοθεωρητικά test για το αν ένας αριθμός είναι πρώτος, και είναι άπειροι στο πλήθος.

Φιλικά,

Αχιλλέας

achilleas έγραψε:Οι αριθμοί Carmichael είναι οι σύνθετοι θετικοί ακέραιοι τέτοιοι ώστε ο

να είναι πολλαπλάσιο του για κάθε θετικό ακέραιο .

Ο πρώτος αριθμός Carmichael είναι ο .

http://www.numericana.com/answer/modular.htm#carmichael

Έπεται από το μικρό θεώρημα του Fermat ότι αν ο είναι πρώτος, τότε ο να είναι πολλαπλάσιο του για κάθε θετικό ακέραιο .

Η ύπαρξη των αριθμών Carmichael καταδεικνύει ότι το αντίστροφο δεν ισχύει.

Οι αριθμοί Carmichael "ξεγελούν" κάποια πιθανοθεωρητικά test για το αν ένας αριθμός είναι πρώτος, και είναι άπειροι στο πλήθος.

Φιλικά,

Αχιλλέας

Ευχαριστώ πολύ για την απάντηση, θα μπορούσες να μου παραθέσεις την απόδειξη ή την μέθοδο εύρεσης των αριθμών αυτών?
πως ξέρουμε οτι για n = 561 θα ισχύει η πρόταση για κάθε a στους φυσικούς?
Απο αυτο που λές για το μικρό θεώρημα του Fermat εγώ συμπεραίνω οτι κάθε πρώτος είναι Carmichael, που κάνω λάθος?

Ιάσονας.

Απιστευτο!
Γεια σου Ιασονα. Ειμαι συμφοιτητρια σου (πρωτοετης κι εγω) και βρηκα αυτο το τοπικ επειδη ακριβως εψαχνα τι ειναι οι αριθμοι carmichael και δεν καταλαβαινα πολλα απο την αγγλικη wikipedia.

Κι εγω για την εργασια του Σταματοπουλου το εψαχνα το θεμα, αν και ειναι νωρις ακομα.
Χαιρομαι που βρηκα πρωτοετη συμφοιτητη στο mathematica!

J.Pap έγραψε:
Ευχαριστώ πολύ για την απάντηση, θα μπορούσες να μου παραθέσεις την απόδειξη ή την μέθοδο εύρεσης των αριθμών αυτών?

Υπάρχουν αλγόριθμοι εύρεσης αριθμών Carmicael. Αλλά δεν νομίζω να υπάρχει κάποιος τύπος γενικός. Η απόδειξη ότι υπάρχουν άπειροι αιρθμοί Carmichael δόθηκε το 1994.

J.Pap έγραψε: πως ξέρουμε οτι για n = 561 θα ισχύει η πρόταση για κάθε a στους φυσικούς?

Αφού αρκεί να τσεκάρεις ότι o διαιρείται με το 3, το 11 και το 17.

Αυτό έπεται από το μικρο θεώρημα του Fermat: δες, π.χ.,

https://nrich.maths.org/discus/messages ... 1198254846

J.Pap έγραψε: Απο αυτο που λές για το μικρό θεώρημα του Fermat εγώ συμπεραίνω οτι κάθε πρώτος είναι Carmichael, που κάνω λάθος?
Ιάσονας.

Δες τον παραπάνω ορισμό που έδωσα...τόνισα τη λέξη "σύνθετος".

Φιλικά,

Αχιλλέας

Rania έγραψε:Απιστευτο!
Γεια σου Ιασονα. Ειμαι συμφοιτητρια σου (πρωτοετης κι εγω) και βρηκα αυτο το τοπικ επειδη ακριβως εψαχνα τι ειναι οι αριθμοι carmichael και δεν καταλαβαινα πολλα απο την αγγλικη wikipedia.

Κι εγω για την εργασια του Σταματοπουλου το εψαχνα το θεμα, αν και ειναι νωρις ακομα.
Χαιρομαι που βρηκα πρωτοετη συμφοιτητη στο mathematica!

Καλησπέρα Ράνια προσπαθώ να καταλάβω τι είναι αυτοι οι αριθμοί και πως τους βρίσκει κανείς αλλα είναι δύσκολο!
Εχω βρεί πολλές πηγές αλλα και στα ελληνικά δυσκολεύομαι να καταλάβω.Έκανα μια προσπάθια να φτιάξω πρόγραμμα που να βρίσκει αν ενας αριθμός είναι carmichael ή οχι αλλα απέτυχα. Οτι ερώτηση έχεις σχετικη καν' την εδω γιατι πιστεύω ειναι απο τα καλύτερα foroum που θα μπορούσαμε να απευθυνθούμε.

achilleas έγραψε:

J.Pap έγραψε:
Ευχαριστώ πολύ για την απάντηση, θα μπορούσες να μου παραθέσεις την απόδειξη ή την μέθοδο εύρεσης των αριθμών αυτών?

Υπάρχουν αλγόριθμοι εύρεσης αριθμών Carmicael. Αλλά δεν νομίζω να υπάρχει κάποιος τύπος γενικός. Η απόδειξη ότι υπάρχουν άπειροι αιρθμοί Carmichael δόθηκε το 1994.

J.Pap έγραψε: πως ξέρουμε οτι για n = 561 θα ισχύει η πρόταση για κάθε a στους φυσικούς?

Αφού αρκεί να τσεκάρεις ότι o διαιρείται με το 3, το 11 και το 17.

Αυτό έπεται από το μικρο θεώρημα του Fermat: δες, π.χ.,

https://nrich.maths.org/discus/messages ... 1198254846

J.Pap έγραψε: Απο αυτο που λές για το μικρό θεώρημα του Fermat εγώ συμπεραίνω οτι κάθε πρώτος είναι 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 (εως ένα άνω φράγμα), αφού πως μπορείς να τσεκάρεις τη συνθήκη διαιρετότητας για κάθε ακέραιο ?

Φιλικά,

Αχιλλέας

Γράφω επίσης μερικές ιδιότητες που έχουν οι συγκεκριμένοι αριθμοί

(1) Είναι περιττοί

(2) Είναι ελεύθεροι τετραγώνου (δηλαδή δεν διαιρούνται από τετράγωνο πρώτου)

(3) Αν ένας πρώτος διαιρεί ένα αριθμό Carmichael τότε ο αριθμός θα διαιρεί τον .

(4) Έχουν τουλάχιστον 3 πρώτους παράγοντες.


Από τα παραπάνω αποδεικνύεται ότι αν ακέραιος ώστε οι αριθμοί να είναι πρώτοι τότε ο ακέραιος είναι αριθμός Carmichael. (Για παράδειγμα για , παίρνουμε τον 1729.)

Φιλικά,

Νίκος Κατσίπης

nkatsipis έγραψε:Γράφω επίσης μερικές ιδιότητες που έχουν οι συγκεκριμένοι αριθμοί

(1) Είναι περιττοί

(2) Είναι ελεύθεροι τετραγώνου (δηλαδή δεν διαιρούνται από τετράγωνο πρώτου)

(3) Αν ένας πρώτος διαιρεί ένα αριθμό Carmichael τότε ο αριθμός θα διαιρεί τον .

(4) Έχουν τουλάχιστον 3 πρώτους παράγοντες.


Από τα παραπάνω αποδεικνύεται ότι αν ακέραιος ώστε οι αριθμοί να είναι πρώτοι τότε ο ακέραιος είναι αριθμός Carmichael. (Για παράδειγμα για , παίρνουμε τον 1729.)

Φιλικά,

Νίκος Κατσίπης

Ευχαριστώ πολυ και εσένα Νίκο

Ιάσονα και Ράνια παλεύω και εγώ για την άσκηση του Τάκη και ψάχνω (αν και δευτεροετής...)..Παιδιά ο Τάκης είπε ότι θα χει σχέση με αυτούς τους αριθμούς όχι ότι θα ναι στάνταρ ένα πρόγραμμα που τους εντοπίζει και τους εμφανίζει..Εν πάση περιπτώσει εγώ αυτό που δεν κατάλαβα είναι γιατί επιλέγουμε πχ στο 561 συγκεκριμένα τα 3,11,17..Είναι η ανάλυση του 561 σε πρώτους παράγοντες??Και τι γίνεται αν στην ανάλυση σε πρώτους παράγοντες ο αριθμός αναλύεται σε παράγοντες με δύναμη μεγαλύτερη του ένα?Δηλαδή αν είναι πχ 3*3*11*11*17*23*29*29 (δεν ξέρω καν ποιος είναι ο αριθμός τυχαία το βαλα)

tony_iommi έγραψε:Ιάσονα και Ράνια παλεύω και εγώ για την άσκηση του Τάκη και ψάχνω (αν και δευτεροετής...)..Παιδιά ο Τάκης είπε ότι θα χει σχέση με αυτούς τους αριθμούς όχι ότι θα ναι στάνταρ ένα πρόγραμμα που τους εντοπίζει και τους εμφανίζει..Εν πάση περιπτώσει εγώ αυτό που δεν κατάλαβα είναι γιατί επιλέγουμε πχ στο 561 συγκεκριμένα τα 3,11,17..Είναι η ανάλυση του 561 σε πρώτους παράγοντες??Και τι γίνεται αν στην ανάλυση σε πρώτους παράγοντες ο αριθμός αναλύεται σε παράγοντες με δύναμη μεγαλύτερη του ένα?Δηλαδή αν είναι πχ 3*3*11*11*17*23*29*29 (δεν ξέρω καν ποιος είναι ο αριθμός τυχαία το βαλα)

Καταρχάς καλώς όρισες στο !!

ναι το είναι ανάλυση του σε πρώτους παράγοντες...

για το ερώτημα που θετεις πρόσεξε παραπάνω τι γράφει ο κύριος Κατσίπης..ένας αριθμός Caramichael είναι ελεύθερος τετραώνου άρα δεν έχει στην αναλυση του σε πρώτους παράγοντες καποιον πρώτο υψωμένο σε μεγαλύτερη δύναμη απο 1...

κι εγώ να γίνει πρόγραμμα υπολογισμού καποιων απ αυτούς τους αριθμούς δύσκολο το βλέπω...

Αν έχω καταλάβει καλά οι αριθμοί Carmichael είναι οσα γινόμενα πρώτων αριθμών

x = prime_number1*prime_number2*.....*prime_number(n) , με όλους τους πρώτους αριθμούς διαφορετικούς μεταξύ τους.
(χωρίς να εννοώ όπου prime_number1 τον πρώτο πρώτο αριθμο κ.τ.λ.)

ικανοποίουν την σχέση :

όπου Ν και Ν

ή

mod χ = 0

ας με διορθώσει κάποιος αν κάνω λάθος ή ξεχνάω κάποιο περιορισμό.

Ναι και εγώ αυτό έχω καταλάβει όμως είναι αδύνατον να ελέγξεις με όλους τους φυσικούς...Δηλαδή δεν υπάρχει περιορισμός για το α?Κανένας?Επί του πρακτέου αυτό καταντά αδύνατη την απόδειξη ότι ένας αριθμός είναι Carmichael..Δεν μιλάω αποκλειστικά για προγραμματιστικό προσδιορισμό αλλά και μαθηματικά αν έχω υποψία ότι κάποιος είναι Carmichael δεν μπορώ να το αποδείξω αφού ο έλεγχος για τα α δε θα σταματήσει ποτέ..

achilleas έγραψε:Υπάρχουν αλγόριθμοι εύρεσης αριθμών Carmicael. Αλλά δεν νομίζω να υπάρχει κάποιος τύπος γενικός. Η απόδειξη ότι υπάρχουν άπειροι αιρθμοί Carmichael δόθηκε το 1994.

Είχα την τύχη να παρακολουθήσω διάλεξη ενός εκ των πρωτεργατών αυτής της απόδειξης, του Andrew Granville, το 1992 (πριν γίνει η δημοσίευση δηλαδή). [Αλλά και την ακόμη μεγαλύτερη τύχη να δειπνήσω στο ίδιο τραπέζι με τον ομιλητή και να μιλήσω αρκετά μαζί του -- όχι επειδή ήμουν τόσο σπουδαίος, απλώς έτσι έτυχε.] Καταπληκτική ομιλία από έναν καταπληκτικό μαθηματικό!

Εμπνευσμένος ίσως από την παραπάνω εμπειρία έδωσα -- πέντε χρόνια αργότερα, όταν δίδαξα Θεωρία Αριθμών -- την ονομασία "anti-Carmichael pair" σε κάθε ζεύγος αριθμών a, b που ικανοποιεί τις σχέσεις a|b(b-1) και b|a(a-1): πλήρης χαρακτηρισμός αυτών των ζευγών δόθηκε, μέσω sci.math, από τον 'ερασιτέχνη' μαθηματικό Kevin Brown, δείτε εδώ. (Αξίζει τον κόπο να επισκεφθείτε τις "Μαθηματικές Σελίδες" του (http://www.mathpages.com), όπως και την αριθμοθεωρητική συλλογή που μόλις εντόπισα!)

Γιώργος Μπαλόγλου