OliForum Matematico

qualcuno mi sa dire come funziona l'algoritmo inventato da fermat per scomporre in fattori primi un numero?
grazie..

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

si è questo
stavo studiando il davenport e mi ero bloccato in quel punto...
come funziona adesso l'ho capito.
ma se un numero ha più di due fattori?
succederà che viene un numero primo e un numero primo sul quale applicare lo stesso algoritmo?

gian92 ha scritto:ma se un numero ha più di due fattori?

Bè allora applichi ancora l'algoritmo a entrambi i numeri, fin quando non ottieni tutti i primi.

gian92 ha scritto:succederà che viene un numero primo e un numero primo sul quale applicare lo stesso algoritmo?

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...

scusa mi sono sbagliato volevo dire non primo comunque grazie

sempre in argomento davenport....
l'algoritmo di captain per la scomposizione in fattori primi come può funzionare su numeri che hanno solo fattori pari?(escluso 1)

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...

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..

gian92 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..

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 tutto

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....