- Art Gallery -

 

.

Στη θεωρία αριθμών, ο νόμος της τετραγωνικής αντιστρεψιμότητας είναι ένα θεώρημα για την αριθμητική μέτρου που δίνει τις συνθήκες για την φερεγγυότητα των δευτεροβάθμιων εξισώσεων modulo πρώτους αριθμούς. Υπάρχει ένας αριθμός από αντίστοιχες δηλώσεις του θεωρήματος. Μια έκδοση του θεωρηματος ορίζει ότι:

\( \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}} \)

για p και q περιττός πρώτος αριθμός, και \( \left(\frac{p}{q}\right) \) που υποδηλώνει το σύμβολο Legendre

Αυτός ο νόμος, σε συνδυασμό με τις ιδιότητες του συμβόλου Legendre, που σημαίνει ότι μπορεί να υπολογιστεί κάθε σύμβολο Legendre(a/p) . Αυτό καθιστά δυνατό να προσδιοριστεί για κάθε δευτεροβάθμια εξίσωση \( x^2\equiv a \pmod p \) , όπου p περιττός πρώτος, αν έχει μια λύση. Ωστόσο, δεν παρέχει καμία βοήθεια καθόλου για την πραγματική εξεύρεση λύσης. (Το άρθρο σχετικά με τετραγωνική υπολειμμάτων συζητά αλγόριθμους για αυτό.)

Το θεώρημα ήταν εικαζόμενο από τον Euler και Legendre και πρώτη αποδεικνύεται από Gauss. [1] Αναφέρεται σε αυτό ως το «θεμελιώδες θεώρημα" στο Disquisitiones Arithmeticae και τα χαρτιά, το γράψιμό του

Το θεμελιώδες θεώρημα πρέπει ασφαλώς να θεωρηθεί ως ένα από τα πιο κομψά στο είδος του. (Άρθρο. 151) Ιδιωτική αναφέρθηκε σε αυτό ως το «χρυσό θεώρημα.» [2] Έχει εκδώσει έξι αποδείξεις, και δύο ακόμα βρέθηκαν μετά το θάνατο του. Υπάρχουν τώρα πάνω από 200 δημοσιευμένες αποδείξεις. [3]

Η πρώτη ενότητα αυτού του άρθρου δίνει μια ιδιαίτερη περίπτωση των τετραγωνική αμοιβαιότητας, που είναι αντιπροσωπευτική γενική περίπτωση. Η δεύτερη ενότητα δίνει τις συνθέσεις της τετραγωνικής αμοιβαιότητας που βρέθηκαν από Legendre και Gauss.

Παράδειγμα παρακίνησης

Θεωρούμε το πολυώνυμο f (n) = n2 - 5 και τις τιμές για n = 1, 2, 3, 4, ... είναι οι The prime factorizations αυτών των τιμών που δίνονται ως εξής:

n f(n) n f(n) n f(n)
−4 −22 16  251 251 31  956 22⋅239
−1 −1 17 284 22⋅71 32 1019 1019
4 22 18 319 11⋅29 33 1084 22⋅271
11 11 19 356 22⋅89 34 1151 1151
5 20 22⋅5 20 395 5⋅79 35 1220 22⋅5⋅61
6 31 31 21 436 22⋅109 36 1291 1291
7 44 22⋅11 22 479 479 37 1364 22⋅11⋅31
8 59 59 23 524 22⋅131 38 1439 1439
9 76 22⋅19 24 571 571 39 1516 22⋅379
10 95 5⋅19 25 620 22⋅5⋅31 40 1595 5⋅11⋅29
11  116 22⋅29 26 671 11⋅61 41 1676 22⋅419
12 139 139 27 724 22⋅181 42 1759 1759
13 164 22⋅41 28 779 19⋅41 43 1844 22⋅461
14 191 191 29 836 22⋅11⋅19     44 1931 1931
15 220  22⋅5⋅11     30 895  5⋅179 45 2020  22⋅5⋅101

Ένα εντυπωσιακό χαρακτηριστικό των δεδομένων είναι ότι με τις εξαιρέσεις των 2 και 5, οι πρώτοι αριθμοί που εμφανίζονται ως παράγοντες είναι ακριβώς αυτές με το τελικό ψηφίο 1 ή 9.

Ένας άλλος τρόπος διατύπωσης για αυτό είναι ότι η πρώτους p για την οποία υπάρχει μια n τέτοιοι ώστε ο αριθμός n2 ≡ 5 (mod p) είναι ακριβώς 2, 5, και εκείνων πρώτους p που είναι ≡ 1 ή 4 (mod 5).

