trovare i divisori di un intero

[scifo]

Ciao amici

Esiste un metodo che, dalla conoscenza dei fattori primi di un intero, può ricavare tutti i suoi divisori?

Se ricordo bene, ho letto da qualche parte che, operando sugli esponenti dei fattori primi di un intero si ottiene il numero dei suoi divisori..
E' giusto?

[Gogo Livorno]

Attento, come dici te la formula degli esponenti è per ricavare il NUMERO dei divisori, non quali siano.

Semplicemente, data la fattorizzazione di un numero, i suoi divisori corrispondono al prodotto di tutti gli esponenti della fattorizzazione aumentati di 1.

La dimosrazione è semplice semplice:

E' scontato che un divisore di un numero dev'essere un sottoinsieme della sua fattorizzazione.

Non è detto però che il divisore contenga tutti i fattori primi del numero.

In pratica è come dire che per comporre il divisore ogni fattore primo p^k può essere preso in qualsiasi esponente da 0 a k, che sono ovviamente k+1.

Infatti si aggiunge lo 0 alla nostra scelta perchè, in quanto ogni numero elevato alla 0 fa 1, e in quanto 1 elemento neutro della moltiplicazione, consente di "far finta" che quel determinato fattore primo non sia stato preso, fino al caso estremo in cui tutti i fattori primi vengono presi alla 0, che darà il divisore 1.

Infatti, NOTA BENE: quella formula include nei divisori anche 1 (tutti i fattori primi alla 0) e il numero stesso (tutti i fattori primi al massimo esponente).

Ho provato a dirtela a parole per farti capire come funziona, se vuoi simboli procedo

[scifo]

Grazie per le tue informazioni,
anche se (pig-head!) non ho capito bene che significa
"un divisore di un numero deve essere un sottoinsieme della sua fattorizzazione"
e "non è detto che il divisore contenga tutti i fattori primi del numero".

Comunque ho capito che il numero dei divisori è il prodotto di tutti gli esponenti della fattorizzazione più 1...

Però, oltre al numero dei divisori, la cosa che mi interessava di più era se esiste un metodo che, dalla fattorizzazione di un numero ricava tutti i suoi divisori...

Potresti aiutarmi ancora?

[Gogo Livorno]

Metti che un numero sia:

2^3 * 3^2 * 5

Scrivilo come:

2*2*2*3*3*5

Tutti i suoi divisori non possono contenere altri fattori primi eccetto 2 3 e 5, e ovviamente non potranno avere più di tre 2, due 3, e un 5.

Quindi in pratica dato l'insieme 2,2,2,3,3,5 per avere un divisore basta prendere un sottoinsieme.

Esempio: 12=2*2*3

I suoi divisori sono tutti i sottoinsiemi possibili della sua fattorizzazione:
2,3,2*2,2*3,2*2*3

Su questo ci siamo?

Per lo stesso motivo ti dico che un divisore non deve per forza contenere tutti i fattori primi del numero di partenza.

Esempio.

N=30=2*3*5

Un divisore di 30 può essere 6, che è 2*3. il 5 mica lo contiene!!!

Qusto è il motivo per il quale nella formula tutti gli esponenti vanno aumentati di uno, in quanto si contempla anche che un fattore possa assumere esponente 0.

In pratica a partire da 30 scriverebbe 6 come 2^1 * 3^1 * 5^0.


Un po' meglio?

[scifo]

Quindi se ho capito bene bisogna prendere per l'insieme fattorizzazione tutti gli elementi, tutti i prodotti degli elementi due a due e così via...

Mi rimangono alcuni dubbi. se ricordo bene la teoria degli insiemi (pig-head!)
Negli insiemi gli elementi non dovrebbero comparire una sola volta?
Il numero dei sottoinsiemi possibili di un insieme di n elementi
(escluso l'insieme vuoto) non dovrebbe essere 2^n - 1 ?

[pic88]

Mh, che sia il caso di fare un po' di ordine?

Restringendoci ai soli numeri interi positivi, sappiamo dal teorema fondamentale dell'aritmetica che ogni $ n \in \mathbb N $ con $ n>1 $ si scrive in modo unico nella forma

$ n=p_1^{a_1}\cdot...\cdot p_k^{a_k^} $ ove $ p_1<p_2<...<p_k $ sono numeri primi e gli $ a_1,...,a_k $ numeri naturali positivi.

Ti invito a provare che ogni divisore di $ n $ e' allora nella forma $ p_1^{b_1}\cdot...\cdot p_k^{b_k} $ ove gli esponenti sono numeri naturali tali che per ogni $ i $ tra 1 e $ k $ vale $ b_i\leq a_i $.

La storia degli insiemi non ha significato per come e' stata posta. Ne' ha molto senso cercare di dargliene uno.

[scifo]

Ho provato a determinare i divisori dalle formule che mi hai dato e ho trovato tutti i divisori a partire dalla fattorizzazione per vari numeri...thanks!

Mi è rimasto il dubbio che 2,2,2,3,3,5 non sia un vero insieme, ma non importa...

[Gogo Livorno]

Mh, che sia il caso di fare un po' di ordine?

Restringendoci ai soli numeri interi positivi, sappiamo dal teorema fondamentale dell'aritmetica che ogni $ n \in \mathbb N $ con $ n>1 $ si scrive in modo unico nella forma

$ n=p_1^{a_1}\cdot...\cdot p_k^{a_k^} $ ove $ p_1<p_2<...<p_k $ sono numeri primi e gli $ a_1,...,a_k $ numeri naturali positivi.

Ti invito a provare che ogni divisore di $ n $ e' allora nella forma $ p_1^{b_1}\cdot...\cdot p_k^{b_k} $ ove gli esponenti sono numeri naturali tali che per ogni $ i $ tra 1 e $ k $ vale $ b_i\leq a_i $.

La storia degli insiemi non ha significato per come e' stata posta. Ne' ha molto senso cercare di dargliene uno.

ti dò pienamente ragione, era solo una maniera per cercare di far digerire il concetto, penso che se fossi partito in quarta con le formule che hai postato ci avrebbe capito poco.

cmq, sono d'accordo sulla storia del divisore nella forma $ p_1^{b_1}\cdot...\cdot p_k^{b_k} $ però è bene specificare che gli esponenti b possono anche essere 0, penso sia fondamentale per far capire la formula.