uniolympiads English

Θεωρία αριθμών: διαιρετότητα και ισοτιμίες

Bézout, Fermat–Euler–Wilson, τάξη modulo nn, κινεζικό θεώρημα υπολοίπων, ο τύπος του Legendre για το vp(n!)v_p(n!), lifting the exponent, τετραγωνικά υπόλοιπα και επιχειρήματα περιστερώνα.

Τι πρέπει να ξέρεις απέξω

Διαιρετότητα. Ο gcd⁡(a,b)\gcd(a, b) είναι ο μικρότερος θετικός ακέραιος της μορφής ax+byax + by με x,y∈Zx, y \in \Z (Bézout). Συνέπειες:

  • αν d∣ad \mid a και d∣bd \mid b, τότε d∣gcd⁡(a,b)d \mid \gcd(a, b)·
  • αν pp πρώτος και p∣abp \mid ab, τότε p∣ap \mid a ή p∣bp \mid b·
  • αν gcd⁡(a,n)=1\gcd(a, n) = 1, ο aa έχει αντίστροφο modulo nn, και από το ac≡bcac \equiv bc μπορείς να διαγράψεις το cc όταν gcd⁡(c,n)=1\gcd(c, n) = 1·
  • gcd⁡(am−1,an−1)=agcd⁡(m,n)−1\gcd(a^m - 1, a^n - 1) = a^{\gcd(m, n)} - 1 για ακέραιο a≥2a \ge 2.

Τα τρία κλασικά θεωρήματα. Για πρώτο pp και gcd⁡(a,n)=1\gcd(a, n) = 1:

ap≡a(modp)(Fermat),aφ(n)≡1(modn)(Euler),(p−1)!≡−1(modp)(Wilson).a^p \equiv a \pmod p \quad \text{(Fermat)}, \qquad a^{\varphi(n)} \equiv 1 \pmod n \quad \text{(Euler)}, \qquad (p - 1)! \equiv -1 \pmod p \quad \text{(Wilson)}.

Τάξη. Αν gcd⁡(a,n)=1\gcd(a, n) = 1, η τάξη ord⁡n(a)\operatorname{ord}_n(a) είναι ο μικρότερος d≥1d \ge 1 με ad≡1(modn)a^d \equiv 1 \pmod n. Ισχύει

ak≡1(modn)  ⟺  ord⁡n(a)∣k,αˊραord⁡n(a)∣φ(n).a^k \equiv 1 \pmod n \iff \operatorname{ord}_n(a) \mid k, \qquad \text{άρα} \quad \operatorname{ord}_n(a) \mid \varphi(n).

Πρωταρχικές ρίζες (μόνο διατύπωση). Υπάρχει gg με ord⁡n(g)=φ(n)\operatorname{ord}_n(g) = \varphi(n) ακριβώς όταν n∈{1,2,4,pk,2pk}n \in \{1, 2, 4, p^k, 2p^k\} με pp περιττό πρώτο. Ειδικά η (Z/pZ)∗(\Z/p\Z)^{*} είναι κυκλική τάξης p−1p - 1, οπότε η xd≡1(modp)x^d \equiv 1 \pmod p έχει ακριβώς gcd⁡(d,p−1)\gcd(d, p - 1) λύσεις.

Κινεζικό θεώρημα υπολοίπων. Αν gcd⁡(m,n)=1\gcd(m, n) = 1, για κάθε a,ba, b το σύστημα x≡a(modm)x \equiv a \pmod m, x≡b(modn)x \equiv b \pmod n έχει ακριβώς μία λύση modulo mnmn. Άρα το πλήθος λύσεων μιας πολυωνυμικής ισοτιμίας modulo nn είναι το γινόμενο των πληθών modulo τις δυνάμεις πρώτων του nn.

Ο τύπος του Legendre. Με vpv_p τον εκθέτη του pp και sp(n)s_p(n) το άθροισμα ψηφίων του nn στη βάση pp:

vp(n!)=∑i≥1⌊npi⌋=n−sp(n)p−1.v_p(n!) = \sum_{i \ge 1} \left\lfloor \frac{n}{p^i} \right\rfloor = \frac{n - s_p(n)}{p - 1} .

