Skip to content

Il piccolo di Fermat, googol divisibili per 7 e 360 palline colorate

15 febbraio 2015

Non sempre per lavoro finisco a Madrid. Questa è la volta di Macerata, e poi di una sosta forzata di un’ora causa neve, e poi Arezzo, e poi si torna a Torino in un lungo viaggio in auto. Un po’ guardo dal finestrino e dialogo col compagno di viaggio, ma il tragitto è comunque lungo e finisco per osservare pigramente e lo scorrere dei pensieri.

Piccolo teorema di Fermat

Ho da poco letto una deliziosa dimostrazione combinatoria del Piccolo teorema di Fermat. O meglio, riletto. Perché faccio fatica a digerire i concetti di teoria elementare dei numeri, che trovo affascinanti ma difficili da visualizzare.

Il Piccolo teorema dice che, se prendo un intero n e un numero primo p, allora n^p - n è un multiplo di p. Questo fatto non è evidente, anche perché altrimenti non sarebbe così curioso. Certo, se prendo come intero n un multiplo di p allora il risultato diventa una banalità, ma siccome è vero per qualsiasi valore di n la cosa si fa molto interessante.

Golomb, quello che ha anche inventato i pentamini, propone una dimostrazione combinatoria del teorema. Supponiamo di avere una classe di p bambini. Ogni bambino ha un portapenne contenente pennarelli di n colori diversi, sempre gli stessi per ogni bambino. E’ evidentemente il primo giorno di scuola, e non ci sono pennarelli dispersi.

La maestra chiama tutti i bambini attorno alla cattedra, domandando loro di prendere un pennarello ciascuno e di mettersi in circolo in un certo ordine fisso e stabilito a priori. Il primo bambino può scegliere tra n colori, il secondo pure, il terzo idem. In totale i bambini possono presentarsi alla maestra in n^p modi diversi. In alcuni casi particolarmente sfortunati, tutti i bambini hanno lo stesso colore. Questi casi, che sono esattamente n, vengono ignorati, e tutti i bambini tornano al posto e ripetono la scelta.

L’impostazione così descritta porta ad un numero totale di n^p - n diversi coloramenti del circolo di bambini. Adesso viene il punto focale dell’argomentazione. Ogni bimbo passa il proprio colore al compagno alla sua sinistra, con l’effetto di ruotare il coloramento di un posto. Il nuovo coloramento è necessariamente diverso dal precedente, per il semplice fatto che almeno un bambino riceverà un colore diverso da quello che ha passato. Abbiamo infatti esplicitamente escluso le situazioni aventi un solo colore.

Ma la cosa più sottile è che ad ogni passaggio di colori otteniamo sempre un coloramento diverso, fino a che non saremo ritornati al punto di partenza. Perché non prima? Se l’esatto ordine iniziale dovesse ripetersi prima di un giro completo, vorrebbe dire che la sequenza di colori sarebbe composta di due parti indistinguibili, dando così luogo ad un coloramento di periodo due. In alternativa, la sequenza dei colori potrebbe essere composta da tre o più parti indistinguibili, ritornando così identica a sé stessa dopo un terzo di giro o ancora più frequentemente. Ciò però è in contrasto con l’ipotesi iniziale, cioè che il numero dei bambini è primo, e quindi non divisibile!

Ne concludiamo che ognuno degli n^p - n coloramenti può, per rotazione, essere trasformato in altri p-1. Tutti i coloramenti sono così ripartibili in gruppi di p elementi che sono identici a meno di una rotazione. Che è un altro modo di dire p è un multiplo di n^p - n.

Un esempio concreto

Abbiamo ancora molte ore per arrivare a casa, e il teorema è dimostrato. Dimostrazione molto bella, peraltro, ma sembra di guardare un oggetto in una vetrina fino a che non lo si prende in mano. Cosa può voler dire in un caso concreto? Devo fare i calcoli a mente, quindi per limiti personali mi accontento di un caso piccolo ma non troppo. Dato che posso raccogliere n per avere n(n^{p-1}-1), mi stuzzica l’idea di avere n=p-1. Ad esempio prendo p=7 bambini, o nanetti, e quindi n=6 colori.

Il teorema mi dice che 6(6^6-1) è divisibile per 7. Davvero? Non direi proprio che sia intuibile. Certamente 7 non divide 6, quindi il teorema mi assicura che 6^6-1 è divisibile per 7. Siamo già arrivati? No, e allora continuo oziosamente i calcoli. Il primo passo, tralasciando un secondo il -1, è di scrivere 6^6=36^3.

Il senno di poi è solitamente sottovalutato, pensando che sia troppo comune e di poco valore. In realtà è esperienza preziosa che ci può aiutare per il futuro, è pur sempre senno. Per vedere che 36^3-1 è divisibile per 7 si potrebbe togliere da 36^3 tutti i multipli di 7 possibili, riducendo così il problema ad uno più facile. Nello specifico, 36^3 = (35 + 1)^3 \equiv_7 1^3 \equiv_7 1, cioè dividendo il cubo per 7 il resto è di 1, e allora 36^3-1 è multiplo esatto. Il passaggio (35 + 1)^3 \equiv_7 1^3 scende comodamente espandendo il cubo e osservando che tutti i termini, tranne 1^3, sono multipli di 7 perché contengono almeno il fattore 35 che lo è.

Ma il senno di poi per definizione non è disponibile prima, quindi continuo ostinatamente con i calcoli. Posso fare 36^3 a mente? Ecco, 36^2 è più facile, lo si fa velocemente per confermare il risultato già memorizzato, che è 1296. E adesso ci sarebbe da fare 1296\cdot 36. Uhm.

A pensarci, moltiplicare per 3 sembra facile e moltiplicare per 6 è facile come raddoppiare un numero, quasi quasi ci provo. Allora, 1296\cdot 3 = 3888. Carino, e siccome sto facendo tutto a mente è anche comodo da conservare un attimo in memoria. Il suo doppio è 7776, quindi voglio vedere se 38880 + 7776 - 1 è un multiplo di 7. Solo che sto raggiungendo il limite della memoria mentale e mi sa che fare la somma è troppo difficile. Semplifico perché facilmente 7775 diviso 7 dà resto 5, e mi rimane 38885.

Ecco che arriva la sorpresa, dividere a mente 38885 per 7. Riproduco lentamente i passaggi per condividerne la semplicità: il 7 nel 38 ci sta cinque volte con il resto di 3. Riporto il 3 e abbasso il secondo 8. E siamo punto a capo! Il 7 nel 38\ldots come prima! Riporto il 3 e abbasso il terzo 8. Riporto ancora il 3 e abbasso il 5, e finalmente il 7 nel 35 ci sta un numero intero di volte e la verifica è conclusa.

Prima di farci distrarre completamente dalla divisione particolarmente agevole, volevo completare il discorso sul Piccolo guardando che 3^4-3=81-3=78 non è un multiplo di 4. Una delle ipotesi è che la potenza sia un numero primo, e l’aver preso il 4 impedisce di applicare il teorema. Se cadono le premesse, non necessariamente troviamo un multiplo intero della potenza, proprio come è appena successo.

Dividendo e riportando

Carinamente abbiamo visto che 38885 è un multiplo di 7. Eseguendo il comune algoritmo di divisione, capiamo subito che il numero di 8 inseriti tra il 3 e il 5 è ininfluente: sono multipli di 7 il 385, il 3885, e anche il

3 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 88\_

88 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 8888 5,

che è quasi 39 googol.

E certamente non è l’unico caso. Ad esempio sono divisibili per 8 i numeri 24, 264, 2664, 26664, ecc, e sono divisibili per 6 i numeri 12, 132, 1332, 13332, ecc.

Stiamo dividendo un numero per un altro creando una sequenza di riporti costante, rendendo particolarmente semplice la divisione. Vi invito a cercare altri casi.

In generale, al posto di riportare sempre uno stesso numero, si possono costruire divisioni in cui riportiamo una qualsiasi sequenza di cifre. Ad esempio, dividendo per 9 il numero 10111111111 ottengo in sequenza come riporti tutti i numeri da 1 a 8. Al penultimo passaggio mi avanzano 8, abbasso l’1 e 81 è multiplo di 9, terminando l’operazione.

Altro esempio, dividendo per 9 il numero 17888888888 ottengo in sequenza i riporti dall’8 all’1.

Prendo un numerone e lo divido per 9, in modo che la sequenza dei resti contenga in un qualche ordine tutte le cifre da 1 a 8, ma in modo che due cifre consecutive non appaiano immediatamente l’una dopo l’altra. Tra le varie possibilità, prendo il più piccolo numero di questo tipo. Il risultato della divisione è un altro numero che contiene tutte le cifre positive tranne una. Quale?

Il piccolo di Fermat, googol divisibili per 7 e 360 palline colorate


Quale cifra positiva non compare nell’intero \frac{n}{9} se n è il più piccolo possibile e nell’algoritmo di divisione lunga a mano la sequenza di resti contiene le cifre da 1 a 8 in modo che due cifre consecutive non siano generate in passi consecutivi dell’algoritmo?

Annunci
No comments yet

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: