Hot-News.it

il portale hot con notizie da tutto il mondo!

Scegli Lingua : Hot-News.it in italiano Hot-News.it in inglese Hot-News.it in spagnolo Hot-News.it in francese Hot-News.it in tedesco Hot-News.it in giapponese Hot-News.it in arabo
Login With Facebook
Martedi
Nov 19
Messaggio
Hot-News.it Merlino's Science News CONGRUENZA DI PRIMO GRADO Ax ≡ B modulo N
21
Mar
2014

CONGRUENZA DI PRIMO GRADO Ax ≡ B modulo N




Per chi non avesse dimestichezza con le congruenze, consigliamo di leggere prima questo articolo:http://giuseppemerlino.wordpress.com/2011/02/17/congruenze/ In questa breve nota useremo il simbolo  ^  per denotare “elevato a” ed il simbolo  *  per

La Hot News

denotare “moltiplicato per”.Operando con carta e penna, si può risolvere la congruenza  Ax ≡ B modulo N, agendo in questo modo:Si tratta la congruenza come se fosse un’eguaglianza e si ricava la x: x = B / A Poi si somma al numeratore B il numero N tante volte fino a che  (B + kN)  sia divisibile per A. La soluzione della congruenza sarà  (B + kN) / A.Facciamo un esempio pratico:Si voglia risolvere la congruenza: 5x ≡ 11  (modulo 41) Dobbiamo aggiungere ad 11 tante volte 41 finchè non si ottenga un numero divisibile per 5: 11 + 41 = 5252 + 41 = 9393 + 41 = 134134 + 41 = 175  divisibile per 5. 175 : 5 = 35 Dunque la nostra congruenza avrà soluzione  x = 35, infatti: 5x ≡ 11  (modulo 41) 5x = 5*35 = 175 e 175 : 41 = 4 con resto 11. Qualora il numero N sia un numero primo P, esiste una soluzione rigorosa per la congruenza Ax ≡ B  modulo P, cioè una formula per x.Il piccolo Teorema di Fermat asserisce che, se P è un numero primo, allora: A^(P-1) ≡ 1 (modulo P)per ogni A compreso tra A e (P-1) e, più in generale, per ogni A che sia primo con P. Rielaboriamo questa espressione: A*A^(P-2) ≡ 1  (modulo P) Moltiplichiamo ambo i membri per B: A*B*A^(P-2) ≡ B  (modulo P) Confrontando questa espressione con la congruenza  Ax ≡ B  modulo P, otteniamo immediatamente: x  =  B*A^(P-2)  (modulo P) Diciamo subito che questa soluzione algebrica coinvolge numeri molto grandi, ma esiste un semplice algoritmo (usato nei programmi al computer) per superarlo. Facciamo prima un esempio con numeri “piccoli”. Si voglia risolvere la congruenza: 5x ≡ 2  (modulo 13) 13 è un numero primo, per cui possiamo applicare la nostra soluzione: x  =  B*A^(P-2)  =  2*5^11  =  2 * 48828125  =  97656250  (modulo P) La minima soluzione della congruenza (detta radice) è il resto della divisione di 97656250 diviso 13: 97656250 : 13  =  7512019 col resto di  3. Dunque la soluzione della congruenza  5x ≡ 2  (modulo 13)  sarà  x= 3, infatti (5*3 -2) è divisibile per 13, come si può facilmente verificare.Ovviamente, con coefficienti e modulo così piccoli, avremmo fatto prima a risolvere la congruenza per tentativi, ma non lo avremmo certo potuto fare per una congruenza con coefficienti e modulo appena più grandi.Abbiamo accennato prima ad un algoritmo per calcolare  il termine  B*A^(P-2)  (modulo P)Si procede in questo modo:Si moltiplica A per se stesso tante volte fino a giungere al primo termine che supera P.Si calcola il valore di questo prodotto modulo P e lo si moltiplica per A tante volte, sempre fermandosi al primo termine che supera P.Si continua fino ad aver moltiplicato in tutto (P-2) termini e si calcola il risultato modulo P.Infine si moltiplica per B e, se necessario, si calcola il risultato modulo P.Questo metodo che, effettuato con carta e penna, è estremamente laborioso (immaginatelo con numeri grandi), è velocissimo al computer, se programmato in linguaggio C o CPP o anche in Basic. Il risultato si ottiene in una frazione di secondo.Facciamo un esempio pratico.Si voglia risolvere la congruenza: 5x ≡ 11  (modulo 41) 41 è un numero primo, quindi sarà valida la soluzione:  x  =  B*A^(P-2)  =  11*5^39  (modulo 41). Calcoliamo, con l’algoritmo che abbiamo appena esposto, il termine  5^39  (modulo 41). 5*5*5 = 125  ;  125 modulo 41 = 22*5*5 = 50  ;   50 modulo 41 = 99*5 = 45  ;  45 modulo 41 = 44*5*5 = 100  ;  100 modulo 41 = 1818*5 = 90  ;  90 modulo 41 = 88*5*5 = 200  ;  200 modulo 41 = 3636*5 = 180  ;  180 modulo 41 = 1616*5 = 80  ;  80 modulo 41 = 3939*5 = 195  ;  195 modulo 41 = 3131*5 = 155 ;  155 modulo 41 = 3232*5 = 160  ;  160 modulo 41 = 3737*5 = 185  ;  185 modulo 41 = 2121*5 = 105  ;  105 modulo 41 = 2323*5 = 115  ;  115 modulo 41 = 3333*5 = 165  ;  165 modulo 41 = 11*5*5*5 = 125  ;  125 modulo 41 = 22*5*5 = 50  ;   50 modulo 41 = 99*5 = 45  ;  45 modulo 41 = 44*5*5 = 100  ;  100 modulo 41 = 1818*5 = 90  ;  90 modulo 41 = 88*5*5 = 200  ;  200 modulo 41 = 3636*5 = 180  ;  180 modulo 41 = 1616*5 = 80  ;  80 modulo 41 = 3939*5 = 195  ;  195 modulo 41 = 3131*5 = 155 ;  155 modulo 41 = 3232*5 = 160  ;  160 modulo 41 = 3737*5 = 185  ;  185 modulo 41 = 2121*5 = 105  ;  105 modulo 41 = 2323*5 = 115  ;  115 modulo 41 = 33 Ci fermiamo in quanto abbiamo moltiplicato 5 per se stesso 39 volte. Dunque: 5^39 modulo 41 = 33 poichè x = 11*5^39, dobbiamo ancora moltiplicare per 11: x = 11*33 = 363  ;  363 modulo 41 = 35. Dunque 35 sarà la soluzione della nostra congruenza, come si può facilmente verificare: 5x ≡ 11  (modulo 41) 5*35 = 175 175 : 41 = 4 con resto appunto 11. La soluzione della congruenza  Ax ≡ B  modulo N  è utile anche per risolvere l’equazione diofantea di primo grado in due incognite: Ax + By  =  C Nella quale A, B e C sono numeri interi e le soluzioni (x,y) sono costituite da numeri interi.Infatti questa equazione può essere facilmente trasformata in una congruenza di primo grado:Si ricavi dall’equazione indifferentemente x o y: y  =  (C – Ax) / B   (1) Affinchè y sia un numero intero, (C – Ax) dovrà essere divisibile per B e cioè: C – Ax  ≡  0  (modulo B) C ≡ Ax (modulo B) Ax ≡ C (modulo B) Risolvendo questa congruenza si trova la x e, ponendo la x nella (1), si trova la y. Sia x che y risulteranno numeri interi.Consideriamo, ad esempio, l’equazione diofantea: 9x + 7y  =  200 y  =  (200 – 9x) / 7    (2) 200 – 9x  ≡  0  (modulo 7) 9x ≡ 200  (modulo 7) Poichè 7 è un numero primo, possiamo applicare la formula: x  =  B*A^(P-2)  (modulo P) x  =  200*9^5  (modulo 7) x  =  200*59049  (modulo 7) x  =  11809800  (modulo 7) x  =  2 Poniamo questo valore della x nella (2) per ricavare la y: y  =  (200 – 9x) / 7  =  (200 – 18) / 7  =  182 / 7  =  26. Dunque una soluzione dell’equazione diofantea  9x + 7y  =  200 sarà: x = 2  ;  y = 26 Infatti: 9x + 7y  = 9*2 + 7*26  = 18 + 182  = 200 Condividi su FacebookFacebook Related

