Τι πρέπει να ξέρεις απέξω
Διαιρετότητα. Ο gcd(a,b) είναι ο μικρότερος θετικός ακέραιος της μορφής ax+by με x,y∈Z (Bézout). Συνέπειες:
- αν d∣a και d∣b, τότε d∣gcd(a,b)·
- αν p πρώτος και p∣ab, τότε p∣a ή p∣b·
- αν gcd(a,n)=1, ο a έχει αντίστροφο modulo n, και από το ac≡bc μπορείς να διαγράψεις το c όταν gcd(c,n)=1·
- gcd(am−1,an−1)=agcd(m,n)−1 για ακέραιο a≥2.
Τα τρία κλασικά θεωρήματα. Για πρώτο p και gcd(a,n)=1:
ap≡a(modp)(Fermat),aφ(n)≡1(modn)(Euler),(p−1)!≡−1(modp)(Wilson).
Τάξη. Αν gcd(a,n)=1, η τάξη ordn(a) είναι ο μικρότερος d≥1 με ad≡1(modn). Ισχύει
ak≡1(modn)⟺ordn(a)∣k,αˊραordn(a)∣φ(n).
Πρωταρχικές ρίζες (μόνο διατύπωση). Υπάρχει g με ordn(g)=φ(n) ακριβώς όταν n∈{1,2,4,pk,2pk} με p περιττό πρώτο. Ειδικά η (Z/pZ)∗ είναι κυκλική τάξης p−1, οπότε η xd≡1(modp) έχει ακριβώς gcd(d,p−1) λύσεις.
Κινεζικό θεώρημα υπολοίπων. Αν gcd(m,n)=1, για κάθε a,b το σύστημα x≡a(modm), x≡b(modn) έχει ακριβώς μία λύση modulo mn. Άρα το πλήθος λύσεων μιας πολυωνυμικής ισοτιμίας modulo n είναι το γινόμενο των πληθών modulo τις δυνάμεις πρώτων του n.
Ο τύπος του Legendre. Με vp τον εκθέτη του p και sp(n) το άθροισμα ψηφίων του n στη βάση p:
vp(n!)=i≥1∑⌊pin⌋=p−1n−sp(n).
Για παράδειγμα v2(100!)=97 και v5(100!)=24, άρα το 100! τελειώνει σε 24 μηδενικά.
Lifting the exponent. Αν p περιττός πρώτος, p∣a−b και p∤ab, τότε για κάθε n≥1
vp(an−bn)=vp(a−b)+vp(n).
Για p=2, με a,b περιττούς και n άρτιο: v2(an−bn)=v2(a−b)+v2(a+b)+v2(n)−1. Παράδειγμα: v3(427−1)=1+3=4 και v2(38−1)=1+2+3−1=5.
Τετραγωνικά υπόλοιπα, σύντομα. Για περιττό πρώτο p, ακριβώς 2p−1 από τα 1,…,p−1 είναι τετράγωνα modulo p. Κριτήριο του Euler: για p∤a,
a(p−1)/2≡{1,−1,a τετραˊγωνο mod p,αλλιωˊς.
Ειδικά το −1 είναι τετράγωνο modulo p ακριβώς όταν p≡1(mod4).
Βασικά λήμματα με σύντομες αποδείξεις
Bézout. Έστω d ο μικρότερος θετικός στο {ax+by}. Διαιρώντας, a=qd+r με 0≤r<d, και το r=a−qd έχει πάλι τη μορφή ax+by. Από την ελαχιστότητα r=0, άρα d∣a, όμοια d∣b. Κάθε κοινός διαιρέτης των a,b διαιρεί το d.
Euler (και Fermat). Αν r1,…,rφ(n) είναι τα υπόλοιπα που είναι πρώτα προς το n, τότε και τα ar1,…,arφ(n) είναι τα ίδια υπόλοιπα με άλλη σειρά (ο πολλαπλασιασμός με a αντιστρέφεται). Εξισώνοντας τα γινόμενα, aφ(n)∏ri≡∏ri, και διαγράφεις το ∏ri.
Wilson. Modulo p, κάθε x∈{1,…,p−1} έχει αντίστροφο. Είναι x≡x−1 μόνο όταν p∣(x−1)(x+1), δηλαδή x≡±1. Τα υπόλοιπα ζευγαρώνονται με τους αντιστρόφους τους, κάθε ζεύγος δίνει γινόμενο 1, και μένει 1⋅(−1).
Η τάξη διαιρεί. Με d=ordn(a) και k=qd+r, 0≤r<d: αν ak≡1, τότε ar≡1, άρα r=0.
Legendre. Ο vp(n!) μετρά κάθε m≤n τόσες φορές όσο είναι ο vp(m). Ο m μετριέται μία φορά για κάθε i με pi∣m, και τα πολλαπλάσια του pi στο {1,…,n} είναι ⌊n/pi⌋.
LTE για περιττό p.
- Αν p∤n: a−ban−bn=∑i=0n−1an−1−ibi≡nbn−1≡0(modp), αφού a≡b.
- Για n=p: γράψε a=b+tp. Τότε ap−1−i≡bp−1−i+(p−1−i)tpbp−2−i(modp2), και αθροίζοντας
i=0∑p−1ap−1−ibi≡pbp−1+tpbp−2⋅2p(p−1)≡pbp−1(modp2),
αφού ο 2p−1 είναι ακέραιος (εδώ χρειάζεται p περιττός). Άρα ο παράγοντας έχει ακριβώς έναν p. Γράφοντας n=pkm με p∤m, εφαρμόζεις τα δύο βήματα επαγωγικά.
Κριτήριο του Euler. Αν a≡x2, τότε a(p−1)/2≡xp−1≡1. Το πολυώνυμο X(p−1)/2−1 έχει στο Fp το πολύ 2p−1 ρίζες, και τα 2p−1 διαφορετικά τετράγωνα (τα x2 και (−x)2 συμπίπτουν) είναι ήδη ρίζες. Για τα υπόλοιπα a είναι (a(p−1)/2)2≡1 και a(p−1)/2≡1, άρα ≡−1.
Τυπικά τεχνάσματα
- Δοκίμασε μικρά moduli. Τα τετράγωνα modulo 8 είναι 0,1,4· οι τέταρτες δυνάμεις modulo 16 είναι 0,1· οι κύβοι modulo 9 είναι 0,±1. Αρκετά «αδύνατα» προβλήματα πεθαίνουν εδώ.
- Κατέβασε τον εκθέτη με την τάξη. Για να βρεις το aNmodn, βρες d με ad≡1 (η τάξη ή ένας διαιρέτης του φ(n)) και κράτα Nmodd.
- Από ισοτιμία σε τάξη. Αν x4≡−y4(modp) με p∤y, τότε (xy−1)4≡−1, άρα ordp(xy−1)=8 και 8∣p−1. Γενικά, αν p≡3(mod4) και p∣x2+y2, τότε p∣x και p∣y.
- Χώρισε με CRT. Η x2≡x(modpk) έχει μόνο τις λύσεις 0,1, γιατί οι x και x−1 είναι πρώτοι μεταξύ τους. Άρα modulo n με r διαφορετικούς πρώτους παράγοντες έχει 2r λύσεις.
- Αθροίσματα δυνάμεων. Για πρώτο p και k≥1, ∑x=0p−1xk≡0(modp) εκτός αν (p−1)∣k, οπότε το άθροισμα είναι ≡−1. (Αν (p−1)∤k, πάρε c με ck≡1· ο πολλαπλασιασμός με c μεταθέτει τα υπόλοιπα, άρα ckS≡S.)
- Πολυώνυμα modulo p. Ένα μη μηδενικό πολυώνυμο βαθμού d έχει το πολύ d ρίζες στο Fp, και Xp−X=∏a∈Fp(X−a).
- Περιστερώνας και πυκνότητα. Ανάμεσα σε n+1 ακέραιους, δύο είναι ισότιμοι modulo n. Από n ακέραιους a1,…,an, κάποιο μη κενό διαδοχικό άθροισμα διαιρείται με n (κοίτα τα n μερικά αθροίσματα και το 0). Για πραγματικό α και N≥1 υπάρχει 1≤q≤N με ∣qα−m∣<N1 για κάποιο ακέραιο m (Dirichlet: N+1 κλασματικά μέρη σε N διαστήματα). Το ίδιο δουλεύει ταυτόχρονα για πολλούς αριθμούς, με κύβους στη θέση των διαστημάτων.
Πώς εμφανίζονται στον IMC
- Τέταρτες δυνάμεις modulo πρώτου (IMC 2007, μέρα 2, θέμα 2). Οι μη μηδενικές τέταρτες δυνάμεις modulo 29 είναι μόνο 7 υπόλοιπα, αφού 4∣28· ένας γρήγορος έλεγχος δείχνει ποια αθροίσματα τριών από αυτά μηδενίζονται.
- CRT για να μετρήσεις λύσεις (IMC 2006, μέρα 1, θέμα 2): η ισοτιμία modulo 10k σπάει σε δύο ισοτιμίες modulo 2k και 5k.
- Πολυωνυμικές ισοτιμίες modulo p (IMC 2020, μέρα 2, θέμα 6· IMC 2023, μέρα 1, θέμα 4· IMC 2022, μέρα 2, θέμα 6): Fermat, πλήθος ριζών στο Fp, αθροίσματα δυνάμεων.
- Legendre και πρώτοι διαιρέτες του n!+1 (IMC 2012, μέρα 2, θέμα 3): κάθε πρώτος διαιρέτης του n!+1 είναι μεγαλύτερος από n.
- 2-αδική εκτίμηση αθροίσματος (IMC 2008, μέρα 2, θέμα 3).
- Μέγιστος κοινός διαιρέτης και Bézout σε σύνολα κλειστά ως προς πράξεις (IMC 2025, μέρα 2, θέμα 7).
- Ταυτόχρονη προσέγγιση Dirichlet (IMC 2026, μέρα 2, θέμα 10).
Παγίδες
- Διαγραφή μόνο με πρώτο προς το modulo. Από 2x≡2(mod6) βγαίνει x≡1(mod3), όχι (mod6).
- Το Euler θέλει gcd(a,n)=1. Το 2φ(4)=4≡1(mod4).
- Το LTE για p=2 έχει άλλο τύπο. Το v2(32−1)=3, ενώ ο τύπος για περιττό p θα έδινε v2(3−1)+v2(2)=2.
- Η πρωταρχική ρίζα δεν υπάρχει πάντα. Modulo 8 κάθε περιττός έχει x2≡1, άρα καμία τάξη δεν είναι φ(8)=4.
Δεν υπάρχουν ακόμα θέματα με αυτά τα εργαλεία.