Αριθμοι Carmichael.

Συντονιστής: nkatsipis

Άβαταρ μέλους
J.Pap
Δημοσιεύσεις: 8
Εγγραφή: Σάβ Οκτ 09, 2010 11:30 am
Επικοινωνία:

Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #1 από J.Pap » Σάβ Οκτ 09, 2010 11:43 am

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


Άβαταρ μέλους
J.Pap
Δημοσιεύσεις: 8
Εγγραφή: Σάβ Οκτ 09, 2010 11:30 am
Επικοινωνία:

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #2 από J.Pap » Κυρ Οκτ 10, 2010 8:04 pm

Αν έχω καταλάβει καλά, απο τον τύπο 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 να είναι σχετικά πρώτοι μεταξύ τους (εύκολο αυτο το κομμάτι).

Τα λέω λίγο μπερδεμένα γιατί ακόμα δεν έχω καταλάβει καλά τι γίνετε!

Θα εκτιμούσα κάθε παραπάνω διευκρύνιση, ευχαριστω.


achilleas
Επιμελητής
Δημοσιεύσεις: 2471
Εγγραφή: Τρί Σεπ 15, 2009 3:32 pm

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #3 από achilleas » Κυρ Οκτ 10, 2010 10:15 pm

Οι αριθμοί Carmichael είναι οι σύνθετοι θετικοί ακέραιοι n τέτοιοι ώστε ο

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

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

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

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

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

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

Φιλικά,

Αχιλλέας


Άβαταρ μέλους
J.Pap
Δημοσιεύσεις: 8
Εγγραφή: Σάβ Οκτ 09, 2010 11:30 am
Επικοινωνία:

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #4 από J.Pap » Κυρ Οκτ 10, 2010 11:09 pm

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

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

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

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

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

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

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

Φιλικά,

Αχιλλέας


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

Ιάσονας.


Rania
Δημοσιεύσεις: 46
Εγγραφή: Τετ Απρ 07, 2010 7:12 pm

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #5 από Rania » Κυρ Οκτ 10, 2010 11:28 pm

Απιστευτο!
Γεια σου Ιασονα. Ειμαι συμφοιτητρια σου (πρωτοετης κι εγω) και βρηκα αυτο το τοπικ επειδη ακριβως εψαχνα τι ειναι οι αριθμοι carmichael και δεν καταλαβαινα πολλα απο την αγγλικη wikipedia.
:coolspeak:
Κι εγω για την εργασια του Σταματοπουλου το εψαχνα το θεμα, αν και ειναι νωρις ακομα. ;)
Χαιρομαι που βρηκα πρωτοετη συμφοιτητη στο mathematica! :clap:


achilleas
Επιμελητής
Δημοσιεύσεις: 2471
Εγγραφή: Τρί Σεπ 15, 2009 3:32 pm

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #6 από achilleas » Δευ Οκτ 11, 2010 12:04 am

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



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

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


Αφού 561=3\cdot 11\cdot 17 αρκεί να τσεκάρεις ότι o a^{561}-a διαιρείται με το 3, το 11 και το 17.

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

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

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


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

Φιλικά,

Αχιλλέας


Άβαταρ μέλους
J.Pap
Δημοσιεύσεις: 8
Εγγραφή: Σάβ Οκτ 09, 2010 11:30 am
Επικοινωνία:

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #7 από J.Pap » Δευ Οκτ 11, 2010 12:07 am

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



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


Άβαταρ μέλους
J.Pap
Δημοσιεύσεις: 8
Εγγραφή: Σάβ Οκτ 09, 2010 11:30 am
Επικοινωνία:

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #8 από J.Pap » Δευ Οκτ 11, 2010 12:10 am

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



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

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


Αφού 561=3\cdot 11\cdot 17 αρκεί να τσεκάρεις ότι o a^{561}-a διαιρείται με το 3, το 11 και το 17.

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

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

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


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

Φιλικά,

Αχιλλέας



Αχιλλέα σε ευχαριστώ πολύ, είναι αργα τωρα για να δουλέψει καθαρα το μυαλό μου τώρα, θα τα δω ολα αυτά αύριο ;)


achilleas
Επιμελητής
Δημοσιεύσεις: 2471
Εγγραφή: Τρί Σεπ 15, 2009 3:32 pm

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #9 από achilleas » Δευ Οκτ 11, 2010 12:19 am

Έχε υπόψη σου επίσης ότι οι αριθμοί 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 (εως ένα άνω φράγμα), αφού πως μπορείς να τσεκάρεις τη συνθήκη διαιρετότητας για κάθε ακέραιο a?

Φιλικά,

Αχιλλέας


Άβαταρ μέλους
nkatsipis
Επιμελητής
Δημοσιεύσεις: 745
Εγγραφή: Κυρ Δεκ 21, 2008 10:26 am
Τοποθεσία: Σαντορίνη
Επικοινωνία:

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #10 από nkatsipis » Δευ Οκτ 11, 2010 11:33 am

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

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

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

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

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


Από τα παραπάνω αποδεικνύεται ότι αν x ακέραιος ώστε οι αριθμοί 6x+1, 12x+1, 18x+1 να είναι πρώτοι τότε ο ακέραιος n=(6x+1)(12x+1)(18x+1) είναι αριθμός Carmichael. (Για παράδειγμα για x=1, παίρνουμε τον 1729.)

Φιλικά,

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


Άβαταρ μέλους
J.Pap
Δημοσιεύσεις: 8
Εγγραφή: Σάβ Οκτ 09, 2010 11:30 am
Επικοινωνία:

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #11 από J.Pap » Δευ Οκτ 11, 2010 4:52 pm

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

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

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

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

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


Από τα παραπάνω αποδεικνύεται ότι αν x ακέραιος ώστε οι αριθμοί 6x+1, 12x+1, 18x+1 να είναι πρώτοι τότε ο ακέραιος n=(6x+1)(12x+1)(18x+1) είναι αριθμός Carmichael. (Για παράδειγμα για x=1, παίρνουμε τον 1729.)

Φιλικά,

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


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


tony_iommi
Δημοσιεύσεις: 2
Εγγραφή: Τρί Οκτ 12, 2010 6:27 pm

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #12 από tony_iommi » Τρί Οκτ 12, 2010 6:37 pm

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


manos1992
Δημοσιεύσεις: 293
Εγγραφή: Πέμ Μάιος 07, 2009 6:53 pm
Τοποθεσία: Αθήνα, Ν.Σμύρνη

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #13 από manos1992 » Τρί Οκτ 12, 2010 6:57 pm

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


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

ναι το 3\cdot 11 \cdot 17 είναι ανάλυση του 561 σε πρώτους παράγοντες...

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

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


Μάνος Μανουράς
Άβαταρ μέλους
J.Pap
Δημοσιεύσεις: 8
Εγγραφή: Σάβ Οκτ 09, 2010 11:30 am
Επικοινωνία:

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #14 από J.Pap » Τρί Οκτ 12, 2010 9:53 pm

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

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

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

\alpha ^{\chi }-\alpha = \kappa *\chi όπου \alpha \in Ν και \kappa \in Ν

ή

(\alpha ^{\chi }-\alpha) mod χ = 0

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


tony_iommi
Δημοσιεύσεις: 2
Εγγραφή: Τρί Οκτ 12, 2010 6:27 pm

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #15 από tony_iommi » Παρ Οκτ 22, 2010 3:52 pm

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


Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2326
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Αριθμοι Carmichael.

Μη αναγνωσμένη δημοσίευση #16 από gbaloglou » Παρ Οκτ 22, 2010 6:40 pm

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), όπως και την αριθμοθεωρητική συλλογή που μόλις εντόπισα!)

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


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.

Επιστροφή σε “ΘΕΩΡΙΑ ΑΡΙΘΜΩΝ”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης