Grafi per controllo del resto modulo N (in base b)
Uso dell'applicazione
L'applicazione genera grafi per il controllo del resto della divisione per N di numeri scritti in base b.
Cambiando i due parametri (N e b) viene generato il relativo (doppio) grafo.
Le classi di resto modulo N (classi di equivalenza, rappresentate dai numeri da 0 a N-1) sono messe in cerchio, collegandole idealmente l'una all'altra con l'operazione .
Le stesse classi sono collegate da un secondo grafo (rosso tratteggiato) secondo l'operazione , dove b è la base.
Uso del grafo
Il grafo generato può essere usato per calcolare il resto della divisone per N di un numero scritto in base b. Quindi, può essere usato come metodo di controllo della divisibilità (resto 0) per moduli per i quali non c'è un criterio semplice, ad esempio 7 o 13.
Per calcolare il resto, si legge il numero scritto in base b dalla cifra più significativa verso la meno significativa. Partendo dal nodo 0 del grafo, si legge la prima cifra e si fanno tanti passi lungo la circonferenza quanti indicati dalla cifra. Per passare alla cifra successiva, si segue una singola volta la freccia del grafo rosso tratteggiato e nuovamente si fanno tanti passi lungo la circonferenza quanti indicati dalla nuova cifra. Quando da un nodo non parte alcuna freccia rossa, al relativo passaggio non si effettua nessuno spostamento.
Il nodo finale indica il resto della divisione per N del numero.
Esempio di uso del grafo
Supponiamo di voler verificare se il numero 135947 sia divisibile per 7:
- generiamo il grafo con N=7 per la base b=10 e partiamo dal punto 0;
- facciamo 1 passo fino al punto 1;
- seguiamo la freccia rossa da 1 a 3 (il resto di 10);
- facciamo 3 passi fino al punto 6 (il resto di 13);
- seguiamo la freccia rossa da 6 a 4 (il resto di 130);
- facciamo 5 passi fino al punto 2 (il resto di 135);
- seguiamo la freccia rossa da 2 a 6 (il resto di 1350);
- facciamo 9 passi (un giro più 2) fino al punto 1 (il resto di 1359);
- seguiamo la freccia rossa da 1 a 3 (il resto di 13590);
- facciamo 4 passi fino al punto 0 (il resto di 13594);
- non c'è alcuna freccia rossa che parte da 0, quindi restiamo su 0 (il resto di 135940);
- facciamo 7 passi (un giro completo) tornando al punto 0 (il resto di 135947).
Come funziona il metodo
Siamo abituati a pensare al numero scritto in base b, come una somma di cifre moltiplicate per le rispettive potenze della base, ad esempio possiamo vedere un numero di 6 cifre come:
.
Ovverosia, possiamo vederlo come un polinomio con le cifre per coefficienti, che viene valutato nella base.
Il funzionamento del metodo descritto sopra, si vede meglio pensando di valutare il polinomio con l'algoritmo di Horner, ovverosia come segue:
.
Ebbene, il metodo descritto sopra equivale a valutare il numero con l'algoritmo di Horner, un'operazione alla volta, guardando di volta in volta il risultato nelle classi di resto modulo N. Sommare ci equivale ad eseguire ci passi lungo la circonferenza; moltiplicare per b equivale a seguire una freccia del grafo rosso tratteggiato.
Provate il funzionamento!
Il numero seguente è scritto in base 8: 642135. È divisibile per 5?
Analizzare le simmetrie
Il (doppio) grafo è simmetrico?
Studiate le simmetrie
Come viene il grafo ponendo N=9 e b=10? Perché? A quali condizioni succede?
Come viene il grafo ponendo N=11 e b=10? Perché? A quali condizioni succede?
Come viene il grafo ponendo N=18 e b=10? Perché? A quali condizioni succede? (*)
Guardate il grafo che si ottiene con N=7 e b=10?, poi con N=7 e b=3. Cosa si nota? A quali condizioni succede?
Guardate il grafo che si ottiene con N=19 e b=10, poi con N=19 e b=2. Cosa si nota? A quali condizioni succede? (*)
Guardate il grafo che si ottiene con N=19 e b=14, poi con N=19 e b=15. Cosa si nota? C'è qualcosa in comune col caso precedente? Si riescono a trovare altre coppie, non necessariamente di numeri consecutivi? Nell'esempio dato, si guardi dove portano le frecce che partono dai nodi 15 e 14... (**)
Guardate il grafo che si ottiene con N=13 e b=6. Provate a partire dal nodo 1 e seguire le frecce del grafo rosso tratteggiato. Cosa si nota? Per quali valori di N si riesce a trovare un b con queste proprietà? (***)
Cercate altre configurazioni notevoli e cercate di giustificarle/generalizzarle.