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

#1

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

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

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

#2

Αν $\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).$

dement · #3

Εναλλακτικά (για $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}$ τετραγωνικών υπολοίπων ως προς

είναι όλα

.

Οπότε η παράσταση $\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$ .

Ο δεύτερος όρος είναι

για

και

για

, από όπου έπονται τα αποτελέσματα

και

αντίστοιχα.

ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ · #4

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

στην τελευταία παίρνουμε ότι

το γινόμενο είναι

αν

και

αν

#5

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

Με θεωρία πολυωνύμων(δεν γνωρίζω αν είναι εντός φακέλου)

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

#6

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

$\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}}$

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

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

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

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

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

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

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

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