Non ci resta che trovare il resto
Polinomi, disuguaglianze, numeri complessi, ...
- razorbeard
- Messaggi: 123
- Iscritto il: 20 apr 2011, 16:28
Non ci resta che trovare il resto
Messaggio da razorbeard »
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
Re: Non ci resta che trovare il resto
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\]
\[\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$.
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}\]
\[\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$.
Vai a
- Getting Started
- ↳ Comitato di accoglienza nuovi utenti
- ↳ Ciao a tutti, mi presento:
- ↳ Glossario e teoria di base
- Problem solving olimpico
- ↳ Algebra
- ↳ Combinatoria
- ↳ Geometria
- ↳ Teoria dei Numeri
- Altri esercizi
- ↳ Matematica ricreativa
- ↳ Matematica non elementare
- ↳ Fisica
- ↳ Informatica
- Supporto tecnico
- ↳ Il sito delle olimpiadi della matematica
- ↳ LaTeX, questo sconosciuto
- Gare e concorsi
- ↳ Olimpiadi della matematica
- ↳ Gara a squadre
- ↳ Giornalino del gruppo tutor
- ↳ Altre gare
- ↳ Scuole d'eccellenza e borse di studio
- Tra un problema e l'altro...
- ↳ Cultura matematica e scientifica
- ↳ Il colmo per un matematico
- ↳ Discorsi da birreria
- I messaggi del vecchio forum (memoria storica di sola lettura)
- ↳ [vecchio forum]Le olimpiadi della matematica
- ↳ [vecchio forum]Come vedo il sito delle Olimpiadi della Matematica
- ↳ [vecchio forum]Giornalino della Matematica
- ↳ [vecchio forum]Gruppo Tutor
- ↳ [vecchio forum]Proponi gli esercizi
- ↳ [vecchio forum]Compro, baratto, vendo, rido!
- ↳ [vecchio forum]Cesenatico
- ↳ [vecchio forum]Sondaggi, che passione!
- ↳ [vecchio forum]Proposte ai Responsabili Provinciali
- ↳ [vecchio forum]Tra responsabili
- ↳ [vecchio forum]Non solo Matematica!