Υπόλοιπο διαίρεσης!

Συντονιστές: cretanman, silouan, rek2

Άβαταρ μέλους
matha
Γενικός Συντονιστής
Δημοσιεύσεις: 6271
Εγγραφή: Παρ Μάιος 21, 2010 7:40 pm
Τοποθεσία: Θεσσαλονίκη

Υπόλοιπο διαίρεσης!

#1

Μη αναγνωσμένη δημοσίευση από matha » Πέμ Ιαν 25, 2018 10:02 am

Ας είναι \displaystyle{p} πρώτος.Θεωρούμε τον αριθμό

\displaystyle{\xi=\prod_{k=1}^{p-1}(k^2+1).}

Να βρεθεί το υπόλοιπο της διαίρεσης \displaystyle{\xi :p.}


Μάγκος Θάνος

Λέξεις Κλειδιά:
Άβαταρ μέλους
emouroukos
Συντονιστής
Δημοσιεύσεις: 1417
Εγγραφή: Δευ Δεκ 22, 2008 1:27 pm
Τοποθεσία: Αγρίνιο

Re: Υπόλοιπο διαίρεσης!

#2

Μη αναγνωσμένη δημοσίευση από emouroukos » Πέμ Ιαν 25, 2018 3:46 pm

Αν \displaystyle p = 2, τότε \displaystyle \xi  = 2 και το ζητούμενο υπόλοιπο είναι ίσο με \displaystyle 0.

Έστω ότι ο \displaystyle p είναι περιττός πρώτος.

\bullet Αν \displaystyle p \equiv 1\left( {\bmod 4} \right), τότε \displaystyle \left( {\frac{{ - 1}}{p}} \right) = 1 και άρα υπάρχει \displaystyle k \in \left\{ {1,2, \ldots ,p - 1} \right\} τέτοιο, ώστε \displaystyle {k^2} + 1 \equiv 0\left( {\bmod p} \right). Συνεπώς, \displaystyle \xi  \equiv 0\left( {\bmod p} \right).

\bullet Έστω ότι \displaystyle p \equiv 3\left( {\bmod 4} \right). Τότε, είναι \displaystyle \left( {\frac{{ - 1}}{p}} \right) = -1 και άρα \displaystyle {k^2} + 1 \not\equiv 0\left( {\bmod p} \right) για κάθε \displaystyle k \in \left\{ {1,2, \ldots ,p - 1} \right\}. Παρατηρούμε ότι αν \displaystyle i,j \in \left\{ {1,2, \ldots ,\frac{{p - 1}}{2}} \right\} με \displaystyle i \ne j, τότε \displaystyle {i^2} + 1 \not\equiv {j^2} + 1\left( {\bmod p} \right), ενώ αν \displaystyle i,j \in \left\{ {1,2, \ldots ,p - 1} \right\} με \displaystyle i \ne j, τότε \displaystyle {i^2} + 1 \equiv {j^2} + 1\left( {\bmod p} \right) \Leftrightarrow j = p - i.

[Πράγματι, έστω ότι \displaystyle {i^2} + 1 \equiv {j^2} + 1\left( {\bmod p} \right). Τότε, είναι \displaystyle p|\left( {i - j} \right)\left( {i + j} \right).

Αν \displaystyle i,j \in \left\{ {1,2, \ldots ,\frac{{p - 1}}{2}} \right\}, τότε \displaystyle 0 < i + j < p, οπότε υποχρεωτικά \displaystyle p|i - j και άρα (αφού \displaystyle \left| {i - j} \right| < p), θα είναι i=j.

Αν \displaystyle i,j \in \left\{ {1,2, \ldots ,p - 1} \right\} με \displaystyle i \ne j, τότε υποχρεωτικά \displaystyle p|i + j και άρα \displaystyle p=i + j.]

