Problemi con le congruenze e i numeri primi
Salve a tutti,
propongo due problemi che non riesco a risolvere:
1) dato il polinomio $n^2+n+41$, questo, sostituendo a n i primi 39 numeri naturali, genera solo primi. Naturalmente è possibile dimostrarlo provandoli tutti con le congruenze, ma c'è un modo più elegante e generale? Ho notato che funziona anche con alcuni numeri congrui a uno modulo 4 come il 17 o il 13.
2) Il secondo problema recita: Dimostrare che il polinomio $x^4-10x^2+1$ è irriducibile su Z (e per questo non c'è problema), mentre è riducibile con Z/p, per ogni p primo.
Ho provato in vari modi, quello che mi sembra migliore è l'induzione notando che per ogni primo p vale che p+1 è congruo a 1 modulo p. Quindi otterrei:
Base induttiva $x^4=-1$ modulo 2 ==> vero
Lo ipotizzerei vero per p e lo dimostrerei per p+1, per non ho ben chiaro cosa fare nè se si possano usare i primi come indici d'induzione.
Grazie
propongo due problemi che non riesco a risolvere:
1) dato il polinomio $n^2+n+41$, questo, sostituendo a n i primi 39 numeri naturali, genera solo primi. Naturalmente è possibile dimostrarlo provandoli tutti con le congruenze, ma c'è un modo più elegante e generale? Ho notato che funziona anche con alcuni numeri congrui a uno modulo 4 come il 17 o il 13.
2) Il secondo problema recita: Dimostrare che il polinomio $x^4-10x^2+1$ è irriducibile su Z (e per questo non c'è problema), mentre è riducibile con Z/p, per ogni p primo.
Ho provato in vari modi, quello che mi sembra migliore è l'induzione notando che per ogni primo p vale che p+1 è congruo a 1 modulo p. Quindi otterrei:
Base induttiva $x^4=-1$ modulo 2 ==> vero
Lo ipotizzerei vero per p e lo dimostrerei per p+1, per non ho ben chiaro cosa fare nè se si possano usare i primi come indici d'induzione.
Grazie
Risposte
Ciao!
Mi sembra che hai le idee non troppo chiare sul procedimento per induzione. Puoi procedere per induzione quando conosci la sequenza di numeri per cui vuoi provare una certa proposizione. I numeri primi formano una sequenza ancora sconosciuta, quindi non riesci a procedere per induzione in questo caso.
1) Non c'è un metodo più elegante di verificare tutto a mano.
2) Non si può procedere per induzione. Se p>2 è primo allora p+1 non è primo. Vale quanto dicevo sopra. Sinceramente non so come si risolva il problema di cui parli, ma probabilmente c'entrano il simbolo di Legendre (se il discriminante del tuo polinomio è un quadrato perfetto sei a posto) e il gruppo di Galois di quel polinomio. Ci penso perché mi interessa!
Mi sembra che hai le idee non troppo chiare sul procedimento per induzione. Puoi procedere per induzione quando conosci la sequenza di numeri per cui vuoi provare una certa proposizione. I numeri primi formano una sequenza ancora sconosciuta, quindi non riesci a procedere per induzione in questo caso.
1) Non c'è un metodo più elegante di verificare tutto a mano.
2) Non si può procedere per induzione. Se p>2 è primo allora p+1 non è primo. Vale quanto dicevo sopra. Sinceramente non so come si risolva il problema di cui parli, ma probabilmente c'entrano il simbolo di Legendre (se il discriminante del tuo polinomio è un quadrato perfetto sei a posto) e il gruppo di Galois di quel polinomio. Ci penso perché mi interessa!
"UgoFoscolo90":Credo che questo sia equivalente a dire che il gruppo di Galois di $x^4-10x^2+1$ non contiene 4-cicli. -ma devo convincermene meglio!-
Dimostrare che il polinomio $x^4-10x^2+1$ [...] è riducibile con Z/p, per ogni p primo.
In questo caso è vero dato che il gruppo di Galois è $A_4$. [Edit: mi sono sbagliato, il gruppo di Galois è il gruppo di Klein $V cong C_2 xx C_2$, che comunque non contiene 4-cicli.]
Interessante! Con un pochi di passaggi otteniamo:
[tex]\displaystyle x^4-10x^2+1 \equiv (x^2-5)^2 - 24 (mod p)[/tex]
Ora valutiamo se [tex]24[/tex] è un quadrato mediante Legendre:
$(\frac{24}{p})=(\frac{3}{p})(\frac{8}{p})=(\frac{3}{p})(\frac{2}{p})$
Da qui mediante il teorema di reciprocità ho che:
$(\frac{2}{p})={(1 \text{ if } p\equiv 1 \text{ or } 7 (mod8)), (-1 \text{ if } p\equiv 3 \text{ or } 5 (mod8)):}$
$(\frac{3}{p})={(1 \text{ if } p\equiv 1 \text{ or } 11 (mod12)), (-1 \text{ if } p\equiv 5 \text{ or } 7 (mod12)):}$
nei casi sopra esposti ho allora che esiste [tex]\alpha_0[/tex] tale che:
[tex](\alpha_0)^2\equiv (x^2-5)^2 (mod p)[/tex]
e dunque:
[tex](\alpha_0)^2\equiv (x^2-5)^2 (mod p)[/tex]
[tex]\alpha_0 \equiv x^2-5 (mod p)[/tex]
ed anche:
[tex]-\alpha_0 \equiv x^2-5 (mod p)[/tex]
qui sarebbe da stabilire se:
[tex]x^2 \equiv 5+-\alpha_0 (mod p)[/tex]
abbia soluzione, ma qui la via pare chiusa... non sapendo chi sia effettivamente [tex]\alpha_0[/tex]. Parallelamente al lavoro di gruppi di Martino, penso che proverò a trovare una via anche in maniera numerica, anche se non pare semplicissimo...
[tex]\displaystyle x^4-10x^2+1 \equiv (x^2-5)^2 - 24 (mod p)[/tex]
Ora valutiamo se [tex]24[/tex] è un quadrato mediante Legendre:
$(\frac{24}{p})=(\frac{3}{p})(\frac{8}{p})=(\frac{3}{p})(\frac{2}{p})$
Da qui mediante il teorema di reciprocità ho che:
$(\frac{2}{p})={(1 \text{ if } p\equiv 1 \text{ or } 7 (mod8)), (-1 \text{ if } p\equiv 3 \text{ or } 5 (mod8)):}$
$(\frac{3}{p})={(1 \text{ if } p\equiv 1 \text{ or } 11 (mod12)), (-1 \text{ if } p\equiv 5 \text{ or } 7 (mod12)):}$
nei casi sopra esposti ho allora che esiste [tex]\alpha_0[/tex] tale che:
[tex](\alpha_0)^2\equiv (x^2-5)^2 (mod p)[/tex]
e dunque:
[tex](\alpha_0)^2\equiv (x^2-5)^2 (mod p)[/tex]
[tex]\alpha_0 \equiv x^2-5 (mod p)[/tex]
ed anche:
[tex]-\alpha_0 \equiv x^2-5 (mod p)[/tex]
qui sarebbe da stabilire se:
[tex]x^2 \equiv 5+-\alpha_0 (mod p)[/tex]
abbia soluzione, ma qui la via pare chiusa... non sapendo chi sia effettivamente [tex]\alpha_0[/tex]. Parallelamente al lavoro di gruppi di Martino, penso che proverò a trovare una via anche in maniera numerica, anche se non pare semplicissimo...
Idea istantanea, ma non necessariamente corretta... consideriamo [tex]\sqrt{.}[/tex] la radice quadrata discreta, ovvero [tex]\sqrt{2}[/tex] per esempio è una classe [tex](mod p)[/tex] tale che il suo quadrato (se esiste) è [tex]2[/tex].
[tex]\displaystyle x^4-10x^2+1 = (x^2 + 5+\sqrt{24})(x^2+5-\sqrt{24}) = [x+(\sqrt3 + \sqrt2)][x-(\sqrt3 + \sqrt2)][x+ (\sqrt3-\sqrt2)][x- (\sqrt3-\sqrt2)][/tex]
Allora il nostro problema è trovare le due radici discrete di [tex]3[/tex] e [tex]2[/tex].
P.S. ovvio che questo discorso vale solo se il polinomio si spezza in polinomi di grado 1.
[tex]\displaystyle x^4-10x^2+1 = (x^2 + 5+\sqrt{24})(x^2+5-\sqrt{24}) = [x+(\sqrt3 + \sqrt2)][x-(\sqrt3 + \sqrt2)][x+ (\sqrt3-\sqrt2)][x- (\sqrt3-\sqrt2)][/tex]
Allora il nostro problema è trovare le due radici discrete di [tex]3[/tex] e [tex]2[/tex].
P.S. ovvio che questo discorso vale solo se il polinomio si spezza in polinomi di grado 1.
Se 24 è un quadrato mod p allora il polinomio è riducibile mod p.
Rimane da controllare cosa succede quando 24 non è un quadrato. Il problema è che se c'è uno zero mod p allora 24 è un quadrato mod p, quindi per i primi p per cui 24 non è un quadrato la fattorizzazione in irriducibili consiste di due polinomi di grado 2 ma non proviene dal prodotto notevole.
Tra l'altro mi sono sbagliato, il gruppo di Galois non è $A_4$ ma il gruppo di Klein $V \cong C_2 xx C_2$. Questo implica tra l'altro che per ogni primo p il polinomio si spezza in 4 fattori di grado 1 oppure in 2 fattori irriducibili di grado 2 (corrispondentemente alle strutture cicliche degli elementi del gruppo di Galois).
Rimane da controllare cosa succede quando 24 non è un quadrato. Il problema è che se c'è uno zero mod p allora 24 è un quadrato mod p, quindi per i primi p per cui 24 non è un quadrato la fattorizzazione in irriducibili consiste di due polinomi di grado 2 ma non proviene dal prodotto notevole.
Tra l'altro mi sono sbagliato, il gruppo di Galois non è $A_4$ ma il gruppo di Klein $V \cong C_2 xx C_2$. Questo implica tra l'altro che per ogni primo p il polinomio si spezza in 4 fattori di grado 1 oppure in 2 fattori irriducibili di grado 2 (corrispondentemente alle strutture cicliche degli elementi del gruppo di Galois).
Aspetta, ma se questo polinomio dovesse potersi scomporre in due di grado due, sarebbe a dire che il polinomio:
$t^2-10t+1=f(t)$
ha due radici in $ZZ_p$, ovvero che esiste la radice di $24$... o sbaglio?
$t^2-10t+1=f(t)$
ha due radici in $ZZ_p$, ovvero che esiste la radice di $24$... o sbaglio?
Non capisco cosa vuoi dire, comunque prendi $p=7$. In questo caso $24=3$ non è un quadrato ma il polinomio si scompone:
[tex]x^4-10x^2+1 = (x^2+x-1)(x^2-x-1)[/tex].
[tex]x^4-10x^2+1 = (x^2+x-1)(x^2-x-1)[/tex].
(il mio precedente post era errato)
L'unica possibile scomposizione allora deve essere del tipo (tutti i conti in [tex]\mathbb Z_p[/tex]):
[tex]x^4-10x^2+1 = (x^2+\alpha_0x+\beta_0)(x^2+\alpha_1x+\beta_1)=x^4+x^3(\alpha_0+\alpha_1)+x^2(\beta_1+\alpha_0\alpha_1+\beta_0)+x(\alpha_0\beta_1+\alpha_1\beta_0)+\beta_0\beta_1[/tex]
da cui:
${(\alpha_0+\alpha_1=0),(\beta_1+\alpha_0\alpha_1+\beta_0=-10),(\alpha_0\beta_1+\alpha_1\beta_0=0),(\beta_0\beta_1=1):}$
allora dalla prima [tex]\alpha_0=-\alpha_1[/tex] e dall'ultima [tex]\beta_0=\beta_1^{-1}[/tex] sostituiamo nella terza:
[tex]\alpha_0\beta_1+\alpha_1\beta_0 = \alpha_1(-\beta_1+\beta_0) = 0[/tex]
Ovvero [tex]\alpha_1=0[/tex] oppure [tex]\beta_1=\beta_0[/tex]!!!
Se [tex]\alpha_1=0=\alpha_0[/tex], allora ci interessano i primi [tex]p[/tex] dove [tex]\beta_1=-5[/tex] (dalla seconda equazione) e tale che [tex]25\equiv 1 (mod p)[/tex] ovvero [tex]p=2,3[/tex]
Sia, invece, [tex]\beta_1=\beta_0[/tex], il sistema si riduce a:
${(\alpha_0=-\alpha_1),(2\beta_1-\alpha_1^2=-10),(\beta_1=\beta_0),(\beta_0=\beta_1^(-1)):}$
Ovvero ci interessano le soluzioni del problema:
[tex]x^2 \equiv 1 (modp)[/tex]
una volta trovato l'insieme [tex]S=\{x \in \mathbb Z_p: x^2 \equiv 1 (mod p)\}[/tex] (non vuoto perchè [tex]1 \in S[/tex]) ci interessa trovare le soluzioni di:
[tex]y^2 \equiv 2x+10 (modp)[/tex]
con [tex]x \in S[/tex]. Ovvero se è sempre:
[tex]\diplaystyle (\frac{2x+10}{p})=(\frac{x+5}{p})(\frac{2}{p})=1[/tex]
simboli di Legendre. Per esempio siccome [tex]-1 \in S[/tex] allora:
[tex]y^2 \equiv -2+10 \equiv 8(modp)[/tex]
implica che deve essere:
[tex]\diplaystyle (\frac{2}{p})=1[/tex]
ed anche [tex]1 \in S[/tex] allora:
[tex]y^2 \equiv 2+10 \equiv 12(modp)[/tex]
implica che deve essere:
[tex]\diplaystyle (\frac{12}{p})=(\frac{3}{p})=1[/tex]
Per questo comincio a non essere concorde che quel polinomio si spezza sempre...
L'unica possibile scomposizione allora deve essere del tipo (tutti i conti in [tex]\mathbb Z_p[/tex]):
[tex]x^4-10x^2+1 = (x^2+\alpha_0x+\beta_0)(x^2+\alpha_1x+\beta_1)=x^4+x^3(\alpha_0+\alpha_1)+x^2(\beta_1+\alpha_0\alpha_1+\beta_0)+x(\alpha_0\beta_1+\alpha_1\beta_0)+\beta_0\beta_1[/tex]
da cui:
${(\alpha_0+\alpha_1=0),(\beta_1+\alpha_0\alpha_1+\beta_0=-10),(\alpha_0\beta_1+\alpha_1\beta_0=0),(\beta_0\beta_1=1):}$
allora dalla prima [tex]\alpha_0=-\alpha_1[/tex] e dall'ultima [tex]\beta_0=\beta_1^{-1}[/tex] sostituiamo nella terza:
[tex]\alpha_0\beta_1+\alpha_1\beta_0 = \alpha_1(-\beta_1+\beta_0) = 0[/tex]
Ovvero [tex]\alpha_1=0[/tex] oppure [tex]\beta_1=\beta_0[/tex]!!!
Se [tex]\alpha_1=0=\alpha_0[/tex], allora ci interessano i primi [tex]p[/tex] dove [tex]\beta_1=-5[/tex] (dalla seconda equazione) e tale che [tex]25\equiv 1 (mod p)[/tex] ovvero [tex]p=2,3[/tex]
Sia, invece, [tex]\beta_1=\beta_0[/tex], il sistema si riduce a:
${(\alpha_0=-\alpha_1),(2\beta_1-\alpha_1^2=-10),(\beta_1=\beta_0),(\beta_0=\beta_1^(-1)):}$
Ovvero ci interessano le soluzioni del problema:
[tex]x^2 \equiv 1 (modp)[/tex]
una volta trovato l'insieme [tex]S=\{x \in \mathbb Z_p: x^2 \equiv 1 (mod p)\}[/tex] (non vuoto perchè [tex]1 \in S[/tex]) ci interessa trovare le soluzioni di:
[tex]y^2 \equiv 2x+10 (modp)[/tex]
con [tex]x \in S[/tex]. Ovvero se è sempre:
[tex]\diplaystyle (\frac{2x+10}{p})=(\frac{x+5}{p})(\frac{2}{p})=1[/tex]
simboli di Legendre. Per esempio siccome [tex]-1 \in S[/tex] allora:
[tex]y^2 \equiv -2+10 \equiv 8(modp)[/tex]
implica che deve essere:
[tex]\diplaystyle (\frac{2}{p})=1[/tex]
ed anche [tex]1 \in S[/tex] allora:
[tex]y^2 \equiv 2+10 \equiv 12(modp)[/tex]
implica che deve essere:
[tex]\diplaystyle (\frac{12}{p})=(\frac{3}{p})=1[/tex]
Per questo comincio a non essere concorde che quel polinomio si spezza sempre...
Se [tex]\alpha_1=0=\alpha_0[/tex], allora ci interessano i primi [tex]p[/tex] dove [tex]\beta_1=-5[/tex] (dalla seconda equazione) e tale che [tex]25\equiv 1 (mod p)[/tex] ovvero [tex]p=2,3[/tex]Se $alpha_1=alpha_0=0$ può essere $beta_0 ne beta_1$, quindi quello che dici non è giusto. Esiste una fattorizzazione con $alpha_1=alpha_0=0$ se e solo se 6 è un quadrato.
ci interessano le soluzioni del problema:Le soluzioni di questo problema sono sempre solo 1 e -1. Quindi il tuo insieme S è ${1,-1}$.
[tex]x^2 \equiv 1 (modp)[/tex]
Per esempio siccome [tex]-1 \in S[/tex] allora:Invece quello che hai scritto dimostra proprio che il polinomio si spezza sempre: infatti se almeno uno tra 2 e 3 è un quadrato allora il polinomio si spezza (scegli $beta_0=1$ se 3 è un quadrato, scegli $beta_0=-1$ se 2 è un quadrato), e se 2 e 3 non sono quadrati allora 6 è un quadrato (cioè 24 è un quadrato) e ricadiamo nel caso già discusso.
[tex]y^2 \equiv -2+10 \equiv 8(modp)[/tex]
implica che deve essere:
[tex]\diplaystyle (\frac{2}{p})=1[/tex]
ed anche [tex]1 \in S[/tex] allora:
[tex]y^2 \equiv 2+10 \equiv 12(modp)[/tex]
implica che deve essere:
[tex]\diplaystyle (\frac{12}{p})=(\frac{3}{p})=1[/tex]
Per questo comincio a non essere concorde che quel polinomio si spezza sempre...
Grazie per la correzione
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo