Divisibilità e primalità

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
peppe
Livello 7
Livello 7
Messaggi: 840
Iscritto il: gio mag 26, 2005 1:41 pm
Località: Cirò Marina KR

Divisibilità e primalità

Messaggio da peppe » ven gen 06, 2017 10:31 pm

La $\sqrt a$ è un separatore?

Quando si "naviga" costeggiando la riva, ossia a vista e terra-terra, le
probabilità di incappare in una secca sono altissime specialmente
se non si possiede una carta nautica (leggi, matematicamente parlando, le dovute nozioni di base).
E oggi mi sono "arenato" in un imprevisto "banco di sabbia".

L'argomento riguardava la primalità dei numeri.

Come si fa a verificare se un numero è primo?

" Verificare se un numero a è primo o meno è un problema complesso, tuttavia sono note
alcune strategie per farlo.
Una prima strategia (utile anche per trovare la fattorizzazione di un numero non primo)
consiste nel dividere il numero a per tutti i primi noti in ordine crescente, fino
ad arrivare a $\sqrt{a}$. A quel punto, se nessuno dei primi che abbiamo provato era un divisore esatto
di a, allora a è certamente primo.


E fin qui la "cosa" è di una chiarezza lampante.

Senonché, l'Autore della discussione, per guastarmi il piacere d'aver capito, una volta tanto, una
cosa senza sforzarmi eccessivamente, e farmi "arenare", ci mette di traverso il "banco di sabbia"
di cui sopra: un vero bastone fra le ruote.

Perché continua asserendo:

Infatti se possiede un divisore $d > \sqrt a$, possiede anche il divisore $a/d < \sqrt a$.

E siccome, per "diffidenza", quando si ragiona sui numeri, ( e non sulle persone...) a
San Tommaso,(con il dovuto rispetto), non ho nulla da invidiare, mi sono messo all'opera facendo degli esempi pratici:

a = 23
$\sqrt23 = 4,79$ i primi inferiori a 4,79 sono 2 e 3 che non dividono il 23 : 23 è primo.

a = 24
$\sqrt 24 = 4,89$ i primi inferiori a 4,89 sono 2 e 3, quello superiore è 6
tutti dividono il 24 che quindi è composto.

$d >\sqrt a$------> 6 > 4,89
$a/d <\sqrt a$---> 24/6 = 4 < 4,89
+++
a = 25 quadrato perfetto non ci sono problemi.
+++
a = 26
$\sqrt 26 = 5,09$ i primi inferiori a 5,09 sono 2,3,5 e solo 2 è un divisore.
i primi superiori a 5,09 sono: 7,11 e 13 e solo 13 è un divisore.

$d > \sqrt a$------> 13 > 5,09
$a/d <\sqrt a$---> 26/13 = 2 < 5,09

Quello che non capisco è perché viene tirata in ballo la radice quadrata del numero.

E così, ragionando alla "Marzullo", mi sono fatto una domanda:

La radice quadrata di a è forse un separatore che fa da spartiacque tra numeri composti
e numeri che sono quadrati perfetti?


E dato questa risposta:

Se per i numeri composti che sono quadrati perfetti tipo 25, (escludendo 1 e 25) tra i divisori
c'è solo il 5, ossia la radice del numero, negli altri casi di numeri composti che non sono
quadrati perfetti ci sono divisori minori della radice del numero in questione e maggiori della
stessa, per cui la radice si comporta come se fosse un "separatore".


Intuisco il senso del ragionamento...ma algebricamente come si spiega?

Probabilmente la domanda è banale, ma, come al solito, non ne sono così certo...
Perdonate...peppe.
«Un uomo è come una frazione il cui numeratore è quello che è, e il cui denominatore quello che pensa di sé.
Più grande è il denominatore, minore la frazione.» Lev Nikolàevič Tolstòj(1828-1910).

giobimbo
Livello 5
Livello 5
Messaggi: 238
Iscritto il: sab nov 19, 2005 5:14 pm
Località: Biella

Re: Divisibilità e primalità

Messaggio da giobimbo » sab gen 07, 2017 8:05 am

L'autore dell'articolo dà per scontato che si stia parlando di numeri dispari, con questo assunto tutto diventa logico:
ogni dispari non primo deve essere il prodotto di due fattori (primi o composti) che sono uguali (Dispari x Dispari) oppure diversi (Piccolo x Grande), allora dividendo per tutti i primi minori della radice quadrata del numero a scopriamo se Dispari o Piccolo sono divisori o no del numero a in questione.

peppe
Livello 7
Livello 7
Messaggi: 840
Iscritto il: gio mag 26, 2005 1:41 pm
Località: Cirò Marina KR

Re: Divisibilità e primalità

Messaggio da peppe » sab gen 07, 2017 11:12 am

Ciao giobimbo e grazie per aver risposto.
Ho fatto delle prove pratiche di quanto affermi e i conti tornano, ma...:

" ogni dispari non primo deve essere il prodotto di due fattori (primi o composti) "

Es. $63 = 7* 9$ [7 è primo; 9 è composto; entrambi dispari]

$\sqrt63 = 7,93$

" oppure diversi (Piccolo x Grande) ":

Es. $35 = 5 * 7$ [5 primo piccolo; 7 primo grande]

$\sqrt35 = 5,91$


"dividendo per tutti i primi minori della radice quadrata del numero a scopriamo
se Dispari o Piccolo sono divisori o no del numero a in questione.
"

1° caso (7,93) : primi minori della radice quadrata di 63, sono: (2, 3 , 5, 7) [3 e 7 sono divisori]
2° caso (5,91) : primi minori della radice quadrata di 35, sono: (2, 3, 5) [solo 5 è divisore]

Però scusami, ma continuo a non afferrare in modo chiaro il ruolo " algebrico " svolto
dalla radice quadrata del numero.

Grazie ancora . peppe :wink:
«Un uomo è come una frazione il cui numeratore è quello che è, e il cui denominatore quello che pensa di sé.
Più grande è il denominatore, minore la frazione.» Lev Nikolàevič Tolstòj(1828-1910).

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 926
Iscritto il: ven mag 20, 2005 8:51 pm
Località: Sestri Levante
Contatta:

Re: Divisibilità e primalità

Messaggio da Gianfranco » sab gen 07, 2017 2:46 pm

Peppe, chiedi:
Intuisco il senso del ragionamento...ma algebricamente come si spiega?
Dato un numero naturale n, per ogni divisore minore (o uguale) della radice quadrata di n ce n'è un altro maggiore (o uguale) della stessa, per cui la radice si comporta come se fosse un "separatore" dei divisori.

Questo è dimostrato dal ragionamento:
Infatti se n possiede un divisore \large a\le\sqrt{n}, possiede anche il divisore \large b=\frac{n}{a}\ge\sqrt{n}.

Però, da questo ragionamento non è chiaro come si arriva a scegliere \large \sqrt{n}.

Immagino che tu chieda una dimostrazione basata su calcoli aritmetici (o algebrici) che permetta di costruire il numero separatore il quale dovrebbe risultare proprio la radice quadrata di n.

Ecco la mia idea:
1) Consideriamo n naturale.

2) Per ogni divisore a di n, esiste un altro divisore b tale che \large b=\frac{n}{a} e possiamo scrivere \large n=ab.

3) Possiamo sempre assegnare a, b in modo che: 1 \le a \le b \le n

4) Consideriamo la disuguaglianza:
a \le b

5) Moltiplichiamo entrambi i membri per a
a^2  \le  ab (perché a  \le  b)

6) Ora moltiplichiamo entrambi i membri per b
ab  \le  b^2 (perché a  \le  b)

7) Combiniamo le due disuguaglianze:
a^2  \le  ab  \le  b^2

8) Ricordando che ab=n, sostituiamo:
a^2  \le  n  \le b^2

9) Estraiamo la radice quadrata (aritmetica)
a  \le  \sqrt {n}  \le b

Questo discorso vale per tutti i numeri naturali, siano essi primi, composti o quadrati perfetti.
Se eliminiamo i quadrati perfetti, possiamo eliminare l'= dalle disuguaglianze, ottenendo alla fine
a < \sqrt {n} < b

P.S.
Un significato al confine fra aritmetica e geometria si ricava dal fatto che \sqrt {n} è la media geometrica di 1 e n.
Tale media geometrica "separa" i divisori di n in due parti uguali.
Pace e bene a tutti.
Gianfranco

peppe
Livello 7
Livello 7
Messaggi: 840
Iscritto il: gio mag 26, 2005 1:41 pm
Località: Cirò Marina KR

Re: Divisibilità e primalità

Messaggio da peppe » sab gen 07, 2017 7:04 pm

Grazie Gianfranco la tua chiarissima dimostrazione: è quello che cercavo. Sono soddisfatto!
Prima di leggere la tua risposta, avevo scritto, e non ho fatto in tempo ad inviare, quanto segue:

Con l'aiuto di questa calcolatrice ho fatto un po' di conti ad uso e consumo di chi ci capisce più di me.
Sono partito dal 1947 per un fatto personale... Ecco i risultati:

1947 = 3 * 11 * 59
$\sqrt{1947} = 44,12...$
Numero di divisori: 8
Divisori :1, 3, 11, 33, 59, 177, 649, 1947
divisori primi < 44,12 : (3, 11)
divisori primi > 44,12 : 59
+++
1948 = 2 * 2 * 487
$\sqrt{1948} = 44,13...$
Numero di divisori: 6
Divisori :1, 2, 4, 487, 974, 1948
divisori primi < 44,13 : 2
divisori primi > 44,13 : 487
+++
1949 primo
$\sqrt{1949} = 44,14...$
++
1950 = 2 * 3 * 5 * 5 * 13 =13x150
$\sqrt{1950} = 44,15...$
Numero di divisori :24
Divisori :1, 2, 3, 5, 6, 10, 13, 15, 25, 26, 30, 39, 50, 65, 75, 78, 130, 150, 195, 325, 390, 650, 975, 1950
divisori primi < 44,15 :[ 2,3,5,13]
divisori primi > 44,15 : nessuno
+++
1951 : primo
$\sqrt{1951} = 44,17...$
+++
1952 = 2 * 2 * 2 * 2 * 2 * 61 = 32x61
$\sqrt{1952} = 44,18...$
Numero di divisori: 12
Divisori :1, 2, 4, 8, 16, 32, 61, 122, 244, 488, 976, 1952
divisori primi < 44,18 : 2
divisori primi > 44,18 : 61
+++
1953 = 3 * 3 * 7 * 31 = 31*63
$\sqrt{1953} = 44,19...$
Numero di divisori: 12
Divisori :1, 2, 4, 8, 16, 32, 61, 122, 244, 488, 976, 1952
divisori primi < 44,19 : 2
divisori primi > 44,19 : 61
...
2016 = 2 * 2 * 2 * 2 * 2 * 3 * 3 * 7 = 7 * 9 * 32
$\sqrt{2016} = 44,89...$
Numero divisori:36
Divisori: 1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 18, 21, 24, 28, 32, 36, 42, 48, 56, 63, 72, 84, 96, 112, 126, 144, 168, 224, 252, 288, 336, 504, 672, 1008, 2016
divisori primi < 44,89 : (2, 3, 7)
divisori primi > 44,89 : nessuno
+++
2017 : primo
$\sqrt{2017} = 44,91...$
+++
2018 = 2 * 1009
$\sqrt{2018} = 44,92...$
Numeri divisori:4
Divisori 1, 2, 1009, 2018
divisori primi < 44,92 : 2
divisori primi > 44, : 1009

Avendo oramai le idee chiare, avrei potuto fare a meno di postarla. E l'avrei fatto se non fosse stato
per quel P.S. in fondo alla tua dimostrazione, con il quale precisi che:

" Un significato al confine fra aritmetica e geometria si ricava dal fatto
che $\sqrt {n}$ è la media geometrica di 1 e n.
Tale media geometrica "separa" i divisori di n in due parti uguali.


E allora mi sono detto, dal momento che conosco la fattorizzazione perché non provare?
E, ovviamente, per la verifica ho scelto i due casi con il maggior numero di divisori:
1° Caso:
1952 = 2 * 2 * 2 * 2 * 2 * 61 = 32x61
$\sqrt{1952} = 44,18...$
Numero di divisori: 12
Divisori: 1, 2, 4, 8, 16, 32, 61, 122, 244, 488, 976, 1952

Quindi utilizzando WolframAlpha ho trovato che
(1* 2* 4* 8* 16* 32* 61* 122* 244* 488* 976* 1952)^1/12 = 55319580739542974464^(1/12) = $4* \sqrt{122}$=
= 44.18144406874904309684365537337726824340911848133800530878...
che corrisponde alla radice quadrata di 1952.$\sqrt{1952} = 44,18...$
Il quale si colloca al centro della lista:
Divisori: 1, 2, 4, 8, 16, 32,[44] 61, 122, 244, 488, 976, 1952
+++
2° Caso:
Il numero dell'anno appena trascorso contiene ben 36 divisori (vedi sopra) e la sua radice è 44,89...
La media geometrica è:
(2*3*4*6*7*8*9*12*14*16*18*21*24*28*32*36*42*48*56*63*72*84*96*112*126*144*168*224*252*288*336*504*672*1008*2016)^1/36 =
= 12*$\sqrt{14}$= 44.89988864128729662700498478779859162107223769334472335564...
che è il valore della $\sqrt{2016} = 44,89...$.
Lista divisori:
1, 2, 3, 4, 6, 7, 8, 9, 12, 14, 16, 18, 21, 24, 28, 32, 36, 42, [44]48, 56, 63, 72, 84, 96, 112, 126, 144, 168, 224, 252, 288, 336, 504, 672, 1008, 2016
E anche in questo caso la radice divide in due gruppi di 18 , i 36 divisori.

I conti tornano ma...la "nebbia" che ha fatto calare quel tuo P.S. rimane... :D
Però sono soddisfatto per la chiarezza del quesito iniziale, che non è per niente banale.
Grazie. peppe
---
Proprio mentre scrivo ho notato un'altra cosa curiosa: la differenza dei valori delle radici di 1950 e 1951 non seguono
la progressione di quelli che vanno dal 1947 al 1950 dove lo scarto decimale approssimato è di 1 unità.
La stessa cosa si verifica tra 2016 e 2017. Boh!
«Un uomo è come una frazione il cui numeratore è quello che è, e il cui denominatore quello che pensa di sé.
Più grande è il denominatore, minore la frazione.» Lev Nikolàevič Tolstòj(1828-1910).

Rispondi