Από τα παραπάνω προκύπτει ότι \displaystyle \xi  = \prod\limits_{k = 1}^{p - 1} {\left( {{k^2} + 1} \right)}  \equiv {\left( {\prod\limits_{k = 1}^{\frac{{p - 1}}{2}} {\left( {{k^2} + 1} \right)} } \right)^2}\left( {\bmod p} \right).

Θεωρούμε τώρα το πολυώνυμο

\displaystyle f\left( X \right) = \prod\limits_{k = 1}^{\frac{{p - 1}}{2}} {\left( {X - {k^2}} \right) - {X^{\frac{{p - 1}}{2}}}}  + 1

και παρατηρούμε ότι (από το μικρό Θεώρημα του Fermat) είναι \displaystyle f\left( {{k^2}} \right) \equiv 0\left( {\bmod p} \right) για κάθε \displaystyle k \in \left\{ {1,2, \ldots ,\frac{{p - 1}}{2}} \right\}, δηλαδή ότι η ισοτιμία \displaystyle f\left( X \right) \equiv 0\left( {\bmod p} \right) έχει \displaystyle {\frac{{p - 1}}{2} > \deg f} μη ισότιμες \displaystyle {\bmod p} λύσεις. Από το Θεώρημα του Lagrange, έπεται ότι \displaystyle f\left( x \right) \equiv 0\left( {\bmod p} \right) για κάθε x \in \mathbb{Z}. Ειδικότερα, είναι \displaystyle f\left( { - 1} \right) \equiv 0\left( {\bmod p} \right), δηλαδή

\displaystyle {\left( { - 1} \right)^{\frac{{p - 1}}{2}}}\prod\limits_{k = 1}^{\frac{{p - 1}}{2}} {\left( {{k^2} + 1} \right) - {{\left( { - 1} \right)}^{\frac{{p - 1}}{2}}}}  + 1 \equiv 0\left( {\bmod p} \right) \Rightarrow  - \prod\limits_{k = 1}^{\frac{{p - 1}}{2}} {\left( {{k^2} + 1} \right)}  \equiv 2\left( {\bmod p} \right) \Rightarrow

\displaystyle  \Rightarrow {\left( {\prod\limits_{k = 1}^{\frac{{p - 1}}{2}} {\left( {{k^2} + 1} \right)} } \right)^2} \equiv 4\left( {\bmod p} \right)

και άρα στην περίπτωση όπου \displaystyle p \equiv 3\left( {\bmod 4} \right) είναι \displaystyle \xi  \equiv 4\left( {\bmod p} \right).


Βαγγέλης Μουρούκος

Erro ergo sum.
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1405
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Υπόλοιπο διαίρεσης!

#3

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Ιαν 25, 2018 4:54 pm

Εναλλακτικά (για p \geqslant 3):

Αποδεικνύουμε με επαγωγή ότι \displaystyle \sum_{i=1}^{p-1} i^k \equiv 0 \mod p για k = 1, ..., p-2, χρησιμοποιώντας το γεγονός ότι για k=0 η παράσταση ισούται με -1 \mod p και θεωρώντας τα τηλεσκοπικά αθροίσματα \displaystyle \sum_{i=1}^{p-1} \left( (i+1)^k - i^k \right).

Έτσι, από τις ταυτότητες Newton, προκύπτει ότι τα στοιχειώδη συμμετρικά πολυώνυμα βαθμού \displaystyle d = 1,..., \frac{p-3}{2} των \displaystyle \frac{p-1}{2} τετραγωνικών υπολοίπων ως προς p είναι όλα 0.

Οπότε η παράσταση \displaystyle \prod_{k=1}^{p-1} (k^2 + 1) = \left( \prod_{k=1}^{\frac{p-1}{2}} (k^2 + 1) \right)^2 = \left(1 + \prod_{k=1}^{\frac{p-1}{2}} k^2 \right)^2.

Ο δεύτερος όρος είναι -1 για p = 4m+1 και 1 για p = 4m+3, από όπου έπονται τα αποτελέσματα 0 και 4 αντίστοιχα.


Δημήτρης Σκουτέρης

Τα μαθηματικά είναι η μοναδική επιστήμη που θα μπορούσε κανείς να εξακολουθήσει να ασκεί αν κάποτε ξυπνούσε και το σύμπαν δεν υπήρχε πλέον.
ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ
Δημοσιεύσεις: 3228
Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ

Re: Υπόλοιπο διαίρεσης!

#4

Μη αναγνωσμένη δημοσίευση από ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ » Πέμ Ιαν 25, 2018 11:51 pm

matha έγραψε:
Πέμ Ιαν 25, 2018 10:02 am
Ας είναι \displaystyle{p} πρώτος.Θεωρούμε τον αριθμό

\displaystyle{\xi=\prod_{k=1}^{p-1}(k^2+1).}

Να βρεθεί το υπόλοιπο της διαίρεσης \displaystyle{\xi :p.}
Με θεωρία πολυωνύμων(δεν γνωρίζω αν είναι εντός φακέλου)

Δουλεύουμε στο \mathbb{Z}_{p},p\geq 3

Είναι γνωστό ότι x^{p-1}-1=(x-1)(x-2)....(x-(p-1))

οπότε και x^{p-1}-1=(x+1)(x+2)....(x+(p-1))

Πολλαπλασιάζοντας κατά μέλη παίρνουμε

(x^{p-1}-1)^{2}=(x^{2}-1)(x^{2}-2^{2}).....(x^{2}-(p-1)^{2})

Επειδή το p-1 είναι ζυγός προκύπτει ότι (t^{\frac{p-1}{2}}-1)^{2}=(t-1)(t-2^{2})....(t-(p-1)^{2})

Θέτοντας t=-1 στην τελευταία παίρνουμε ότι

το γινόμενο είναι 0 αν p=4k+1

και 4 αν p=4k+3


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8520
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Υπόλοιπο διαίρεσης!

#5

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Ιαν 26, 2018 10:16 am

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ έγραψε:
Πέμ Ιαν 25, 2018 11:51 pm

Με θεωρία πολυωνύμων(δεν γνωρίζω αν είναι εντός φακέλου)
Δεν νομίζω να μπει πρόβλημα που να λύνεται μόνο με τέτοιες μεθόδους αλλά η συγκεκριμένη λύση θα ήταν σίγουρα αποδεκτή.


Άβαταρ μέλους
matha
Γενικός Συντονιστής
Δημοσιεύσεις: 6271
Εγγραφή: Παρ Μάιος 21, 2010 7:40 pm
Τοποθεσία: Θεσσαλονίκη

Re: Υπόλοιπο διαίρεσης!

#6

Μη αναγνωσμένη δημοσίευση από matha » Κυρ Ιαν 28, 2018 7:36 pm

Θεωρούμε το πολυώνυμο

\displaystyle{P(x)=(x+1)(x+2)\cdots (x+p-1).}

Το ζητούμενο βασίζεται στο ότι ισχύει \displaystyle{P(x)=x^{p-1}-1+pQ(x)}, για κάποιο πολυώνυμο \displaystyle{Q(x)\in Z[x].}

Τότε είναι

\displaystyle{\xi =P(i)P(-i)=\left[i^{p-1}-1+pQ(i)\right]\left[(-i)^{p-1}-1+pQ(-i)\right]},

οπότε \displaystyle{\mod p} ισχύει

\displaystyle{\xi =(i^{p-1}-1)((-i)^{p-1}-1)=\begin{cases}4,~~ if ~~p\equiv 3\mod 4, \\ 0, ~~otherwise\end{cases}}


Μάγκος Θάνος
Απάντηση

Επιστροφή σε “Θεωρία Αριθμών - Επίπεδο Αρχιμήδη (Seniors)”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης