backup del Post

Solo con zero e uno

Immagino sia noto a tutti che se un numero ha come fattori primi solo 2 e 5, esiste un suo multiplo che è una potenza di 10. Sapete anche tutti che 111 è un multiplo di 3, e 111.111.111 un multiplo di 9. Combinando quelle proprietà, vediamo anche che 1110 è un multiplo di 6, e magari ricordate anche che 1001 è multiplo di 7, di 11 e di 13, essendo il loro prodotto. A questo punto potrete magari chiedervi se è vero o no che dato un qualunque numero intero ci sia un suo multiplo che contenga solo le cifre 1 e 0. Che ne dite?

La risposta è affermativa, e una possibile dimostrazione sfrutta una proprietà che potrebbe sembrare fuori luogo in questo caso: il principio dei cassetti, quello che afferma che se metto k+1 calzini in k cassetti allora almeno un cassetto conterrà due calzini. (Ne avevo parlato qui sul Post). Dato un numero qualunque n, prendiamo i numeri 1, 11, 111, … fino a quello composto da n+1 cifre 1, e consideriamo il resto della divisione per n di ciascuno di questi numeri. Otterremo n+1 risultati, tutti compresi per definizione tra 0 e n−1, e quindi al più di n valori diversi; per il principio dei cassetti almeno due di tali resti, diciamo quello del numero con p cifre e di quello con q cifre, devono pertanto avere lo stesso valore. Per fissare le idee immaginiamo che p>q e che il resto comune della divisione dei due numeri per n sia r. A questo punto basta prendere i due numeri corrispondenti e sottrarli tra loro: avremo un numero della forma 111…111000…000, con p−q 1 e q 0, che per costruzione è multiplo di n. Infatti esso è la differenza di un multiplo di n più r, e di un altro multiplo di n sempre più r; possiamo raccogliere insieme i due multipli ed eliminare gli r.

Chi ha studiato matematica un po’ più avanzata (a livello universitario di base) e conosce la funzione totiente φ(n) (il numero di numeri inferiori a n e primi con esso) e il Piccolo teorema di Fermat nella generalizzazione di Eulero, che afferma che se a è primo con n allora a^φ(n) ≡ 1 (mod n) può anche calcolare una stima superiore per il numero minimo di cifre di un tale multiplo. Se n è primo con 10, infatti, sappiamo che 10^φ(9n) ≡ 1 (mod 9n), e pertanto (10^φ(9n)−1)/9 è composto da φ(9n) cifre 1. Se invece n è della forma 2^a5^b, a seconda se a è maggiore o minore di b lo possiamo moltiplicare per 5^a−b o 2^b−a e ottenere una potenza di 10 (se a=b la potenza ce l’abbiamo già). Combinando i due risultati possiamo dire che un limite superiore per il numero di cifre del multiplo è φ(9n)|a−b|.