Αριθμοί Carmichael — Όταν οι Σύνθετοι Μιμούνται τους Πρώτους

Οι αριθμοί Carmichael αποτελούν ένα από τα πιο εντυπωσιακά παραδείγματα εξαπάτησης στη Θεωρία Αριθμών. Είναι σύνθετοι αριθμοί — δηλαδή δεν είναι πρώτοι — που όμως συμπεριφέρονται σαν πρώτοι σε ορισμένες μαθηματικές δοκιμές. Αυτή η «μαθηματική μεταμφίεση» τούς έχει χαρίσει το παρατσούκλι ψευδοπρώτοι του Fermat.

📘 Το Θεώρημα του Fermat και η Έκπληξη

Το σημείο εκκίνησης είναι το γνωστό Μικρό Θεώρημα του Fermat:
αν $p$ είναι πρώτος αριθμός, τότε για κάθε ακέραιο $a$ που δεν διαιρείται από τον $p$, ισχύει

$$a^{p-1} \equiv 1 \ (\text{mod} \ p)$$

Με άλλα λόγια, αν πάρουμε οποιονδήποτε αριθμό $a$ και τον υψώσουμε στη δύναμη $p-1$, το υπόλοιπο της διαίρεσης με τον $p$ είναι πάντα 1 — αν και μόνο αν ο p είναι πρώτος.

Αυτός ο τύπος χρησιμοποιείται ευρέως ως τεστ πρωτότητας, δηλαδή για να ελέγξουμε αν ένας αριθμός είναι πρώτος.

Ωστόσο, οι αριθμοί Carmichael έρχονται να ανατρέψουν την εμπιστοσύνη μας σε αυτό το τεστ.

---

🔍 Η Ανατροπή του Carmichael

Το 1910, ο μαθηματικός Robert Carmichael ανακάλυψε ότι υπάρχουν σύνθετοι αριθμοί που ικανοποιούν το θεώρημα του Fermat για κάθε βάση a.
Δηλαδή, ακόμη κι αν δεν είναι πρώτοι, συμπεριφέρονται σαν να ήταν!

Οι πρώτοι τρεις αριθμοί Carmichael που βρέθηκαν είναι:
561 = 3 × 11 × 17,
1105 = 5 × 13 × 17,
1729 = 7 × 13 × 19.

Κάθε ένας από αυτούς περνάει το τεστ του Fermat για κάθε πιθανό a, παρότι είναι σύνθετος.

---

🧠 Μαθηματικές Ιδιότητες

Για να είναι ένας αριθμός $n$ Carmichael, πρέπει να ισχύουν δύο προϋποθέσεις:

1. Ο $n$ πρέπει να είναι squarefree, δηλαδή να μην διαιρείται από το τετράγωνο κανενός πρώτου.

2. Για κάθε πρώτο $p$ που διαιρεί το $n$, ο $p - 1$ πρέπει να διαιρεί το $n - 1$.

Αν οι δύο αυτές συνθήκες ικανοποιούνται, τότε ο αριθμός συμπεριφέρεται σαν να είναι πρώτος σε κάθε βάση, αν και δεν είναι.

---

⚙️ Γιατί Έχουν Σημασία

Οι αριθμοί Carmichael δεν είναι απλώς ένα θεωρητικό παράδοξο.
Έχουν πρακτική σημασία, ειδικά στην κρυπτογραφία και στα τεστ πρωτότητας που χρησιμοποιούνται στους αλγορίθμους ασφάλειας (όπως το RSA).
Η ύπαρξή τους δείχνει ότι χρειάζονται πιο εξελιγμένες δοκιμές πρωτότητας — όπως το τεστ Miller–Rabin — για να αποφεύγονται ψευδείς θετικοί έλεγχοι.