[...Leggi Tutto]

 
 

Novita'  Vuoi Commentare l'Articolo? Accedi al portale o se non hai il login Registrati


Ogni opinione espressa in questi commenti e' unicamente quella del suo autore, identificato tramite nickname collegato alla sua registrazione e di cui si assume ogni responsabilita' civile, penale e amministrativa derivante dalla pubblicazione del materiale inviato.L'utente, inviando un commento, dichiara e garantisce di tenere Hot-News.it manlevata e indenne da ogni eventuale effetto pregiudizievole e/o azione che dovesse essere promossa da terzi con riferimento al materiale divulgato e/o pubblicato.

Sconti e Offerte

Risparmi, Sconti, OfferteVuoi risparmiare sui tuoi acquisti? Offerte, Sconti, Codici Sconto, LastMinute e tanto altro ancora solo per te!

Ads

Le HOT News!

 

Vuoi Guadagnare e fare Affari!?

 Vuoi guadagnare e fare affari con internet?! Scopri come ogni giorno puoi, con soli 5 mi...

 

Dediche d'Amore

Dedica al tuo Lui o alla tua Lei parole d'amore...Hot-News.it pubblicherà la tua dedica ...

 

Dì la tua! Pubblica un tuo articolo!

Diventa reporter di Hot-News.it! E' facilissimo! 2 secondi e potrai veder i tuoi articoli ...

Chi è Online

Visitatori Online  541 visitatori online

Statistiche Visitatori

mod_vvisit_counterOggi2299
mod_vvisit_counterQuesto mese118005
mod_vvisit_counterTotale13486612


forum, portale, soundtrack, hotnews, hot news, notizie, videogiochi, ps3, xbox, shop, compra, prezzi, gossip, donna, rss, calcio, mondo, lavoro, musica, calciomercato, voti fantacalcio, probabili formazioni, uomini e donne, amici, maria de filippi