🔢 Το Θεώρημα του Zsigmondy — Ένα ισχυρό εργαλείο σε προβλήματα Ολυμπιάδων

Πολλά δύσκολα προβλήματα Θεωρίας Αριθμών σε μαθηματικές Ολυμπιάδες γίνονται εντυπωσιακά απλούστερα όταν χρησιμοποιήσουμε ένα βαθύτερο θεώρημα.

Ένα από τα πιο χρήσιμα είναι το Θεώρημα του Zsigmondy, που πήρε το όνομά του από τον Αυστροούγγρο μαθηματικό Karl Zsigmondy.

Η βασική ιδέα του είναι όμορφη: καθώς αυξάνεται ο εκθέτης σε παραστάσεις όπως

\[ a^n-b^n, \]

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

📐 Θεώρημα του Zsigmondy — Πρώτη μορφή

Έστω θετικοί ακέραιοι \(a,b,n\), με

\[ a>b,\qquad \gcd(a,b)=1,\qquad n\ge2. \]

Τότε ο αριθμός

\[ a^n-b^n \]

έχει τουλάχιστον έναν πρώτο διαιρέτη που δεν διαιρεί κανέναν από τους αριθμούς

\[ a^k-b^k,\qquad k<n, \]

με δύο εξαιρέσεις:

\[ \boxed{2^6-1^6} \]

και την περίπτωση

\[ \boxed{n=2\quad\text{και}\quad a+b\text{ δύναμη του }2}. \]

Ένας τέτοιος πρώτος ονομάζεται συχνά πρωταρχικός πρώτος διαιρέτης (primitive prime divisor).

📐 Θεώρημα του Zsigmondy — Δεύτερη μορφή

Αν \(a,b,n\) είναι θετικοί ακέραιοι με

\[ a>b,\qquad \gcd(a,b)=1,\qquad n\ge2, \]

τότε ο αριθμός

\[ a^n+b^n \]

έχει τουλάχιστον έναν πρώτο διαιρέτη που δεν διαιρεί κανέναν από τους αριθμούς

\[ a^k+b^k,\qquad k<n, \]

με εξαίρεση την περίπτωση

\[ \boxed{2^3+1^3=9}. \]

💡 Η ουσία

Όταν ο εκθέτης μεγαλώνει, το \(a^n-b^n\) — και στην αντίστοιχη μορφή το \(a^n+b^n\) — συνήθως αναγκάζεται να αποκτήσει έναν νέο πρώτο διαιρέτη. Αυτή ακριβώς η εμφάνιση ενός «νέου» πρώτου δημιουργεί ισχυρούς περιορισμούς σε διοφαντικές εξισώσεις.

1️⃣ Παράδειγμα — Japanese Mathematical Olympiad 2011

Να βρεθούν όλες οι τετράδες θετικών ακεραίων

\[ (a,n,p,q,r) \]

— με την ομαδοποίηση των μεταβλητών όπως δίνεται στην πηγή — για τις οποίες

\[ \boxed{ a^n-1=(a^p-1)(a^q-1)(a^r-1) }. \]

Λύση

Αν

\[ a\ge3,\qquad n\ge3, \]

τότε, από το Θεώρημα του Zsigmondy, ο αριθμός \(a^n-1\) διαθέτει έναν πρωταρχικό πρώτο διαιρέτη: έναν πρώτο που δεν διαιρεί κανέναν αριθμό

\[ a^k-1,\qquad k<n. \]

Όμως στη δεξιά πλευρά εμφανίζονται μόνο παράγοντες της μορφής

\[ a^p-1,\qquad a^q-1,\qquad a^r-1. \]

Έτσι, όταν οι εκθέτες \(p,q,r\) είναι μικρότεροι από \(n\), ο νέος πρώτος διαιρέτης που εγγυάται το Zsigmondy δεν μπορεί να εμφανιστεί στη δεξιά πλευρά.

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

Το ουσιαστικό σημείο του παραδείγματος είναι ακριβώς αυτό: μια φαινομενικά δύσκολη παραγοντική εξίσωση περιορίζεται δραστικά επειδή το \(a^n-1\) πρέπει να διαθέτει έναν νέο πρώτο παράγοντα.

2️⃣ Παράδειγμα — IMO Shortlist 2000

Να βρεθούν όλες οι τριάδες θετικών ακεραίων \((a,m,n)\) που ικανοποιούν

\[ \boxed{ a^m+1\mid(a+1)^n }. \]

Λύση

Η πηγή δίνει ως λύσεις

\[ \boxed{(a,m)=(2,3)} \]

με

\[ n\ge2. \]

Πράγματι,

\[ 2^3+1=9 \]

και

\[ 9\mid3^n \]

για κάθε \(n\ge2\).

Τώρα έστω

\[ a>1,\qquad m\ge2 \]

και διαφορετικά από την εξαιρετική περίπτωση \((a,m)=(2,3)\).

Από το Θεώρημα του Zsigmondy, ο \(a^m+1\) έχει έναν πρώτο διαιρέτη που δεν διαιρεί το \(a+1\).

Αν όμως

\[ a^m+1\mid(a+1)^n, \]

κάθε πρώτος διαιρέτης του \(a^m+1\) θα έπρεπε αναγκαστικά να διαιρεί το \(a+1\).

Άτοπο.

Οι περιπτώσεις

\[ a=1 \]

ή

\[ m=1 \]

ελέγχονται άμεσα και δίνουν τις υπόλοιπες προφανείς λύσεις.

3️⃣ Παράδειγμα — Math Olympiad Summer Program 2001

Να βρεθούν όλες οι τετράδες θετικών ακεραίων

\[ (x,r,p,n) \]

τέτοιες ώστε \(p\) να είναι πρώτος, \(n,r>1\) και

\[ \boxed{x^r-1=p^n}. \]

Λύση

Αν ο \(x^r-1\) έχει έναν πρώτο διαιρέτη που δεν διαιρεί το \(x-1\), τότε — επειδή

\[ x^r-1=p^n \]

έχει μόνο έναν διακεκριμένο πρώτο διαιρέτη — προκύπτει ότι ο \(x^r-1\) θα έπρεπε να έχει τουλάχιστον δύο διαφορετικούς πρώτους παράγοντες.

Αυτό είναι αδύνατο.

Επομένως βρισκόμαστε αναγκαστικά σε μία από τις εξαιρέσεις του Θεωρήματος του Zsigmondy:

\[ r=2, \]

ή στην ειδική περίπτωση

\[ x=2,\qquad r=6. \]

Η δεύτερη περίπτωση δεν λειτουργεί, αφού

\[ 2^6-1=63 \]

δεν είναι δύναμη ενός μόνο πρώτου.

Άρα

\[ r=2. \]

Τότε

\[ p^n=x^2-1=(x+1)(x-1). \]

Επειδή \(x-1\) και \(x+1\) διαφέρουν κατά \(2\), και το γινόμενό τους είναι δύναμη ενός μόνο πρώτου, αναγκαστικά

\[ p=2. \]

Άρα

\[ 2^n=(x+1)(x-1). \]

Η πηγή το γράφει στη μορφή

\[ 2^n=2(2^n-2), \]

από όπου προκύπτει

\[ n=3 \]

και συνεπώς

\[ x=3. \]

Άρα η λύση είναι

\[ \boxed{(x,r,p,n)=(3,2,2,3)}. \]

4️⃣ Παράδειγμα — Czech–Slovak Match 1996

Να βρεθούν όλες οι θετικές ακέραιες λύσεις της εξίσωσης

\[ \boxed{ p^x-y^p=1 } \]

όπου \(p\) είναι πρώτος αριθμός.

Λύση

Γράφουμε την εξίσωση ως

\[ p^x=y^p+1. \]

Αρχικά, αν

\[ y=1, \]

τότε

\[ p^x=2, \]

και συνεπώς

\[ \boxed{(p,x,y)=(2,1,1)}. \]

Τώρα έστω

\[ y>1. \]

Αν

\[ p\ne3, \]

τότε, σύμφωνα με το Θεώρημα του Zsigmondy, ο αριθμός

\[ y^p+1 \]

έχει έναν πρώτο διαιρέτη που δεν διαιρεί το

\[ y+1. \]

Όμως

\[ y^p+1=p^x \]

είναι δύναμη ενός μόνο πρώτου.

Από την άλλη, επειδή \(p\) είναι περιττός στην περίπτωση αυτή,

\[ y+1\mid y^p+1. \]

Άρα ο \(y^p+1\) θα έπρεπε να έχει τουλάχιστον δύο διαφορετικούς πρώτους διαιρέτες — αντίφαση.

Μένει λοιπόν η εξαιρετική περίπτωση

\[ p=3. \]

Η πηγή καταλήγει έτσι στις αντίστοιχες μικρές λύσεις, μαζί με την περίπτωση \(y=1\) που εξετάστηκε προηγουμένως.

💡 Γιατί το Θεώρημα του Zsigmondy είναι τόσο χρήσιμο στις Ολυμπιάδες;

Σε μια εξίσωση όπως

\[ a^n-b^n=p^k \]

ή

\[ a^n+b^n\mid c^m, \]

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

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

μεγαλύτερος εκθέτης → νέος πρώτος διαιρέτης → ισχυρός περιορισμός → συχνά αντίφαση

📚

Έρχεται το πολλαπλό βιβλίο ΝΕΟ — βρες όλες τις επιλογές εδώΠολλαπλό βιβλίο ΝΕΟ — 437 βιβλία σε PDF

PDF & Ψηφιακά Μαθησιακά Αντικείμενα — χωρίς εγγραφή • Portify

📚 437 βιβλία🎬 22.000+ Ψηφιακά Μαθησιακά Αντικείμενα

Δες τα βιβλία →