Heltallene [tex]a_1, \ldots a_n[/tex] har den egenskapen at for et bestemt polynom [tex]P(x)[/tex] med heltallskoeffisienter finnes det for ethvert heltall [tex]c[/tex] et heltall [tex]i[/tex] mellom [tex]1[/tex] og [tex]n[/tex] slik at [tex]a_i[/tex] deler [tex]P(c)[/tex].
Vis at det finnes en [tex]k[/tex] slik at [tex]a_k[/tex] deler [tex]P(x)[/tex] for alle heltall [tex]x[/tex].
Polynom delelig med heltallsmengde
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Uten tap av generalitet er ingen [tex]a_i[/tex] 0. Hvis en av dem er 1 er resultatet opplagt, så vi ser i det følgende kun på det tilfellet der hver [tex]a_i[/tex] er delt av minst ett primtall.
La [tex]A=\{ p_1,p_2,...,p_r \}[/tex] være mengden av alle forskjellige primtall som deler [tex]a_1a_2 \cdots a_n[/tex]. For hver [tex]p_j \in A[/tex], er enten [tex]P(x)[/tex] identisk lik modulo [tex]p_j[/tex], eller så finnes en familie heltallige [tex]x[/tex] slik at [tex]P(x) \equiv m_j \pmod {p_j}[/tex] for en [tex]m_j \not \equiv 0 [/tex]. Hvis [tex]P(x)[/tex] ikke er identisk lik 0 modulo [tex]p_j[/tex] for alle [tex]p_j \in A[/tex], gir det kinesiske restklasseteoremet at det finnes en [tex]x_0[/tex] slik at [tex]P(x_0) \not \equiv 0 \pmod {p_j}[/tex] for alle [tex]p_j \in A[/tex], som gir motsigelse da ingen [tex]a_i[/tex] vil dele [tex]P(x_0)[/tex]. Det må altså finnes [tex]q_1,q_2,...,q_k \in A[/tex] som deler [tex]P(x)[/tex] for alle [tex]x[/tex]. La [tex]w_1,w_2,...,w_{r-k}[/tex] være de (evt.) andre elementene av [tex]A[/tex], dvs de primtallene som ikke deler [tex]P(x)[/tex] for alle [tex]x[/tex].
For [tex]j=1,2,...,k[/tex], definer [tex]e_j=\max \{n \in \mathbb{N}|P(x) \equiv 0 \pmod {q_j^n} \forall x \in \mathbb{Z} \}[/tex]. [tex]q_j^{e_j}[/tex] er altså den maksimale potensen av [tex]q_j[/tex] som deler [tex]P(x)[/tex] for alle [tex]x[/tex]. Det er videre to muligheter. Den ene er at det finnes en [tex]a_i[/tex] som deler [tex]q_1^{e_1}q_2^{e_2} \cdots q_k^{e_k}[/tex], i hvilket tilfelle vi er ferdige. Den andre er at det ikke finnes noen slike. Hver [tex]a_i[/tex] er da en multippel av [tex] q_j^{e_j+1}[/tex] for en [tex]j \in \{1,2,...,k\}[/tex] eller en multippel av en av [tex]w_j[/tex]'ene. Siden det for hver [tex]y \in \{q_1^{e_1+1},q_2^{e_2+1},...,q_k^{e_k+1},w_1,w_2,...,w_{r-k}\}[/tex] finnes en [tex]x[/tex] slik at [tex]P(x) \not \equiv 0 \pmod y[/tex], gir det kinesiske restklasseteoremet som over motsigelse.
Vi konkluderer med at en av [tex]a_i[/tex]'ene må dele [tex]q_1^{e_1}q_2^{e_2} \cdots q_k^{e_k}[/tex], og resultatet følger.
La [tex]A=\{ p_1,p_2,...,p_r \}[/tex] være mengden av alle forskjellige primtall som deler [tex]a_1a_2 \cdots a_n[/tex]. For hver [tex]p_j \in A[/tex], er enten [tex]P(x)[/tex] identisk lik modulo [tex]p_j[/tex], eller så finnes en familie heltallige [tex]x[/tex] slik at [tex]P(x) \equiv m_j \pmod {p_j}[/tex] for en [tex]m_j \not \equiv 0 [/tex]. Hvis [tex]P(x)[/tex] ikke er identisk lik 0 modulo [tex]p_j[/tex] for alle [tex]p_j \in A[/tex], gir det kinesiske restklasseteoremet at det finnes en [tex]x_0[/tex] slik at [tex]P(x_0) \not \equiv 0 \pmod {p_j}[/tex] for alle [tex]p_j \in A[/tex], som gir motsigelse da ingen [tex]a_i[/tex] vil dele [tex]P(x_0)[/tex]. Det må altså finnes [tex]q_1,q_2,...,q_k \in A[/tex] som deler [tex]P(x)[/tex] for alle [tex]x[/tex]. La [tex]w_1,w_2,...,w_{r-k}[/tex] være de (evt.) andre elementene av [tex]A[/tex], dvs de primtallene som ikke deler [tex]P(x)[/tex] for alle [tex]x[/tex].
For [tex]j=1,2,...,k[/tex], definer [tex]e_j=\max \{n \in \mathbb{N}|P(x) \equiv 0 \pmod {q_j^n} \forall x \in \mathbb{Z} \}[/tex]. [tex]q_j^{e_j}[/tex] er altså den maksimale potensen av [tex]q_j[/tex] som deler [tex]P(x)[/tex] for alle [tex]x[/tex]. Det er videre to muligheter. Den ene er at det finnes en [tex]a_i[/tex] som deler [tex]q_1^{e_1}q_2^{e_2} \cdots q_k^{e_k}[/tex], i hvilket tilfelle vi er ferdige. Den andre er at det ikke finnes noen slike. Hver [tex]a_i[/tex] er da en multippel av [tex] q_j^{e_j+1}[/tex] for en [tex]j \in \{1,2,...,k\}[/tex] eller en multippel av en av [tex]w_j[/tex]'ene. Siden det for hver [tex]y \in \{q_1^{e_1+1},q_2^{e_2+1},...,q_k^{e_k+1},w_1,w_2,...,w_{r-k}\}[/tex] finnes en [tex]x[/tex] slik at [tex]P(x) \not \equiv 0 \pmod y[/tex], gir det kinesiske restklasseteoremet som over motsigelse.
Vi konkluderer med at en av [tex]a_i[/tex]'ene må dele [tex]q_1^{e_1}q_2^{e_2} \cdots q_k^{e_k}[/tex], og resultatet følger.