Subject: Congruenze

Sto preparando il maledettissimo esame di discreta e sto impazzendo dietro alle congruenze non lineari. Il prof. non tratta nelle sue dispense l'argomento, ma me lo sono ritrovato al primo appello estivo. Ho cercato un po' in giro ed il metodo più immediato trovato finora è il seguente.

Prendo la mia congruenza f(x) == 0 (mod m). Se non è primo, fattorizzo m nei suoi fattori primi e metto a sistema tutte le congruenze f(x) == 0 mod (p_i), dove p_i è l'i-esimo fattore primo. Ricavo le soluzioni e costruisco n sistemi con congruenze nella forma x == s_k (mod p_i) (con s_k k-esima soluzione) per tutte le n-uple soluzioni possibili e risolvo nuovamente ottenendo le n soluzioni della congruenza iniziale.

Passo ad un esempio:

x^2 + 3x + 2 == 0 (105)

105=3*5*7, quindi creo un sistema a 3 congruenze. Nello specifico:

- x^2 -1 == 0 (3)
- x^2 +3x + 2 == 0 (5)
- x^2 +3x + 2 == 0 (7)

Sappiamo che essendo il modulo un numero primo, ciascuna congruenza avrà alpiù n soluzioni pari al grado del polinomio. Per trovare le soluzioni sostituisco ad x i valori da 0 a p-1, controllando che siano congrui a 0 (in tal caso sono soluzione). Dovrei rispettivamente controllare i valori 0, 1,2 per la prima, 0,1,2,3,4 per la seconda e 0,1,2,3,4,5,6 per la terza. Per semplificare i calcoli posso far variare x da -p/2 a p/2, cioè -1,0,1 per la prima, -2,-1,0,1,2 per la seconda (si noti che -2 e -1 sono rispettivamente congrui a 3 e 4), -3,-2,-1,0,1,2,3 per la terza.

Sostituendo ottengo le seguenti soluzioni:

- x = -1, x = 1
- x = -1, x = -2
- x = -1, x = -2

ora dovrei costruire 8 sistemi per ciascuna delle triple possibili. Non proprio agevole. Basta che il modulo della congruenza iniziale si fattorizzi in più di 2 numeri primi perché con buone probabilità inizi a diventare impensabile rimettere insieme le soluzioni parziali trovate, senza contare che sostituire tutti i possibili valori di resto ad x per trovare le soluzioni è fattibile quando non si ha a che fare con numeri primi piuttosto grossi.

Insomma ho questo duplice problema. Qualcuno mi sa aiutare? Tenete anche conto che non ci è permesso, per un qualche morboso motivo, utilizzare la calcolatrice all'esame.

nessuno?

nobody

la risolvo anche, ma sono 8 sistemi...e potrebbe essere di gran lunga peggio!

Ho provato a guardare se aull'Algebretta che avevo usato per studiare le congruenze all'università 20 anni fa mi diceva qualcosa, ma non c'è gran che in proposito e non ho sottomano i vecchi appunti.

Ad ogni modo, il fatto che il tuo polinomio si scomponga come (x+1)(x+2) non ti è di aiuto per niente? Così diventa
(x+1)(x+2) == 0 (105)

Cha ha come ovvie soluzioni -1 cioè 104, e -2 cioè 103. Così ad occhio mi verrebbe da dire che le classi di congruenza [-1] e [-2] siano tutte e sole le soluzioni di questa congruenza, che tradotto in numeri interi sono tutti i numeri delle due seguenti forme:
x1=-1+k*105
x2= -2 + k*105

Dici che l'ho fatta troppo facile?....scusami ma dopo 20 anni ce le ho un po' arrugginite!

tutto giusto, se non fosse che quelle sono solo 2 delle 7 soluzioni finali. Una congruenza nella forma:

f(x) == 0 (p)

con p numero primo ha alpiù n soluzioni, dove n è il grado del polinomio. 105 si fattorizza in 3*5*7, quindi ha alpiù 8 soluzioni (2^3). Le 3 congruenze del sistema (si veda il post iniziale) hanno, in questo caso, 2 soluzioni ciascuna. Ogni sistema di triple (formato dalle soluzioni parziali trovate) contribuirà con 1 soluzione della congruenza iniziale (poiché l'MCD dei moduli, essendo questi numeri primi, sarà sempre = 1, quindi il singolo sistema avrà sempre e solo 1 soluzione). Risolvendo si ottengono tutte le 7 soluzioni (non 8 perché 2 sistemi davano soluzione -1).

In particolare tali soluzioni sono: -1, -2 (le radici che annullano il polinomio), 13, 19, -16, -22 e -37. Il problema è che risolvere ciascuna sistema è una sfacchinata non da poco. Immagina un polinomio di grado superiore al 2 ed un modulo con parecchi fattori primi...

immagino....due palle! suppongo che tu non sia iscritto alla facoltà di matematica (quella che ho fatto io) perchè noi raramente facevamo robe così "laboriose"

no, informatica

allora mi torna, voi dovete imparare ad insegnare al computer come fare certi calcoli: se a risolvere gli 8 sistemi è un computer su tue indicazioni allora il problema non si pone più.

Comunque me lo fossi ritrovato io di fronte in uno scritto l'avrei risolto scomponendo in fattori come ho detto e quindi cercando tra tutti i multipli di 7 tra 0 e 104 quelli che moltiplicati per il numero successivo contengono come fattori anche il 3 ed il 5. Non sarebbe così laborioso (indico :

[0] va bene quindi [-1] è soluzione
[7] non va bene perchè [8] non è multiplo di 3 e 5
[14] va bene perchè 15 è 3*5 quindi [13] è soluzione

Queto suggerisce al volo che siccome o il numero considerato o il suo successivo deve esser multiplo di cinque, idem si ragiona per il 3, scartiamo a piè pari un sacco di numeri, quindi:

[21] va bene perchè 20 è multiplo di 5, quindi [19] è soluzione

[28] lo scartiamo
[35] va bene perchè contiene come fattori 7 e 5 e il suo successivo è il 36 che contiene il 3, quindi [34] è un'altra soluzion.
[42] lo scartiamo
[49] lo scartiamo perchè ne lui ne il successivo son multipli di 3
[56] lo scartiamo
[63] lo scartiamo
[70] va bene perchè multiplo di 5 e 71 è multiplo di 3, quindi [69] è soluzione
[77] lo scartiamo
[84] va bene perchè multiplo di 3 e 85 è multiplo di 5, per cui [83] è soluzione
[91] va bene quindi [89] è soluzione
[98] lo scartiamo

Fine.

Ora, a mente lucida e non con il sonno di ieri sera a pensare questa soluzione ci ho messo pochi minuti 5 o 6 minuti a scriverla. Però capisco che potrebbe diventare impraticabile nel caso di una congruenza modulo un numero troppo grosso e fattorizzabile in numeri primi troppo piccoli perchè bisognerebbe analizzare troppi casi uno ad uno. Inoltre potrebbe non capitarti un polinomio cosè facilmente scomponibile.

Però, potrebbe anche essere che si aspettino che tu risolva il problema normalmente con metodi tipo quello che hai detto ma che in alcuni casi sia ammesso, e magari lo apprezzano, utilizzare scorciatoie come quella che ti ho indicato io.

p.s.: non ho ricontrollato, quindi non garantisco di non aver sbagliato nessun conto.
(edited)

ovviamente il mio [89] è il tuo [-16], ah uso le parentesi quadrate perchè sono abitutato a rappresentare così le classi di congruenza per distinguerle dai numeri interi

allora mi torna, voi dovete imparare ad insegnare al computer come fare certi calcoli: se a risolvere gli 8 sistemi è un computer su tue indicazioni allora il problema non si pone più.

ahahahahah, no no. Dobbiamo fare i calcoli a mano, non ci fanno usare nemmeno la calcolatrice :D

Comunque non ho capito il tuo ragionamento (in riferimento al numero successivo che deve essere multiplo e quello precedente). Me lo spiegheresti meglio? Mi pare che sia molto più rapido.

Visto che il polinomio si scompone in (x+1)(x+2) la congruenza diventa
(x+1)(x+2)==0 (mod 105)

Ora siccome x+2 è il numero successivo ad x+1 il problema si riduce a trovare due numeri che moltiplicati tra loro siano multipli di 105 e che siano uno il successivo dell'altro. Poi una volta trovati x+1 o x+2 si ricava x di conseguenza.

Se vuoi poi pensarlo facendo una sosituzion chiami n=x+1 quidni ti diventaù
n(n+1) == 0 mod 105

Quando si ha robe congrua a 0 modulo qualcosa, è spesso conveniente raguonare in termini di fattorizzazione.

In quasto caso, tra tutte le 105 classi di congruenza che ci interessano si guardano quelle che moltiplicate per la successiva diano 0, ovvero siano multiple di 105, ma siccome per essere multiplo di 105 devi contenere come fattori il 3 il 5 ed il 7, si può velocizzare la procedura scorrendo tutti i multipli di 7 e guardare se moltiplicati per il precedente o il successivo numero non vadano a contenere anche i fattori 3 e 5.

tutto chiaro, grazie ;)

ahahahahah, no no. Dobbiamo fare i calcoli a mano, non ci fanno usare nemmeno la calcolatrice :D

Ora, ma "da grande" non li farai a mano, ma sapendoli fare a mano potrai farli fare ad un computer :)