criteri di divisibilità ed altro

sergio_vanni · Messaggio da **sergio_vanni** » 01 gen 1970, 01:33

Trasferisco qui dal forum \"da 9 a n ...\" il dibattito sui criteri di divisibilità per sistemi di numerazione di ordine n (diverso da 0). Il materiale finora acquisito è il seguente:
 1. Divisibilità per n: se un numero termina per 0 esso è divisibile per n;
 2. Divisibilità per n-1: se la somma delle cifre che compongono un numero è divisible per n-1, allora il numero è divisibile per n-1;
 3. Divisibilità per n+1: se la differenza tra la somma delle cifre pari e la somma delle cifre dispari è nulla o è un numero divisibile per n+1, allora il numero è divisibile per n+1.
 Aggiungo:
 4. 1° Criterio di divisibilità per 2: se n è un numero pari, allora ogni numero che termini per una cifra pari è divisibile per 2;
 5. 2° Criterio di divisibilità per 2: se n è un numero dispari, allora ogni numero per il quale la somma delle cifre generi un numero pari è un numero divisibile per 2.
 6. Criterio di divisibilità per n/2: se n è un numero pari, sono divisibili per n/2 tutti i numeri che terminano per n/2 e per 0.
 
 Lascio alla libera fantasia di ciascuno trovare altri criteri di divisibilità o altre peculiarità dei sistemi di numerazione non decimali.
 _______________
 
 Ricorda che non sei sfamato dalla generosità del tuo salumiere, ma che sei nutrito dalla sua ingordigia. [ This message was edited by: sergio_vanni on 2001-06-22 07:57 ]

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

DIVISIBILITA\' PER 3
 Ecco i criteri per stabilire se un numero k (con ABC...N le sue cifre) è divisibile per 3.
 - se n == 0 mod 3 allora k è divisibile per 3 se e solo se N==0 (mod 3)
 - se n == 1 mod 3 allora k è divisibile per 3 se e solo se (A+B+C+...+N)==0 mod 3.
 - se n == 2 mod 3 e il numero delle cifre di k pari, k è divisibile per 3 se e solo se (A+2B+C+...+N)==0 mod 3. Se il numero delle cifre di k è dispari, allora k è divisibile per 3 se e solo (2A+B+2C+...+N)==0 mod 3.
 
 Chi sa dimostrare questi tre criteri? <IMG SRC="images/forum/icons/icon_biggrin.gif">
 Ciao <IMG SRC="images/forum/icons/icon_smile.gif"> [addsig]

Gauss · Messaggio da **Gauss** » 01 gen 1970, 01:33

Provo a dire qualcosa di definitivo. Sia b la base in cui lavoro, voglio trovare i criteri di divisibilità per un numero N di un numero in base b.
 Intanto itero le seguenti operazioni: prendo Trovo la congruenza di b modulo N, quella di b^2, quella di b^3... etc, fino a quando non ottengo un ciclo di resti che si ripete sempre uguale (questo accade sempre ed è facile mostrarlo). A questo punto so che un numero in base b si può rappresentare come a_n*b^n + a_n-1*b^(n-1)+...+a_1*b + a_0, con a_i intero compreso tra 0 e b. Per le regole delle congruenze il numero sopra scritto sarà congruo modulo N al numero che ottengo sostituendo ai vari b^i i resti delle divisioni di b^i per N. Otterro quindi il numero R=a_n*r_n + a_n-1*r_n-1+...+a_1*r_1 + a_0. Ogni numero n in base b sarà caratterizzato dal suo R(n)_N (N è ilnumero di cui si cerca il crityerio di divisibilità). n sarà quindi divisibile per N lo sarà il suo R(n)_N.

N3o · Messaggio da **N3o** » 01 gen 1970, 01:33

E per quanto riguarda i numeri periodici? Quali frazioni generano numeri periodici in base n?

sergio_vanni · Messaggio da **sergio_vanni** » 01 gen 1970, 01:33

Caro Gauss, ingegnoso ma complicato: un criterio di divisibilità funziona se si è in grado di individuare in via istantanea (o quasi) l\'esistenza della divisibilità stessa. Altrimenti tanto vale provare a fare la divisione!
 Secondo me esistono altri criteri di facile uso che possono essere aggiunti a quelli fin qui elencati da me e dal tuo omonimo.
 Mi riservo di tornare sull\'argomento indicandone di ulteriori.[addsig]

Gauss · Messaggio da **Gauss** » 01 gen 1970, 01:33

La mia non voleva essere la definitiva pietra sull\'argomento divisibilità, ma voleva aiutare nel muoversi all\'interno di questo argomento. Qualsiasi proprietà enunciata riguardo ai criteri di divisibilità può essere dimostrata servendosi del metodo della serie di resti, o perlomeno credo. Per esempio, per quanto riguarda la proprietà che afferma che un numero in base B è divisibile per B/2 se il numero termina o per 0 o per B/2, può essere dimostrata utilizzando una serie R(n)_B. Svolgendo il procedimento si avrà che la suddetta successione sarà formata solo dal termine in a_0, infatti tutti gli altri saranno 0 essendo una potenza di B sempre divisibile per B/2 (B pari). Perchè n sia divisibile per B/2 dovrà esserlo a_0, da questo a_0 potrà essere o 0 o B/2.

sergio_vanni · Messaggio da **sergio_vanni** » 01 gen 1970, 01:33

Credo che lordgauss abbia centrato il punto centrale della questione della divisibilità. Per individuare rapidamente criteri di divisibilità in un qualsiasi sistema di numerazione di ordine \"n\" sono rilevanti tre numeri: n, n-1 ed n+1.
 Rilevanza di n: se n ammette dei divisori (a, b, c,...) allora l\'ultima cifra di un qualsiasi numero N basta per individuare l\'esistenza o l\'assenza della divisibilità. Se l\'ultima cifra è 0 o è divisibile per uno dei divisori di n, allora l\'intero numero N è divisibile per quel divisore. Si vedano, a titolo di esempio, i criteri di divisibilità per 2 e per 5 con riferimento al sistema decimale di numerazione.
 Rilevanza di n-1: Se n-1 ammette dei divisori (d, e, f, ...), allora è la somma delle cifre che compongono il numero N che determina l\'assenza o la presenza di divisibilità per i divisori di n-1. Se la somma delle cifre del numero N è divisibile per uno (o più) dei divisori di n-1, allora anche il numero N è divisibile per quel divisore (o per quei divisori). Questa è una estensione dei criteri di divisibilità per 3 e per 9 ai quali ci ha abituato il sistema decimale.
 Rilevanza di n+1: Se n+1 ammette dei divisori (g, h, i, ...) allora la differenza tra la somma delle cifre dispari e la somma delle cifre pari di un numero N determina sia la divisibilità per n+1 che la divisibilità per i divisori di n+1.
 Il sistema decimale ci ha abituati ad un n+1 che non ha divisori (il numero undici), ma esistono sistemi di numerazione (come il sistema vigesimale (base 20 - mi sembra di ricordare che lo usassero i Maya) nei quali n+1 è un numero che ammette divisori. In questi casi se la differenza fra la somma delle cifre dispari e la somma delle cifre pari di un qualsiasi numero N genera un numero divisibile per uno dei divisori (g, h, i, ...) di n+1, allora il numero N è divisibile per quel divisore di n+1.
 [addsig]

sergio_vanni · Messaggio da **sergio_vanni** » 01 gen 1970, 01:33

Numeri periodici in base n
 
 Nel suo intervento N3o ha sollevato l\'interessante questione dei numeri periodici in base n. Interessante e complicata, perchè gli eventuali calcoli di verifica occorre farseli da soli visto che le calcolatrici scientifiche più diffuse (ad esempio quella incorporata in Windows) non effettuano il calcolo degli \"n_simali\". Ecco come la penso.
 
 Per caspire se una data frazione è capace di generare un numero periodico occorre compiere tre passi:
 1. Calcolare i fattori primi di n (2 e 5, nel sistema decimale; quattro volte 2, nel sistema esadecimale) poichè tali fattori - se inclusi nel denominatore della frazione - non generano numeri periodici.
 2. Calcolare i fattori primi del numeratore della frazione poichè essi elidono, ove esistano, altrettanti fattori primi del denominatore della frazione, impedendo che si generi un numero periodico (ad esempio, nel sistema decimale, 1/7 genera un numero periodico, ma 49/14 non genera un numero periodico).
 3. Calcolare i fattori primi del denominatore ed isolare quelli non elisi dalla procedura 2 e non individuati con la procedura 1:se si individua un qualche fattore primo \"nuovo\" o non eliso, allora la frazione genererà un numero periodico.
 
 Qualche esempio:
 1/3 = 0.333.. (sistema decimale)
 1/3 = 0.4 (sistema duodecimale)
 1/11 = 0. 010101.. (cioè 1/3 nel sistema binario)
 
 Provare per credere!
 __________
 
 Beviti un goccio, guarda il mondo attraverso il bicchiere... E rifletti sulla soluzione cosmica (Paul McCartney)[addsig]

N3o · Messaggio da **N3o** » 01 gen 1970, 01:33

Tutto giusto, Sergio, ma proviamo ad affrontare la questione con un po\' più di rigore: siano a e b due interi primi fra loro, con b>1, se in base n la frazione a/b genera un numero non periodico, esso conterrà un numero finito di cifre dopo la virgola. Supponiamo che siano x.
 Moltiplichiamo il numero periodico per n^x, si tratta in pratica di moltiplicarlo x volte per b. Poiché ad ogni moltiplicazione per b si ottiene l\'effetto di spostare a destra la virgola di una posizione, alla fine avremo un numero intero.
 Quindi, affinché a/b non sia periodico, (a n^x)/b deve essere intero. Poiché b è primo con a, dovrà necessariamente dividere n^x, cioè contenere solo i fattori della base.
 
 Se invece il numero è periodico, quali sono le condizioni affinché abbia anche un antiperiodo? E da cosa di dipende il numero di cifre del periodo e quelle dell\'antiperiodo?