qualcuno mi sa dire come funziona l'algoritmo inventato da fermat per scomporre in fattori primi un numero?
grazie..
fermat e la scomposizione in fattori primi
Se è quello che dico io...
Ad esempio tu hai un numero $ \dispaystyle N $ che vuoi scomporre...
Devi trovare il numero più piccolo tale sia $ \dispaystyle m^{2}>N $
Attenzione il più piccolo...
Poi devi fare in modo che una di queste forme
$ \dispaystyle \\ m^{2}-N, (m+1)^{2}-N, (m+2)^{2}-N $
E via dicendo sia un quadrato perfetto
ad una volta che ad esempio hai trovato che
$ \dispaystyle (m+c)^{2} - N=y^{2} $
poni
$ \dispaystyle x=(m+c)^{2} $
$ \dispaystyle \\ x^{2}-N=y^{2} \\ N=x^{2}-y^{2} $
E scomponi la differnza di quedrati
$ \dispaystyle \\ N=(x+y) \cdot (x-y) $
Se vuoi qualche esempio non esitare a chiedere
Ad esempio tu hai un numero $ \dispaystyle N $ che vuoi scomporre...
Devi trovare il numero più piccolo tale sia $ \dispaystyle m^{2}>N $
Attenzione il più piccolo...
Poi devi fare in modo che una di queste forme
$ \dispaystyle \\ m^{2}-N, (m+1)^{2}-N, (m+2)^{2}-N $
E via dicendo sia un quadrato perfetto
ad una volta che ad esempio hai trovato che
$ \dispaystyle (m+c)^{2} - N=y^{2} $
poni
$ \dispaystyle x=(m+c)^{2} $
$ \dispaystyle \\ x^{2}-N=y^{2} \\ N=x^{2}-y^{2} $
E scomponi la differnza di quedrati
$ \dispaystyle \\ N=(x+y) \cdot (x-y) $
Se vuoi qualche esempio non esitare a chiedere
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Bè allora applichi ancora l'algoritmo a entrambi i numeri, fin quando non ottieni tutti i primi.gian92 ha scritto:ma se un numero ha più di due fattori?
Se provi ad applicare l'algoritmo su un numero primo ti assicuro che non funziona...numero primo proprio perchè non scomponibile...oppure se funziona ottieni come scomposizione 1 per il numero stesso...gian92 ha scritto:succederà che viene un numero primo e un numero primo sul quale applicare lo stesso algoritmo?
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Allora...partendo dal presupposto che non lo ricordo bene...comunque il punto di forza di quell'algoritmo è proprio il fatto che il numero che consideri non è divisibile per 2.
Anche perchè i numeri primi son tutti dispari(tranne appunto il 2)...
Quindi se devi usare l'algoritmo ti assicuri di operare con un numero dispari altrimenti lo dividi per 2 fin quando non arrivi ad un numero dispari (o al limite ti rendi conto che il numero che volevi scomporre è una potenza di 2)...
Comunque credo che l'algoritmo non funzioni con i numeri pari...
Magari prova a fare gli esercizi che stanno alla fine del libro...
Anche perchè i numeri primi son tutti dispari(tranne appunto il 2)...
Quindi se devi usare l'algoritmo ti assicuri di operare con un numero dispari altrimenti lo dividi per 2 fin quando non arrivi ad un numero dispari (o al limite ti rendi conto che il numero che volevi scomporre è una potenza di 2)...
Comunque credo che l'algoritmo non funzioni con i numeri pari...
Magari prova a fare gli esercizi che stanno alla fine del libro...
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
Mah non credo se ne siano dimenticati...questo lo penso io...magari funziona lo stesso...fai qualche tentativo che ti costa...io non lo ricordo bene...appena ho tempo me lo rivedo per bene e faccio qualche tentativo...se non hai risolto posto il tuttogian92 ha scritto:siccome non era scritto che non si poteva usare con le potenze di due ho pensato di non aver capito bene come funzionava...
comunque grazie si sono dimenticati di specificare questa cosa..
Alla fine del diciannovesimo secolo, un matematico straordinario,Cantor, languiva in un manicomio... Più si avvicinava alle risposte che cercava, più esse sembravano allontanarsi. Alla fine impazzì, come altri matematici prima di lui
io ho provato con 128 ma va avanti per molto tempo.
comunque siccome l'algoritmo funziona così:
si prende un numero e si scrive in questo modo:
x=3q1+r0poi si fanno operazioni e quello che viene si scrive come
y=5q2+r1 e cosi via
z=7q3+r2 quando si trova rn=0 vuol dire che il numero dispari davanti a qn è un divisore del numero iniziale quindi se un numero non ha divisori dispari non si potrà mai trovare un suo divisore con questo algoritmo....
comunque siccome l'algoritmo funziona così:
si prende un numero e si scrive in questo modo:
x=3q1+r0poi si fanno operazioni e quello che viene si scrive come
y=5q2+r1 e cosi via
z=7q3+r2 quando si trova rn=0 vuol dire che il numero dispari davanti a qn è un divisore del numero iniziale quindi se un numero non ha divisori dispari non si potrà mai trovare un suo divisore con questo algoritmo....