Για παράδειγμα v2(100!)=97v_2(100!) = 97 και v5(100!)=24v_5(100!) = 24, άρα το 100!100! τελειώνει σε 2424 μηδενικά.

Lifting the exponent. Αν pp περιττός πρώτος, p∣a−bp \mid a - b και p∤abp \nmid ab, τότε για κάθε n≥1n \ge 1

vp(an−bn)=vp(a−b)+vp(n).v_p(a^n - b^n) = v_p(a - b) + v_p(n) .

Για p=2p = 2, με a,ba, b περιττούς και nn άρτιο: v2(an−bn)=v2(a−b)+v2(a+b)+v2(n)−1v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1. Παράδειγμα: v3(427−1)=1+3=4v_3(4^{27} - 1) = 1 + 3 = 4 και v2(38−1)=1+2+3−1=5v_2(3^8 - 1) = 1 + 2 + 3 - 1 = 5.

Τετραγωνικά υπόλοιπα, σύντομα. Για περιττό πρώτο pp, ακριβώς p−12\frac{p - 1}{2} από τα 1,…,p−11, \dots, p - 1 είναι τετράγωνα modulo pp. Κριτήριο του Euler: για p∤ap \nmid a,

a(p−1)/2≡{1,a τετραˊγωνο mod p,−1,αλλιωˊς.a^{(p-1)/2} \equiv \begin{cases} 1, & a \text{ τετράγωνο mod } p, \\ -1, & \text{αλλιώς}. \end{cases}

Ειδικά το −1-1 είναι τετράγωνο modulo pp ακριβώς όταν p≡1(mod4)p \equiv 1 \pmod 4.

Βασικά λήμματα με σύντομες αποδείξεις

Bézout. Έστω dd ο μικρότερος θετικός στο {ax+by}\{ax + by\}. Διαιρώντας, a=qd+ra = qd + r με 0≤r<d0 \le r < d, και το r=a−qdr = a - qd έχει πάλι τη μορφή ax+byax + by. Από την ελαχιστότητα r=0r = 0, άρα d∣ad \mid a, όμοια d∣bd \mid b. Κάθε κοινός διαιρέτης των a,ba, b διαιρεί το dd.

Euler (και Fermat). Αν r1,…,rφ(n)r_1, \dots, r_{\varphi(n)} είναι τα υπόλοιπα που είναι πρώτα προς το nn, τότε και τα ar1,…,arφ(n)a r_1, \dots, a r_{\varphi(n)} είναι τα ίδια υπόλοιπα με άλλη σειρά (ο πολλαπλασιασμός με aa αντιστρέφεται). Εξισώνοντας τα γινόμενα, aφ(n)∏ri≡∏ria^{\varphi(n)} \prod r_i \equiv \prod r_i, και διαγράφεις το ∏ri\prod r_i.

Wilson. Modulo pp, κάθε x∈{1,…,p−1}x \in \{1, \dots, p - 1\} έχει αντίστροφο. Είναι x≡x−1x \equiv x^{-1} μόνο όταν p∣(x−1)(x+1)p \mid (x - 1)(x + 1), δηλαδή x≡±1x \equiv \pm 1. Τα υπόλοιπα ζευγαρώνονται με τους αντιστρόφους τους, κάθε ζεύγος δίνει γινόμενο 11, και μένει 1⋅(−1)1 \cdot (-1).

Η τάξη διαιρεί. Με d=ord⁡n(a)d = \operatorname{ord}_n(a) και k=qd+rk = qd + r, 0≤r<d0 \le r < d: αν ak≡1a^k \equiv 1, τότε ar≡1a^r \equiv 1, άρα r=0r = 0.

Legendre. Ο vp(n!)v_p(n!) μετρά κάθε m≤nm \le n τόσες φορές όσο είναι ο vp(m)v_p(m). Ο mm μετριέται μία φορά για κάθε ii με pi∣mp^i \mid m, και τα πολλαπλάσια του pip^i στο {1,…,n}\{1, \dots, n\} είναι ⌊n/pi⌋\lfloor n / p^i \rfloor.

LTE για περιττό pp.

  • Αν p∤np \nmid n: an−bna−b=∑i=0n−1an−1−ibi≡nbn−1≢0(modp)\frac{a^n - b^n}{a - b} = \sum_{i=0}^{n-1} a^{n-1-i} b^i \equiv n b^{n-1} \not\equiv 0 \pmod p, αφού a≡ba \equiv b.
  • Για n=pn = p: γράψε a=b+tpa = b + tp. Τότε ap−1−i≡bp−1−i+(p−1−i) tp bp−2−i(modp2)a^{p-1-i} \equiv b^{p-1-i} + (p - 1 - i)\, t p\, b^{p-2-i} \pmod{p^2}, και αθροίζοντας
∑i=0p−1ap−1−ibi≡p bp−1+tp bp−2⋅p(p−1)2≡p bp−1(modp2),\sum_{i=0}^{p-1} a^{p-1-i} b^i \equiv p\, b^{p-1} + tp\, b^{p-2} \cdot \frac{p(p-1)}{2} \equiv p\, b^{p-1} \pmod{p^2},

αφού ο p−12\frac{p - 1}{2} είναι ακέραιος (εδώ χρειάζεται pp περιττός). Άρα ο παράγοντας έχει ακριβώς έναν pp. Γράφοντας n=pkmn = p^k m με p∤mp \nmid m, εφαρμόζεις τα δύο βήματα επαγωγικά.

Κριτήριο του Euler. Αν a≡x2a \equiv x^2, τότε a(p−1)/2≡xp−1≡1a^{(p-1)/2} \equiv x^{p-1} \equiv 1. Το πολυώνυμο X(p−1)/2−1X^{(p-1)/2} - 1 έχει στο Fp\F_p το πολύ p−12\frac{p-1}{2} ρίζες, και τα p−12\frac{p - 1}{2} διαφορετικά τετράγωνα (τα x2x^2 και (−x)2(-x)^2 συμπίπτουν) είναι ήδη ρίζες. Για τα υπόλοιπα aa είναι (a(p−1)/2)2≡1\big(a^{(p-1)/2}\big)^2 \equiv 1 και a(p−1)/2≢1a^{(p-1)/2} \not\equiv 1, άρα ≡−1\equiv -1.

Τυπικά τεχνάσματα

  • Δοκίμασε μικρά moduli. Τα τετράγωνα modulo 88 είναι 0,1,40, 1, 4· οι τέταρτες δυνάμεις modulo 1616 είναι 0,10, 1· οι κύβοι modulo 99 είναι 0,±10, \pm 1. Αρκετά «αδύνατα» προβλήματα πεθαίνουν εδώ.
  • Κατέβασε τον εκθέτη με την τάξη. Για να βρεις το aN mod na^N \bmod n, βρες dd με ad≡1a^d \equiv 1 (η τάξη ή ένας διαιρέτης του φ(n)\varphi(n)) και κράτα N mod dN \bmod d.
  • Από ισοτιμία σε τάξη. Αν x4≡−y4(modp)x^4 \equiv -y^4 \pmod p με p∤yp \nmid y, τότε (xy−1)4≡−1(x y^{-1})^4 \equiv -1, άρα ord⁡p(xy−1)=8\operatorname{ord}_p(x y^{-1}) = 8 και 8∣p−18 \mid p - 1. Γενικά, αν p≡3(mod4)p \equiv 3 \pmod 4 και p∣x2+y2p \mid x^2 + y^2, τότε p∣xp \mid x και p∣yp \mid y.
  • Χώρισε με CRT. Η x2≡x(modpk)x^2 \equiv x \pmod{p^k} έχει μόνο τις λύσεις 0,10, 1, γιατί οι xx και x−1x - 1 είναι πρώτοι μεταξύ τους. Άρα modulo nn με rr διαφορετικούς πρώτους παράγοντες έχει 2r2^r λύσεις.
  • Αθροίσματα δυνάμεων. Για πρώτο pp και k≥1k \ge 1, ∑x=0p−1xk≡0(modp)\sum_{x=0}^{p-1} x^k \equiv 0 \pmod p εκτός αν (p−1)∣k(p - 1) \mid k, οπότε το άθροισμα είναι ≡−1\equiv -1. (Αν (p−1)∤k(p - 1) \nmid k, πάρε cc με ck≢1c^k \not\equiv 1· ο πολλαπλασιασμός με cc μεταθέτει τα υπόλοιπα, άρα ckS≡Sc^k S \equiv S.)
  • Πολυώνυμα modulo pp. Ένα μη μηδενικό πολυώνυμο βαθμού dd έχει το πολύ dd ρίζες στο Fp\F_p, και Xp−X=∏a∈Fp(X−a)X^p - X = \prod_{a \in \F_p} (X - a).
  • Περιστερώνας και πυκνότητα. Ανάμεσα σε n+1n + 1 ακέραιους, δύο είναι ισότιμοι modulo nn. Από nn ακέραιους a1,…,ana_1, \dots, a_n, κάποιο μη κενό διαδοχικό άθροισμα διαιρείται με nn (κοίτα τα nn μερικά αθροίσματα και το 00). Για πραγματικό α\alpha και N≥1N \ge 1 υπάρχει 1≤q≤N1 \le q \le N με ∣qα−m∣<1N|q \alpha - m| < \frac{1}{N} για κάποιο ακέραιο mm (Dirichlet: N+1N + 1 κλασματικά μέρη σε NN διαστήματα). Το ίδιο δουλεύει ταυτόχρονα για πολλούς αριθμούς, με κύβους στη θέση των διαστημάτων.

Πώς εμφανίζονται στον IMC

  • Τέταρτες δυνάμεις modulo πρώτου (IMC 2007, μέρα 2, θέμα 2). Οι μη μηδενικές τέταρτες δυνάμεις modulo 2929 είναι μόνο 77 υπόλοιπα, αφού 4∣284 \mid 28· ένας γρήγορος έλεγχος δείχνει ποια αθροίσματα τριών από αυτά μηδενίζονται.
  • CRT για να μετρήσεις λύσεις (IMC 2006, μέρα 1, θέμα 2): η ισοτιμία modulo 10k10^{k} σπάει σε δύο ισοτιμίες modulo 2k2^k και 5k5^k.
  • Πολυωνυμικές ισοτιμίες modulo pp (IMC 2020, μέρα 2, θέμα 6· IMC 2023, μέρα 1, θέμα 4· IMC 2022, μέρα 2, θέμα 6): Fermat, πλήθος ριζών στο Fp\F_p, αθροίσματα δυνάμεων.
  • Legendre και πρώτοι διαιρέτες του n!+1n! + 1 (IMC 2012, μέρα 2, θέμα 3): κάθε πρώτος διαιρέτης του n!+1n! + 1 είναι μεγαλύτερος από nn.
  • 22-αδική εκτίμηση αθροίσματος (IMC 2008, μέρα 2, θέμα 3).
  • Μέγιστος κοινός διαιρέτης και Bézout σε σύνολα κλειστά ως προς πράξεις (IMC 2025, μέρα 2, θέμα 7).
  • Ταυτόχρονη προσέγγιση Dirichlet (IMC 2026, μέρα 2, θέμα 10).

Παγίδες

  • Διαγραφή μόνο με πρώτο προς το modulo. Από 2x≡2(mod6)2x \equiv 2 \pmod 6 βγαίνει x≡1(mod3)x \equiv 1 \pmod 3, όχι (mod6)\pmod 6.
  • Το Euler θέλει gcd⁡(a,n)=1\gcd(a, n) = 1. Το 2φ(4)=4≢1(mod4)2^{\varphi(4)} = 4 \not\equiv 1 \pmod 4.
  • Το LTE για p=2p = 2 έχει άλλο τύπο. Το v2(32−1)=3v_2(3^2 - 1) = 3, ενώ ο τύπος για περιττό pp θα έδινε v2(3−1)+v2(2)=2v_2(3 - 1) + v_2(2) = 2.
  • Η πρωταρχική ρίζα δεν υπάρχει πάντα. Modulo 88 κάθε περιττός έχει x2≡1x^2 \equiv 1, άρα καμία τάξη δεν είναι φ(8)=4\varphi(8) = 4.

Για μελέτη

  • Gelca & Andreescu, Putnam and Beyond, §1.3 (The Pigeonhole Principle)

Θέματα διαγωνισμών με αυτά τα εργαλεία

Δεν υπάρχουν ακόμα θέματα με αυτά τα εργαλεία.