Esercizi sulle congruenze.
Fino ad oggi sono stato abituato ad affrontare congruenze del tipo$x^(2)\equiv 1 \mod{7}$dove, anche se compare il termine x di secondo grado, portando l'1 dall'altra parte e con un certo ragionamento riesco a risolvere la congruenza.
Ma non riesco a risolvere congruenze del tipo$x^2+x+3 \equiv 0 \mod{5}$ poichè non so come discutere quel trinomio di secondo grado.
Qualcuno può darmi una mano e dirmi come posso risolvere le congruenze di quel tipo?
Ma non riesco a risolvere congruenze del tipo$x^2+x+3 \equiv 0 \mod{5}$ poichè non so come discutere quel trinomio di secondo grado.
Qualcuno può darmi una mano e dirmi come posso risolvere le congruenze di quel tipo?
Risposte
Io di solito cerco di ricondurmi a una forma del tipo
$x^2-=b(modn)$
Inoltre, se hai al primo membro una cosa del tipo
Ricordati poi che avendo
$ax^2+bx+c=0$
moltiplicando ambo i membri per 4a e sommando e sottraendo $b^2$ arrivi a
$(2ax-b)^2=b^2-4ac$
Quindi la congruenze diventa
$(2ax-b)^2-=b^2-4ac (modn)$
Ponendo
$2ax-b=y$..
Ciao
$x^2-=b(modn)$
Inoltre, se hai al primo membro una cosa del tipo
Ricordati poi che avendo
$ax^2+bx+c=0$
moltiplicando ambo i membri per 4a e sommando e sottraendo $b^2$ arrivi a
$(2ax-b)^2=b^2-4ac$
Quindi la congruenze diventa
$(2ax-b)^2-=b^2-4ac (modn)$
Ponendo
$2ax-b=y$..
Ciao
Quindi mi stai dicendo che devo effettuare le sostituzioni che mi hai detto, risolvere la congruenza in funzione del parametro $y$, e alla fine sostituire ponendo $y=2ax-b$ ?
$x^2+x+3-=0(mod5)$
Moltiplicando per 4, si avrà
$4x^2+4x+12-=0(mod5)$
$4x^2+4x+1+11-=0(mod5)$
$(2x+1)^2+11-=0(mod5)$
$(2x+1)^2-=-11(mod5)$
$(2x+1)^2-=4(mod5)$
sia
$2x+1=y$
...
Moltiplicando per 4, si avrà
$4x^2+4x+12-=0(mod5)$
$4x^2+4x+1+11-=0(mod5)$
$(2x+1)^2+11-=0(mod5)$
$(2x+1)^2-=-11(mod5)$
$(2x+1)^2-=4(mod5)$
sia
$2x+1=y$
...
In questo caso è sufficiente procedere per tentativi: sostituisci 0,1,2,3,4 e vedi cosa ti restituisce zero.
Grazie mille in un topic mi avete tolto tati dubbi!
p.s. scusate se faccio e spesso farò domande stupide!
p.s. scusate se faccio e spesso farò domande stupide!
Ho ancora dubbi sulla risoluzione delle congruenze...
Come faccio a risolvere una congruenza del tipo $x^30+x+3 \equiv 0 \mod{5}$ ? questa volta il trinomio non è di secondo grado e non posso fare il ragionamento che precedentemente mi avete suggerito, e se provo a fare a tentativi.... con quell'esponente è impossibile.
Grazie ancora per l'aiuto che mi date e che (spero) mi darete.
Come faccio a risolvere una congruenza del tipo $x^30+x+3 \equiv 0 \mod{5}$ ? questa volta il trinomio non è di secondo grado e non posso fare il ragionamento che precedentemente mi avete suggerito, e se provo a fare a tentativi.... con quell'esponente è impossibile.
Grazie ancora per l'aiuto che mi date e che (spero) mi darete.
ciao per ridurre il trinomio di trentesimo grado devi giocherellare un pò con Fermat...Io sono in classe tua, non ho capito perfettamente l'argomento, cmq il prof ha spiegato come ricondurre questa roba a una forma accettabile. Supponendo x diverso da zero (sennò la congruenza è ovviamente "falsa" - a proposito, come si dice in questi casi? falsa, impossibile, non ha soluzione? le sto studiando da poco...) sappiamo dal corollario del piccolo teorema di Fermat che $x^(p-1) \equiv 1 (mod p)$, quindi che $x^4 \equiv 1 (mod 5)$. Essendo $x^30=x^28 * x^2 = x^(4^7) * x^2$, e sfruttando quanto detto prima , il tuo trinomio diventa $x^2 + x + 3 \equiv 0 (mod5)$, e ora è più maneggevole.... cmq secondo me dovremmo dire qualcosa al nostro esercitatore di aritmetica, in modo molto garbato, ovviamente ( 
), riguardo il fatto che spesso va davvero veloce nelle spiegazioni e che oltre la quinta/sesta fila non si sente più niente...non è che così abbiamo proprio una grande preparazione....scusate l'off topic
), riguardo il fatto che spesso va davvero veloce nelle spiegazioni e che oltre la quinta/sesta fila non si sente più niente...non è che così abbiamo proprio una grande preparazione....scusate l'off topic
Puoi vedere facilmente che 0 non è una soluzione, mentre 1 sì.
Ora osservi che $2^4 \equiv 1$ mod 5, quindi $2^{30} = 2^{28} \cdot 2^2 \equiv 2^2=4$ mod 5. Quindi $2^{30}+2+3 \equiv 4$ mod 5, quindi 2 non è soluzione.
Osservi che $3^4 \equiv 1$ mod 5, quindi $3^{30} = 3^{28} \cdot 3^2 \equiv 9 \equiv 4$ mod 5. Quindi $3^{30}+3+3 \equiv 0$ mod 5, quindi 3 è soluzione.
Osservi che $4^2 \equiv 1$ mod 5, quindi $4^{30} = (4^2)^{15} \equiv 1$ mod 5. Quindi $4^{30}+4+3 \equiv 3$ mod 5, quindi 4 non è soluzione.
Ora osservi che $2^4 \equiv 1$ mod 5, quindi $2^{30} = 2^{28} \cdot 2^2 \equiv 2^2=4$ mod 5. Quindi $2^{30}+2+3 \equiv 4$ mod 5, quindi 2 non è soluzione.
Osservi che $3^4 \equiv 1$ mod 5, quindi $3^{30} = 3^{28} \cdot 3^2 \equiv 9 \equiv 4$ mod 5. Quindi $3^{30}+3+3 \equiv 0$ mod 5, quindi 3 è soluzione.
Osservi che $4^2 \equiv 1$ mod 5, quindi $4^{30} = (4^2)^{15} \equiv 1$ mod 5. Quindi $4^{30}+4+3 \equiv 3$ mod 5, quindi 4 non è soluzione.
ci metti un pò più tempo così, martino...
Può darsi, ma a me pare un ragionamento pulito.
Certo che è pulito, anzi sicuramente sarai molto più ferrato di me sull'argomento...solo che con un solo passaggio puoi arrivare al trinomio di secondo grado scritto sopra e da li ricavi in fretta che le soluzioni sono 1 e 3. Almeno così è come il prof ha consigliato di agire
"alvinlee88":
ciao per ridurre il trinomio di trentesimo grado devi giocherellare un pò con Fermat...Io sono in classe tua, non ho capito perfettamente l'argomento, cmq il prof ha spiegato come ricondurre questa roba a una forma accettabile. Supponendo x diverso da zero (sennò la congruenza è ovviamente "falsa" - a proposito, come si dice in questi casi? falsa, impossibile, non ha soluzione? le sto studiando da poco...) sappiamo dal corollario del piccolo teorema di Fermat che $x^(p-1) \equiv 1 (mod p)$, quindi che $x^4 \equiv 1 (mod 5)$. Essendo $x^30=x^28 * x^2 = x^(4^7) * x^2$, e sfruttando quanto detto prima , il tuo trinomio diventa $x^2 + x + 3 \equiv 0 (mod5)$, e ora è più maneggevole.... cmq secondo me dovremmo dire qualcosa al nostro esercitatore di aritmetica, in modo molto garbato, ovviamente (
Avevo capito il teorema di fermat ma mi mancava proprio il passaggio che mi hai detto per ridurla di secondo grado!!!!
**** non so proprio come **** ringraziarti!!!!!!!!!!! Sei un grande!
Certo, è un buonissimo metodo, ma di solito (parlo per me) preferisco ridurmi al più "primordiale possibile", nel senso che voglio usare il meno possibile strumenti relativamente potenti, perché sia più evidente il livello di semplicità della soluzione.
Comincerei a fare considerazioni più generali per esempio nel caso di $x^n+x+3$ (dove bisogna distinguere i casi rispetto a n).
Edito: per inciso (scusate se dico un'ovvietà) i polinomi $x^2+x+3$ e $x^{30}+x+3$ hanno le stesse soluzioni in $F_5$ ma non sono lo stesso polinomio di $F_5[X]$.
Comincerei a fare considerazioni più generali per esempio nel caso di $x^n+x+3$ (dove bisogna distinguere i casi rispetto a n).
Edito: per inciso (scusate se dico un'ovvietà) i polinomi $x^2+x+3$ e $x^{30}+x+3$ hanno le stesse soluzioni in $F_5$ ma non sono lo stesso polinomio di $F_5[X]$.
certamente ma quando dici " osservi che $2^4 \equiv 1 (mod 5)$ ecc. " in sostanza applichi il teorema, riferito solo al caso particolare invece che al generale. Essendo quindi abbastanza primordiale come ragionamento, non vedo perchè non generalizzare col teorema...Se il modulo era 11 che facevi, ti calcolavi $2^10$ e guardavi a cosa era conguro modulo 11? mi sembra piuttosto casinoso..
Ehi ehi, non sto dicendo che ho ragione, sto solo dicendo che io farei in un altro modo.
Se dovendolo discutere "modulo 2003" mi sarà venuta voglia di passare la giornata a discutere ogni singolo caso, allora forse mi accorgerò che esiste un metodo enormemente più veloce... Ma non mi sembra che la mia (discutibile) preferenza nel caso "modulo 5" denoti una qualche mia colpa o mancanza
Ciao.
Se dovendolo discutere "modulo 2003" mi sarà venuta voglia di passare la giornata a discutere ogni singolo caso, allora forse mi accorgerò che esiste un metodo enormemente più veloce... Ma non mi sembra che la mia (discutibile) preferenza nel caso "modulo 5" denoti una qualche mia colpa o mancanza
Ciao.
ci mancherebbe!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo