Domanda sui criteri di divisibilità in altre basi

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Domanda sui criteri di divisibilità in altre basi #43325

avt
Dennis
Banned
Ciao, questi esercizi sui criteri di divisibilità mi stanno uccidendo.

Sulle mie dispense leggo che un numero m in base 10 è divisibile per 8 se e solo se è divisibile per 8 il numero formato dalle ultime tre cifre di m e si ha  m\equiv c_2[10]^2+c_1[10]+c_0 (mod8) ora io ho il numero in base 7 e quindi immagino che sarà  m\equiv c_2[7]^2+c_1[7]+c_0 (mod8) .

Il mio numero è 103210002100112310021200100310_7 le sue ultime tre cifre sono 310 e quindi avrò  m\equiv 3[7]^2+1[7]+0 (mod8) ,  m\equiv 154 (mod8) ma  154 (mod8)=2 quindi verrebbe che il numero non è divisibile per 8 e da resto 2.

Ma se io converto il mio numero dalla base 7 alla base 10 e faccio il modulo con 8 mi viene resto 0 cioè che è divisibile per 8.

3437160069360227247604672(mod8)=0
 
 

Domanda sui criteri di divisibilità in altre basi #43399

avt
Galois
Coamministratore
Ciao Dennis.

Purtroppo i criteri di divisibilità, in quanto operano direttamente con le cifre del numero, non possono essere generalizzati per le varie basi, ma valgono solo e soltanto per la base 10. Capirai bene infatti che nel cambio da una base all'altra le cifre vengono completamente stravolte.

Tu, nel tuo modo di procedere, praticamente, se andiamo a vedere che hai fatto hai convertito il 310 (le ultime tre cifre del numero che avevi) dalla base 7 alla base 10 e poi verificato col criterio (per la base 10) se il numero è divisibile per 8.

Questo procedimento va bene.. però tu lo hai applicato al numero 310(in base 7) o 154 (in base 10) ma non a tutto il numero di partenza..

Non so se ho reso bene l'idea..

Chiedi pure se hai dubbi emt
Ringraziano: Omega, Pi Greco

Re: Domanda sui criteri di divisibilità in altre basi #43490

avt
Dennis
Banned
Grazie Galois, è quello che avevo pensato anche io, ma allora come si risolvono questo tipo di esercizi?Come trovo il resto della divisione per 8 e per 6 del mio numero in base 7?
e quando ho altre basi?

Re: Domanda sui criteri di divisibilità in altre basi #46707

avt
Galois
Coamministratore
Salve ragazzi. E' da un bel po' che ci penso, e finalmente credo di essere giunto ad una conclusione (ne approfitto oggi per scriverla vesto che il forum è chiuso e sono più libero emt).. Mi dispiace che l'utente che ha posto la domanda sia stato (anche se giustamente) bannato, ma voglio rispondere comunque con la speranza di aiutare eventuali ospiti e/o utenti che hanno lo stesso problema emt

Ovviamente non prendete come oro colato quello che leggerete.. anzi spero in eventuali conferme e/o smentite ... l'argomento è più che delicato ... ci proponiamo infatti di dire se dato un numero a in base n, con n \neq 10, è divisibile per un numero k (sempre in base n).

In altre parole, nella base 10 per dire se un numero è divisibile per un altro numero ci vengono in aiuto i criteri di divisibilità.. ma nelle altre basi? Di certo non si possono utilizzare gli stessi criteri, infatti essi operano direttamente con le cifre del numero, e NON possono essere generalizzati per le varie basi, infatti nel cambio da una base all'altra le cifre vengono completamente stravolte!

Ad esempio, sappiamo che un numero in base 10 è divisibile per 2 se è pari.

Bene, prendiamo il numero 12_{7} e volessimo dire se è divisibile o meno per 2, utilizzando lo stesso criterio di divisibilità per la base 10 saremmo tentati a dire che 12_{7} è divisibile per 2. [N.B: 2_{10}=2_{7}]

Ma 12_{7} = 9_{10} che ovviamente non è divisibile per 2!

Questo piccolo esempio ci conferma quindi che i criteri di divisibilità valgono solo e soltanto per la base 10.

Ci proponiamo quindi di determinare un procedimento grazie al quale dire se un numero (in una qualunque base) è divisibile per un altro (ovviamente sempre nella stessa base)

A tele scopo vorrei chiamare l'Algoritmo Euclideo (che è uno dei primi argomenti che si tratta in un corso di Algebra)

In parole povere, l'algoritmo euclideo prevede di sottrarre dal numero maggiore quello minore tante volte quanto possibile e di continuare fino ad ottenere 0 o 1 (nel primo caso l’ultimo risultato trovato è il MCD, nell'altro sono primi tra loro.

Facciamo un esempio.
Prendiamo i numeri 506_{10} \ e \ 407_{10}

Ora:

506_{10} - 407_{10} = 99_{10}

407_{10} - 99_{10} = 308_{10}

308_{10} - 99_{10} = 209_{10}

209_{10} - 99_{10} = 110_{10}

110_{10} - 99_{10} = 11_{10}

99_{10} - 11_{10} = 88_{10}

88_{10} - 11_{10} = 77_{10}

77_{10} - 11_{10} = 66_{10}

66_{10} - 11_{10} = 55_{10}

55_{10} - 11_{10} = 44_{10}

44_{10} - 11_{10} = 33_{10}

33_{10} - 11_{10} = 22_{10}

22_{10} - 11_{10} = 11_{10}

11_{10} - 11_{10} = 0_{10}

Quindi, per l'algoritmo euclideo, possiamo dire che mcd(506,407)=11

Io nel precedente esempio (per far capire bene come funziona) ho fatto tutte le sottrazioni, ma ovviamente nulla vieta di sottrarre al numero più grande un multiplo del più piccolo fino ad ottenere un numero più piccolo di quello che si sottrae.

Ad esempio, invece di fare:

407_{10} - 99_{10} = 308_{10}

308_{10} - 99_{10} = 209_{10}

209_{10} - 99_{10} = 110_{10}

110_{10} - 99_{10} = 11_{10}

Si sarebbe potuto fare direttamente:

407_{10} - 4*(99_{10}) = 11_{10}

Ora, a cosa ci serve tutto questo?

trovare il massimo comun divisore tra due numeri, vuol dire trovare il divisore comune tra i due numeri, ovvero sapere per quale numero (comune) son divisibili i due numeri di partenza e quindi, tramite questo metodo, possiamo dire se un numero è divisibile per un altro!

Ad esempio, nella base 10, supponiamo di non conoscere il criterio di divisibilità per 8 e vogliamo vedere se il numero 156 è divisibile per 8.

Procediamo come prima:

156 - 8 = 148
148 - 8 = 140
140 - 8 = 132
132 - 8 = 124
124 - 8 = 116

..e così via..

12-8=4 (siamo arrivati ad avere un numero minore di 8, quindi continuiamo):
[Ovviamente avremmo potuto sottrarre direttamente 8*19=152]
8-4 = 4
4-4 = 0

ne segue che mcd(156,8) = 4 e quindi 156 non è divisibile per 8!

Se lo stesso procedimento lo facciamo per il numero 160 arriviamo ad avere:

160-8 = 152
152-8 = 144

e così via...

8-8=0

e quindi mcd(160,8)=8.. ne segue quindi che 160 è divisibile per 8!

Ora, l'algoritmo euclideo vale in ogni contesto in cui è possibile eseguire la divisione col resto, quindi NON SOLO PER LA BASE 10!

Ed ecco quindi che abbiamo trovato un modo per determinare se un numero è divisibile per un altro in una qualunque base!

Ci proponiamo ad esempio di determinare se il numero 143_{7} è divisibile per 8.

Innanzitutto essendo 8>7, convertiamo l'8 dalla base 10 alla base 7.

8=11_{7}

E procediamo come sopra, facendo attenzione però che ora le operazioni vanno eseguite in base 7, quindi nelle sottrazioni e nelle eventuali moltiplicazioni dobbiamo star attenti a non fare macelli emt

143_{7} - 11_{7} = 132_{7}

132_{7} - 11_{7} = 121_{7}

Possiamo sottrarre in blocco 11_{7}*5_{7} = 55_{7} e quindi:

121_{7} - 55_{7} = 33_{7}

55_{7} - 33_{7} = 22_{7}

33_{7} - 22_{7} = 11_{7}

22_{7} - 11_{7} = 11_{7}

11_{7} - 11_{7} = 0


Quindi

11_{7} = mcd (143_{7} e 11_{7}),

ovvero 143_{7} è divisibile per 11_{7}=8_{10} !!!!

emt emt emt

Certo, potrebbe sembrare un po' laborioso, anzi lo è.. ma con un po' di pratica diventa più semplice e per numeri molto grandi richiede di certo l'uso di una calcolatrice..

Ma altri metodi non mi son venuti in mente emt

Questo funziona e in fin dei conti è facilmente comprensibile! (spero emt )

Come detto sopra spero in eventuali conferme e/o smentite!

emt emt emt
Ringraziano: Pi Greco
  • Pagina:
  • 1
Os