An Old Chinese Theorem and Pierre de Fermat – From Fermat’s Little Theorem to Pseudoprimes

Ένα παλιό κινεζικό θεώρημα και ο Πιερ ντε Φερμά

Η ιστορία της θεωρίας αριθμών είναι γεμάτη από απλές, αλλά απίστευτα δυνατές ιδέες. Μία από αυτές συνδέει ένα παλιό κινεζικό κριτήριο για πρώτους αριθμούς με το διάσημο Μικρό Θεώρημα του Φερμά, και οδηγεί στη μελέτη των λεγόμενων ψευδοπρώτων.

Το Μικρό Θεώρημα του Φερμά

Ο Πιερ ντε Φερμά παρατήρησε ότι αν ο αριθμός p είναι πρώτος και a δεν διαιρείται από το p, τότε ισχύει

a^p−1 ≡ 1 (mod p).

Μια πολύ ιδιαίτερη περίπτωση, που μας ενδιαφέρει εδώ, είναι όταν παίρνουμε a = 2 και p περιττό πρώτος. Τότε

2^p−1 ≡ 1 (mod p).

Αυτό επιτρέπει ένα τεστ για το αν ένας αριθμός είναι πρώτος: αν για έναν περιττό θετικό ακέραιο n ισχύει

2ⁿ⁻¹ ≡ 1 (mod n),

τότε ίσως ο n να είναι πρώτος. Το “ίσως” είναι κλειδί: υπάρχουν σύνθετοι αριθμοί που περνούν αυτό το τεστ.

Το «παλιό κινεζικό» κριτήριο

Κινέζοι μαθηματικοί χρησιμοποίησαν για αιώνες το εξής κριτήριο: ένας περιττός αριθμός n είναι πρώτος, αν και μόνο αν

n | 2ⁿ⁻¹ − 1.

Σήμερα ξέρουμε ότι αυτό δεν ισχύει απόλυτα· ορισμένοι σύνθετοι αριθμοί “συμπεριφέρονται” σαν πρώτοι ως προς τη βάση 2. Αυτοί λέγονται ψευδοπρώτοι στη βάση 2.

Παράδειγμα ψευδοπρώτου

Ένας κλασικός ψευδοπρώτος στη βάση 2 είναι ο αριθμός:

341 = 11 · 31.

Είναι προφανώς σύνθετος, αλλά μπορούμε να δείξουμε ότι

2³⁴⁰ ≡ 1 (mod 341).

Άρα ως προς τη βάση 2 συμπεριφέρεται σαν να ήταν πρώτος, κάτι που καταρρίπτει τη “σφιχτή” εκδοχή του κινεζικού κριτηρίου.

Από τον n στο 2ⁿ − 1

Το απόσπασμα που είδες στο βιβλίο ασχολείται με την εξής ιδέα: αν ένας σύνθετος περιττός αριθμός n είναι ψευδοπρώτος στη βάση 2, τότε μπορούμε να μελετήσουμε τον αριθμό

2ⁿ − 1.

Ο στόχος είναι να δείξουμε ότι και αυτός έχει «παρόμοια» ιδιότητα, δηλαδή ότι διαιρεί έναν αριθμό της μορφής 2^k − 1 για κατάλληλο k, ή ότι εμφανίζεται σε μια αλυσίδα σχέσεων τύπου Φερμά. Η απόδειξη στηρίζεται στην παραγοντοποίηση

2^ab − 1 = (2^a − 1)(2^a(b−1) + 2^a(b−2) + … + 1)

όταν n = ab με περιττούς ακεραίους a και b. Έτσι φαίνεται καθαρά ότι 2^a − 1 και 2^b − 1 παίζουν ρόλο στη δομή του 2ⁿ − 1.

Μία χαρακτηριστική ιδέα της απόδειξης

Χονδρικά, η λογική είναι η εξής:

1. Θεωρούμε έναν περιττό σύνθετο αριθμό n με την ιδιότητα ότι διαιρεί το 2ⁿ⁻¹ − 1.
2. Γράφουμε n = ab με α, b περιττούς και μεγαλύτερους από 1.
3. Εξετάζουμε αριθμούς της μορφής 2^k − 1 όπου το k σχετίζεται με το n, π.χ. k = 2n − 2 ή k = (2ⁿ − 1), και χρησιμοποιούμε παραγοντοποιήσεις για να δείξουμε ότι n (ή παράγοντές του) συνεχίζουν να διαιρούν κατάλληλες εκφράσεις.
4. Εμφανίζονται έτσι σειρές ψευδοπρώτων, όπου η ιδιότητα “μοιάζω με πρώτο στη βάση 2” μεταφέρεται από έναν αριθμό σε άλλους, μεγαλύτερους.

Το πνεύμα της απόδειξης συνδέεται στενά με τεχνικές που αγαπούν οι σύγχρονες ολυμπιάδες: έξυπνη παραγοντοποίηση, χρήση του Μικρού Θεωρήματος του Φερμά και προσεκτική μελέτη διαιρέσεων.

Γιατί η ιστορία αυτή είναι σημαντική;

• Δείχνει ότι απλά κριτήρια πρώτου αριθμού χρειάζονται μεγάλη προσοχή.
• Αναδεικνύει την έννοια του ψευδοπρώτου, βασική στην κρυπτογραφία και στη θεωρία δοκιμών πρώτου.
• Συνδέει την αρχαία κινεζική παράδοση με την ευρωπαϊκή θεωρία αριθμών του 17ου αιώνα.

Μικρές παρατηρήσεις, όπως αυτή του Φερμά, γεννούν βαθιά ερωτήματα: πότε ένα απλό κριτήριο είναι αρκετό, και πότε εμφανίζονται «εξαιρέσεις» που μας αναγκάζουν να κοιτάξουμε πιο βαθιά;

An Old Chinese Theorem and Pierre de Fermat

The history of number theory is full of ideas that are easy to state but surprisingly powerful. One beautiful story connects an old Chinese primality test with Fermat’s little theorem and leads naturally to the study of pseudoprimes.

Fermat’s Little Theorem

Pierre de Fermat observed that if p is a prime and a is not divisible by p, then

a^p−1 ≡ 1 (mod p).

In the special case a = 2 and odd prime p we get

2^p−1 ≡ 1 (mod p).

This suggests a simple primality test: for an odd integer n, if

2ⁿ⁻¹ ≡ 1 (mod n),

then perhaps n is prime. The word “perhaps” is crucial: some composite numbers also satisfy this congruence.

The “old Chinese” criterion

Chinese mathematicians used for centuries the statement that an odd number n is prime if and only if

n | 2ⁿ⁻¹ − 1.

Today we know this is not universally true. Certain composite numbers behave like primes with respect to base 2. These are called base-2 pseudoprimes.

A classic pseudoprime

A well-known example is

341 = 11 · 31.

Although clearly composite, one can show that

2³⁴⁰ ≡ 1 (mod 341).

So, with respect to base 2, 341 behaves like a prime. This already disproves the strict form of the Chinese criterion.

From n to 2ⁿ − 1

The book page you saw discusses the following idea: if an odd composite integer n is a base-2 pseudoprime, then it is natural to look at the number

2ⁿ − 1.

The aim is to show that this number also has a related property: it divides, or is a factor of, an expression of the form 2^k − 1 for suitable k, or belongs to a chain of Fermat-type congruences. The proof uses the factorisation

2^ab − 1 = (2^a − 1)(2^a(b−1) + 2^a(b−2) + … + 1)

for n = ab with odd integers a, b. This exposes the roles of 2^a − 1 and 2^b − 1 in the structure of 2ⁿ − 1.

A characteristic proof idea

Very roughly, the argument proceeds like this:

1. Take an odd composite n such that n divides 2ⁿ⁻¹ − 1.
2. Write n = ab with odd integers a, b > 1.
3. Study numbers of the form 2^k − 1 where k is related to n, for example k = 2n − 2 or k = 2ⁿ − 1, and use factorisations to show that n (or its factors) keep dividing suitable expressions.
4. This gives chains of pseudoprimes, where the property “I look prime in base 2” is propagated from one number to others.

The spirit of the proof is very close to modern olympiad techniques: clever factorisation, Fermat’s little theorem and a careful study of divisibility.

Why this story matters

• It shows that simple primality tests must be treated with care.
• It highlights the concept of pseudoprimes, fundamental in cryptography and primality testing.
• It connects ancient Chinese mathematics with European number theory of the 17th century.

Small observations, like Fermat’s, can lead to deep questions: when is a simple test enough, and when do the “exceptions” force us to look deeper into the structure of numbers?