Non ci resta che trovare il resto

Polinomi, disuguaglianze, numeri complessi, ...
Rispondi
Avatar utente
razorbeard
Messaggi: 123
Iscritto il: 20 apr 2011, 16:28

Non ci resta che trovare il resto

Messaggio da razorbeard » 30 nov 2020, 11:36

Sia $p(x)=x^5+2x^4+3x^3+4x^2+5x+6$. Determinare il resto di $p(1)-p(2)+p(3)-p(4)+...-p(2018)+p(2019)$ diviso per 1010.
E' un buon giorno... per morire

kart
Messaggi: 7
Iscritto il: 31 mar 2020, 09:05

Re: Non ci resta che trovare il resto

Messaggio da kart » 05 dic 2020, 21:34

Testo nascosto:
Lemma
Sia $f(x)$ un polinomio di grado $d$ e sia $p$ primo. Se $d<p-1$, allora $\displaystyle\sum_{x=0}^{p-1} f(x) \equiv 0 \pmod{p}$.
Dimostrazione
Sia $f(x)=a_d x^d+\dots+a_1 x+a_0$ e sia $g$ generatore modulo $p$. Consideriamo un generico termine $a_m x^m$ con $0<m\leq d$
\[ \sum_{x=0}^{p-1} a_m x^m \equiv a_m \sum_{x=1}^{p-1} x^m \equiv a_m \sum_{k=0}^{p-2} (g^k)^m \equiv a_m \sum_{k=0}^{p-2} (g^m)^k
\equiv a_m \frac{(g^m)^{p-1} -1}{g^m-1} \equiv 0 \pmod{p}\]
Infatti, essendo $0<m\leq d<p-1$, si ha $g^m\not\equiv 1 \pmod{p}$ poiché $g$ è generatore e $(g^m)^{p-1}\equiv 1 \pmod{p}$ per il piccolo teorema di Fermat. Quindi
\[\sum_{x=0}^{p-1} f(x) \equiv \sum_{x=0}^{p-1} \left( a_0+\sum_{k=1}^d a_k x^k \right) \equiv \sum_{x=0}^{p-1} a_0 + \sum_{k=1}^d \left( \sum_{x=0}^{p-1} a_k x^k \right) \equiv a_0p+0 \equiv 0 \pmod{p} \;\;\;\;\;\;\Box \]

Abbiamo che $1010=2\cdot5\cdot101$, quindi analizziamo il resto modulo questi primi.
\[r := p(1)-p(2)+p(3)-p(4)+\dots-p(2018)+p(2019) = 6+\sum_{x=0}^{1009} \left( p(2x+1)-p(2x)\right) \\ p(x)=x^5+2x^4+3x^3+4x^2+5x+6\]
  • $\pmod{2}$
    Per il piccolo teorema di Fermat abbiamo che $x^2\equiv x\pmod{2}$
    \[p(x)\equiv x^5+x^3+x \equiv x+x+x \equiv 3x \equiv x \pmod{2} \\ \implies p(2x+1)-p(2x) \equiv 1-0 \equiv 1 \pmod{2} \\
    \implies r \equiv 6+\sum_{x=0}^{1009} 1 \equiv 6+1010 \equiv 0 \pmod{2}\]
  • $\pmod{5}$
    Per il piccolo teorema di Fermat abbiamo che $x^5\equiv x\pmod{5}$
    \[p(x)\equiv 2x^4+3x^3+4x^2+x+1 \pmod{5}\]
    Applicando il Lemma sui termini di grado $<4$ e usando il piccolo teroema di Fermat (se $5\nmid a$, allora $a^4\equiv 1 \bmod{5}$) si ottiene
    \[ \sum_{x=0}^{1009} p(2x+1) \equiv 202 \sum_{x=0}^{4} p(2x+1) \equiv 202 \left( 0 + \sum_{x=0}^4 2(2x+1)^4 \right) \equiv 4\sum_{x=0}^4 16x^4 \equiv 4\sum_{x=1}^4 x^4 \equiv 4\cdot4 \equiv 1 \pmod{5}
    \\ \sum_{x=0}^{1009} p(2x) \equiv 202 \sum_{x=0}^{4} p(2x) \equiv 202 \left( 0 + \sum_{x=0}^4 2(2x)^4 \right) \equiv 4\sum_{x=0}^4 16x^4 \equiv 4\sum_{x=1}^4 x^4 \equiv 4\cdot4 \equiv 1 \pmod{5} \]
    \[\implies r \equiv 6+1-1 \equiv 1 \pmod{5}\]
  • $\pmod{101}$
    Applicando il Lemma su $(p(2x+1)-p(2x))$ abbiamo che
    \[ \sum_{x=0}^{1009} \left( p(2x+1)-p(2x)\right) \equiv 10\sum_{x=0}^{100} \left( p(2x+1)-p(2x)\right) \equiv 0 \pmod{101}\]
    \[\implies r \equiv 6+0 \equiv 6 \pmod{101}\]
Ora per il teorema cinese possiamo risalire al resto della divisione per $1010$
\[\begin{cases} r \equiv 0 \pmod{2} \\ r \equiv 1 \pmod{5} \\ r \equiv 6 \pmod{101}\end{cases}\]
Dalla prima equazione ricaviamo $r=2h_1$, sostituendo nella seconda otteniamo
\[2h_1 \equiv 1 \pmod{5} \implies h_1 \equiv 3 \pmod{5} \implies h_1 = 5h_2+3 \implies r = 10h_2+6\]
Sostituendo nella terza si ottiene
\[10h_2+6 \equiv 6 \pmod{101} \implies 10h_2 \equiv 0 \pmod{101} \implies h_2 \equiv 0 \pmod{101} \\ \implies h_2=101h_3 \implies r = 1010h_3+6\]
Essendo $r$ il resto della divisione per $1010$, si ha $0\leq r<1010$, quindi $r=6$.

Rispondi