Το θεώρημα της τετραγωνικής αντιστρεψιμότητας δίνει ένα παρόμοιο χαρακτηρισμό πρώτοι διαιρέτες του f (n) = n2 - c για κάθε ακέραιο c.
Ορολογία, δεδομένα και δύο δηλώσεις του θεωρήματος

Ένα τετραγωνικό υπόλοιπο (mod n) είναι οποιοσδήποτε αριθμός συγλίνει με ένα τετράγωνο (mod n). Μια τετραγωνική nonresidue (mod n) είναι οποιοσδήποτε αριθμός που δεν είναι συγλίνoν με ένα τετράγωνο (mod n). Το επίθετο "τετραγωνική" μπορεί να αλλάξει αν το πλαίσιο καθιστά σαφές ότι αυτό συνεπάγεται. Κατά την εργασία ισοπόλοιπων πρώτων αριθμών (όπως σε αυτό το άρθρο), είναι σύνηθες για το μηδέν ως ειδική περίπτωση. Με αυτόν τον τρόπο, οι ακόλουθες δηλώσεις γίνει πραγματικότητα:

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

Πίνακας τετραγωνικών υπολοίπων
Squares mod primes

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
n2 1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625
mod 3 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1
mod 5 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0 1 4 4 1 0
mod 7 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 2 4 1 0 1 4 2 2
mod 11 1 4 9 5 3 3 5 9 4 1 0 1 4 9 5 3 3 5 9 4 1 0 1 4 9
mod 13 1 4 9 3 12 10 10 12 3 9 4 1 0 1 4 9 3 12 10 10 12 3 9 4 1
mod 17 1 4 9 16 8 2 15 13 13 15 2 8 16 9 4 1 0 1 4 9 16 8 2 15 13
mod 19 1 4 9 16 6 17 11 7 5 5 7 11 17 6 16 9 4 1 0 1 4 9 16 6 17
mod 23 1 4 9 16 2 13 3 18 12 8 6 6 8 12 18 3 13 2 16 9 4 1 0 1 4
mod 29 1 4 9 16 25 7 20 6 23 13 5 28 24 22 22 24 28 5 13 23 6 20 7 25 16
mod 31 1 4 9 16 25 5 18 2 19 7 28 20 14 10 8 8 10 14 20 28 7 19 2 18 5
mod 37 1 4 9 16 25 36 12 27 7 26 10 33 21 11 3 34 30 28 28 30 34 3 11 21 33
mod 41 1 4 9 16 25 36 8 23 40 18 39 21 5 32 20 10 2 37 33 31 31 33 37 2 10
mod 43 1 4 9 16 25 36 6 21 38 14 35 15 40 24 10 41 31 23 17 13 11 11 13 17 23
mod 47 1 4 9 16 25 36 2 17 34 6 27 3 28 8 37 21 7 42 32 24 18 14 12 12 14

Αυτός ο πίνακας είναι πλήρης για περιττών πρώτων λιγότερο από 50. Για να ελέγξετε αν ένας αριθμός m είναι τετραγωνικό υπόλοιπο mod ένα από αυτά πρώτους p, βρείτε ένα ≡ m (mod p) και 0 ≤ A <p. Αν α είναι στη σειρά p, τότε m είναι ένα υπόλειμμα (mod ρ) αν ένας δεν είναι σε σειρά p του πίνακα, τότε το m είναι ένα μη υπόλοιπο (mod p).
-1 ΚΑΙ ΤΟ ΠΡΩΤΟ ΣΥΜΠΛΗΡΩΜΑ

Πρώτα απ 'όλα, για ποιους αριθμούς οι πρώτοι αριθμοί είναι -1 τετραγωνικό υπόλοιπο; Εξετάζοντας τον πίνακα, διαπιστώνουμε -1 σε σειρές 5, 13, 17, 29, 37, και 41 αλλά όχι σε σειρές 3, 7, 11, 19, 23, 31, 43 ή 47.

(−1 ≡ 2 (mod 3), −1 ≡ 4 (mod 5), −1 ≡ 10 (mod 11), etc.)

Οι πρώην πρώτων αριθμών είναι όλα ≡ 1 (mod 4), και η δεύτερη είναι όλα ≡ 3 (mod 4). Αυτό οδηγεί στο :

Το πρώτο συμπλήρωμα τετραγωνική αντιστρεψιμότητας:

\( \text{The congruence }x^2 \equiv -1 \pmod p \text{ is solvable if and only if }p\equiv 1 \pmod 4. \)

±2 και το δεύτερο συμπλήρωμα

Για ποιους αριθμούς οι πρώτοι αριθμοί είναι 2 τετραγωνικό υπόλοιπο; Εξετάζοντας τον πίνακα, βρίσκουμε 2 σε σειρές 7, 17, 23, 31, 41, και 47, αλλά όχι σε σειρές 3, 5, 11, 13, 19, 29, 37, ή 43.

Η πρωτη είναι όλα ≡ ± 1 (mod 8), και η τελευταία είναι όλα ≡ ± 3 (mod 8). Αυτό οδηγεί στο :

Το δεύτερο συμπλήρωμα τετραγωνική αντιστρεψιμότητας:

\( \text{The congruence }x^2 \equiv 2 \pmod p \text{ is solvable if and only if }p\equiv \pm 1 \pmod 8. \)

-2 Είναι σε σειρές 3, 11, 17, 19, 41, 43, αλλά όχι σε σειρές 5, 7, 13, 23, 29, 31, 37, ή 47. Η πρώτη είναι ≡ 1 ή ≡ 3 (mod 8) , και η τελευταία είναι ≡ 5 ή 7 ≡ (mod 8).
±3

3 είναι στις σειρές 11, 13, 23, 37 και 47, αλλά όχι στις σειρές 5, 7, 17, 19, 29, 31, 41, ή, 43.

Η πρώτη είναι ≡ ±1 (mod 12) και η τελευταία είναι ≡ ±5 (mod 12).

-3 είναι στις σειρές 7, 13, 19, 31, 37 και 43, αλλά όχι στις σειρές 5, 11, 17, 23, 29, 41, or 47.Η πρώτη είναι ≡ 1 (mod 3) και η τελευταία ≡ 2 (mod 3).

Δεδομένου ότι το μόνο υπόλοιπο (mod 3) είναι 1, βλέπουμε ότι ο -3 είναι ένα τετραγωνικό υπόλοιπο modulo κάθε πρώτου ο οποίος είναι ένα υπόλοιπο (mod 3).
±5

5 είναι στις σειρές 11, 19, 29, 31, και 41 αλλά όχι στις σειρές 3, 7, 13, 17, 23, 37, 43, or 47.

Η πρώτη είναι ≡ ±1 (mod 5) και η τελευταία είναι ≡ ±2 (mod 5).

Δεδομένου ότι το μόνο υπόλοιπο (mod5) είναι ±1, βλέπουμε ότι ο 5 είναι ένα τετραγωνικό υπόλοιπο modulo κάθε πρώτου ο οποίος είναι ένα υπόλοιπο (mod5).

−5 είναι στις σειρές 3, 7, 23, 29, 41, 43, και 47 αλλά όχι στις σειρές 11, 13, 17, 19, 31, or 37. Η πρώτη είναι ≡ 1, 3, 7, 9 (mod 20) και η τελευταία είναι ≡ 11, 13, 17, 19 (mod 20).

Η έκδοση του Gauss

Οι παρατηρήσεις του σχετικά με το -3 και +5 εξακολουθούν να κρατούν: -7 είναι ένα υπόλοιπο (mod p) αν και μόνο αν p είναι ένα υπόλοιπο (mod7), -11 είναι ένα υπόλοιπο (mod p) αν και μόνο αν p είναι ένα υπόλοιπο (mod 11), +13 είναι ένα υπόλοιπο (mod p) αν και μόνο αν p είναι ένα υπόλοιπο (mod 13), ...

Οι πιο περίπλοκοι κανόνες για τους τετραγωνικούς χαρακτήρες +3 και -5, οι οποίοι εξαρτώνται από τη μαθηματικές αναλογίες (mod 12) και (mod 20) αντίστοιχα, είναι οι ίδιοι με το -3 και +5 δουλεύοντας με το πρώτο συμπλήρωμα.

Για παράδειγμα, για το -5 για να είναι υπόλοιπο (mod p), είτε τα 5 και -1 πρέπει να είναι υπόλοιπα (mod p), είτε και οι δυο να μην υπόλοιπα.

Δηλαδή, p πρέπει να είναι ≡ ±1 (mod 5) και ≡ 1 (mod 4), το οποίο είναι το ίδιο με το p ≡ 1 ή 9 (mod 20), ή p πρέπει να είναι ≡ ±2 mod 5 και ≡ 3 mod 4, το οποίο είναι το ίδιο με το p ≡ 3 or 7 (mod 20).Βλέπε [1]

Παραπομπές

«Chinese remainder theorem».

Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License