NEMEROS PRIMOS

[peppe]

"NUMEROS PRIMOS"
è il titolo di questa videolezione in cui vengono discussi 4 questi sui numeri primi:

https://www.youtube.com/watch?v=h-o3NTm73i0

Relativamente al primo quesito:

Se 80! ha n divisori. Quanti divisori ha 81! ?

si fa presto a dire " se n è il numero dei divisori di 80! ".
Ho provato a calcolare 80! con WolframAlpha e mi sforna un numero
astronomico.
Lo stesso dicasi con la fattorizzazione di 80!

E allora mi chiedo, nel caso di numeri così grandi, come si fa a
calcolare il numero dei suoi divisori, dal momento che neppure con
WolframAlpha sono riuscito a calcolarli?

Sicuramente non è pensabile applicare il metodo ,che è abbastanza
difficoltoso anche con numeri piccoli, spiegato qui:

https://www.lezionidimatematica.net/Num ... one_06.htm

Sempre riguardo a questo primo quesito, riesco a seguire solo lo
svolgimento della prima parte.
Non riesco a capire perché l'esponente del fattore 3, (che è
26+8+2=36), si ottiene con le divisioni successive di 80 diviso 3, come
specificato nell'esempio "Práctico" che fa il professore.

Saluti .peppe

[Gianfranco]

Se 80! ha n divisori. Quanti divisori ha 81! ?

E allora mi chiedo, nel caso di numeri così grandi, come si fa a
calcolare il numero dei suoi divisori, dal momento che neppure con
WolframAlpha sono riuscito a calcolarli?

Ciao Peppe, provo a risponderti senza aver visto il video.
---
Per prima cosa dico due punti fondamentali per risolvere questo problema.

• Primo punto: c'è una formula per trovare il numero dei divisori di un numero conoscendo la sua fattorizzazione in numeri primi, ma in questo caso non serve applicarla esplicitamente. Bisogna invece suppore di conoscere tale numero e che sia $n$.

• Secondo punto: in questo caso serve invece un metodo per calcolare l'esponente del fattore $3$ nella fattorizzazione di $80!$. Tale metodo è abbastanza facile e si può applicare soltanto col calcolo mentale.

---
Segue traccia di risoluzione. Puoi fare delle prove per verificare.

Prendi per esempio la scomposizione in fattori primi di 360.
$360 = 2^3 \cdot 3^2 \cdot 5^1$
Il numero totale dei fattori di 360 è:
$4 \cdot 3 \cdot 2 = 24$

In generale, sapendo la scomposizione in fattori primi di un numero, si può calcolare quanti fattori ha.
Per esempio, se:
$z = a^p \cdot b^q \cdot c^r \cdot ...$
allora il numero dei fattori di n è:
$nf=(p+1)(q+1)(r+1)...$

Veniamo al nostro problema di $80!$ e $81!$

1) Sappiamo che i fattori di $80!$ sono $n$.

2) Sappiamo che $81!=80!\cdot3^4$

3) Quindi la scomposizione in fattori primi di $81!$ differisce da quella di $80!$ solo per il fatto che l'esponente di $3$ aumenta di $4$ unità.

4) Supponiamo di conoscere l'esponente di $3$ nella fattorizzazione di $80!$ e chiamiamolo $k$.

5) Allora è facile capire che il numero $n_1$ dei fattori di $81!$ è:
$
\displaystyle n_1=\frac{n}{k+1}\cdot(k+1+4)=n+\frac{4n}{k+1}
$

6) Se conosciamo $k$, è facile trovare $n_1$.

A questo punto il problema diventa:
Nella scomposisizione di $80!$, qual è l'esponente del fattore $3$?
.
.
.
La risposta è:
$k=36$
.
.
.
da cui si ricava che il numero di fattori di $81!$ è:
$\displaystyle n_1=n+\frac{4n}{37}=\frac{41n}{37}$


Per pura curiosità, aggiungo i risultati espliciti trovati con Maxima.

fattori80fatt.png (35.74 KiB) Visto 20241 volte

[Gianfranco]

Ok, ma come si fa a scoprire l'esponente di $3$ nella scomposizione di $80!$ a mente o quasi?
Basta pensare a come si forma $80!$.
$80!=1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot .... \cdot 9 \cdot ... \cdot 27 \cdot ... \cdot 80$

$80 \ \mathbf{div}\ 3 = 26$
$80 \ \mathbf{div}\ 9 = 8$
$80 \ \mathbf{div}\ 27 = 2$

Esponente di $3 = 26+8+2=36$

Oppure, ancora più facile:
$80 \ \mathbf{div}\ 3 = 26$
$26 \ \mathbf{div}\ 3 = 8$
$8 \ \mathbf{div}\ 3 = 2$

Esponente di $3 = 26+8+2=36$

[peppe]

Gianfranco,
grazie per i chiarimenti.

Saluti. peppe

[Gianfranco]

Il procedimento che ho mostrato (ma non dimostrato) per trovare l'esponente di $3$ nella fattorizzazione di $80!$ funziona perché $3$ è un numero primo.
Forse è per questo motivo che il post si intitola "Numeros primos".
Se invece $a$ è un numero composto, per trovare la massima potenza di $a$ che divide $b!$ bisogna scomporre $a$ in fattori primi e fare il test per ogni fattore primo di $a$.
1) Tutti i fattori di $a$ devono dividere $b!$
2) L'esponente massimo di $a$ è il minimo tra gli esponenti dei fattori di $a$ nella fattorizzazione di $b!$

Per esempio:
1) la massima potenza di $6$ che divide $20!$ è $6^8$ perché $20!=2^{18} \cdot 3^8$...etc.
2) la massima potenza di $46$ che divide $20!$ è $46^0$ perché $23$ non divide $20!$
3) la massima potenza di $38$ che divide $20!$ è $38^1$

Salvo errori & omissioni.

[peppe]

Gianfranco,approfitto della gentile e paziente disponibilità per chiarire
un'altra questione che oggi pomeriggio mi sta facendo scervellere un po'.

Trascrivo dal sito (vedi fonte)

"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^2 = B^2

Risulterà allora:

N = B^2 – A^2

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^2

Troviamo i fattori:

391 + 3^2 = 20^2

391 = 20^2 – 3^2

391 = (20 – 3) x (20 + 3)

391 = 17 x 23

Come si può facilmente verificare."

Fonte:
https://giuseppemerlino.wordpress.com/2 ... ro-intero/

Ho fatto anch'io una prova con il numero 405, che dista dal quadrato 441 di 36 unità,ossia 6^2
e i conti tornano :
405*6^2= 21^2
405=21^2-6^2
405=(21-6)*(21+6)
405=15*27 (e 15 e 27 sono due divisori "vicini")

Poi ho provato con il numero scelto a caso, 395 = (5*79), e mi sta sorgendo il dubbio che ,forse,
nel caso in cui i due divisori sono "distanti " tra loro (come lo sono 5 e 79) il metodo NON funziona cosa
che sicuramente non è vera).

Nei casi simili al numero 395 = 5X79, qual è il numero A^2 che sommato a 395 mi dà B^2?
Ho provato con i quadrati dei numeri da 1 a 30 ed oltre ma inutilmente.

Esiste un metodo pratico e veloce per trovare il valore del quadrato B^2=395+A^2?

Scusa il disturbo.
Saluti.peppe

[franco]

Esiste un metodo pratico e veloce per trovare il valore del quadrato B^2=395+A^2?

Sapendo che i fattori di 395 sono 5 e 79, è semplice calcolare A e B ...
$(79+5)/2=42$
$(79-5)/2=37$
$395+37^2=42^2$
$395+1369=1764$

Però è un serpente che si morde la coda ... se vogliamo trovare i fattori del numero dato non so quanto questo sistema sia pratico.

[peppe]

Grazie Franco,anche se mi sfugge il motivo percui la somma è la sottrazione dei due fattori devono essere divisi per 2. Per quanto riguarda la praticità del metodo, quello che si insegna sin dalla scuola media è sicuramente il più facile. La mia è solo una curiosità.

[franco]

... mi sfugge il motivo percui la somma è la sottrazione dei due fattori devono essere divisi per 2...

Peppe,
come hai scritto nel tuo post:
$N+A^2=B^2$
$N=B^2-A^2$
$N=(B–A)(B+A)$

i due fattori sono quindi:
$x=B+A $
$y=B-A$

sommando membro a membro:
$x+y=2B$
$B=(x+y)/2$

sottraendo membro a membro:
$x-y=2A$
$A=(x-y)/2$

[peppe]

Illuminante!
Grazie Franco.

[Gianfranco]

Ciao Peppe, mi apprestavo a rispondere alla tua domanda ma vedo che lo ha fatto egregiamente Franco.
Grazie Franco!

[peppe]

Grazie, Gianfranco.
Franco è arrivato per 'primo'...
Tieniti pronto per i miei prossimi dubbi.
Saluti. peppe.