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
Domenica
Gen 26
Messaggio
Hot-News.it Merlino's Science News DIVISORI, FATTORI PRIMI E FATTORIZZAZIONE DI UN NUMERO INTERO
03
Apr
2014

DIVISORI, FATTORI PRIMI E FATTORIZZAZIONE DI UN NUMERO INTERO




Il Teorema Fondamentale dell’Aritmetica afferma che: “Ogni numero intero maggiore di 1 o è un numero primo o si può esprimere come prodotto di numeri primi. Tale rappresentazione è unica,

La Hot News

se si prescinde dall’ordine in cui compaiono i fattori”.Ad esempio: 1105 = 5 x 13 x 17 E non vi è nessun’altra rappresentazione di questo numero come prodotto di numeri primi.A questo punto occorre ricordare che un numero primo è un numero intero maggiore di uno divisibile solo per se stesso e per l’unità.Non bisogna confondere i fattori primi di un numero con i suoi divisori. Ad esempio, nell’esempio precedente, i fattori primi di 1105 sono 5, 13 e 17, mentre i suoi divisori sono 1, 5, 13, 17, 65, 85, 221 e 1105 e, tra questi, 1, 65, 85, 221 e 1105 non sono numeri primi.Nella scomposizione in fattori primi di un numero, uno o più fattori primi possono anche apparire più volte, ad esempio: 360 = 2³ x 3² x 5 Dove il fattore primo 2 appare 3 volte, il fattore primo 3 appare 2 volte ed il fattore primo 5 appare una volta.Esistono due relazioni tra i fattori primi ed i divisori di un numero.Nelle formule seguenti useremo il simbolo ^ per indicare “elevato a”.Se la scomposizione in fattori primi di N è: N = p^a  x  q^b  x …… x  r^c Allora il numero dei divisori di N sarà dato da: (a + 1) x (b + 1) x …… x (c + 1) Verifichiamo quanto detto sul numero 360, i cui divisori sono 24 (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180 e 360): 360 = 2³x3²x5 (3 + 1) x (2 + 1) x (1 + 1) = 4 x 3 x 2 = 24 La somma dei divisori sarà invece data da: Verifichiamo sempre sul numero 360:La somma dei divisori di 360 è: 1+2+3+4+5+6+8+9+10+12+15+18+20+24+30+36+40+45+60+72+90+120+180+360 = 1170 Applichiamo ora la formula, ricordando sempre che 360 = 2³x3²x5: [(2^4 -1) / 1] x [(3^3 - 1) / 2] x [(5^2 – 1) / 4 = = 15 x 13 x 6 = 1170 Si definiscono divisori propri di un numero tutti i suoi divisori tranne il numero stesso.In particolare, si definisce “numero abbondante” un numero che sia inferiore alla somma dei suoi divisori propri e “numero deficiente” un numero che sia superiore alla somma dei suoi divisori propri.Il nostro esempio 360 è un “numero abbondante” in quanto la somma dei suoi divisori propri è 810.Quei rarissimi numeri che sono eguali alla somma dei loro divisori propri, vengono definiti “numeri perfetti” e sono stati trattati in questo articolo:http://giuseppemerlino.wordpress.com/2010/10/25/numeri-amici-perfetti-e-n-di-mersenne/ Uno dei problemi più ardui della Teoria dei Numeri è la scomposizione di un numero intero nei suoi fattori primi.“Ma è un argomento che si insegna alla scuola media !”, direte voi. Verissimo, ma quei metodi, dai quali peraltro partiremo, sono utilizzabili per numeri di grandezza “ragionevole”, ma già con un numero considerato “piccolo” in Teoria dei Numeri come 71.445.617 (= 503 x 142.039) ci troveremmo in grandi difficoltà a trovarne i fattori primi.Il problema è talmente arduo che numeri primi di oltre 60 cifre decimali vengono usati in crittografia, per esempio per nascondere i dati della vostra carta di credito quando comprate qualcosa su internet o quando accedete dal web al vostro conto bancario.Il punto di partenza per fattorizzare un numero intero sono i criteri di divisibilità. Essi sono veramente tanti, ma quelli veramente utili nella fase iniziale dell’analisi dell’intero da fattorizzare sono, a mio giudizio, solamente tre:1) tutti i numeri pari (cioè con ultima cifra 0, 2, 4, 6, 8) sono divisibili per 22) tutti i numeri che hanno come somma delle cifre un numero divisibile per 3, sono divisibili per 3.3) tutti i numeri con ultima cifra 5 o 0, sono divisibili per 5Procediamo allora, col metodo che abbiamo imparato alla scuola media, alla fattorizzazione nel nostro solito esempio (360).Scriviamo il numero tracciando a destra dello stesso una riga verticale.Cerchiamo il più piccolo numero primo per cui è divisibile il numero di partenza; nel nostro caso 2 e scriviamo perciò 2 a destra di 360.Scriviamo il quoziente 180 sotto a 360 e procediamo sempre così, fino a giungere ad un numero primo, quando la scomposizione sarà terminata. Questo procedimento viene estremamente velocizzato al computer facendo alcune semplici considerazioni:Innanzitutto, se il numero da esaminare è pari, lo si divide per 2 e, se il risultato fosse ancora pari lo si divide di nuovo per 2, fino a che si ottenga un numero dispari.Ora si comincia l’analisi sul numero dispari, provando per ciascun numero primo, a partire da 3, 5, 7, 11 ….., se il numero da esaminare sia divisibile per esso.La velocità del procedimento è estremamente accelerata da una semplice considerazione:Se il nostro numero da esaminare è N, non è necessario provare la sua divisibilità per tutti i numeri primi fino ad N, ma ci si può tranquillamente limitare solo ai numeri primi inferiori alla radice quadrata di N, infatti, se N non è un numero primo, sicuramente un suo fattore primo sarà inferiore a questo limite.Se, per esempio, vogliamo fattorizzare il numero 4181, dobbiamo provare tutti i numeri primi fino al limite 65 (√4181 = 64,66065264 …..) e cioè: 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61. Dobbiamo dunque eseguire solo 17 divisioni, cosa che il computer esegue pressocchè istantaneamente. Ma di solito il fattore primo viene trovato ancora prima. Nel nostro esempio è 37, ottenuto dopo 11 divisioni: 4181 = 37 x 113 Per fattorizzare grandi numeri è dunque assolutamente necessario disporre di una tabella di numeri primi, il più estesa possibile. Qui ne diamo una con i numeri primi da 1 a 1013: Un altro metodo di fattorizzazione di un numero intero N, che talvolta può essere più veloce da quello esposto, è stato ideato dal grande matematico Pierre de Fermat.Questo metodo consiste nel cercare un quadrato esatto tale che, sommato ad N, dia un altro quadrato esatto: N + A² = B² Risulterà allora: N = B² – A² N = (B – A) x (B + A) Ed il numero è fattorizzato ! Si procede sommando uno alla volta al numero N da fattorizzare i quadrati esatti 1, 4, 9, 16, 25, 36 etc … finchè questa somma non dia per risultato un quadrato esatto.Questo metodo è più veloce del precedente quando esistano due divisori di N vicini fra loro.Facciamo un esempio:Si voglia fattorizzare il numero 391. 391 + 1 = 392 (non è un quadrato esatto)391 + 4 = 395 (non è un quadrato esatto)391 + 9 = 400 = 20² Troviamo i fattori: 391 + 3² = 20² 391 = 20² – 3² 391 = (20 – 3) x (20 + 3) 391 = 17 x 23 Come si può facilmente verificare. Anche in questo caso può essere utile una tabella di quadrati perfetti. Qui ne diamo una da 1 a 30: I metodi di fattorizzazione fin qui esposti diventano lenti quando si debbano fattorizzare numeri di centinaia di cifre. In tal caso si usano metodi sofisticati che richiedono conoscenze di matematiche superiori che esulano da questa breve trattazione. Citiamo ad esempio il metodo Pollard Rho (probabilistico), il metodo Pollard P-1 (probabilistico) ed il metodo delle curve ellittiche (ECM). Condividi su FacebookFacebook Articoli collegati

[...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  338 visitatori online

Statistiche Visitatori

mod_vvisit_counterOggi5126
mod_vvisit_counterQuesto mese125006
mod_vvisit_counterTotale14052303


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