Primi brutti brutti

[Pigkappa]

Dalle Olimpiadi Nazionale Russe, ha un testo che fa sorridere...

Sia $ \displaystyle p $ un numero primo che ha esattamente 300 cifre, tutte diverse da zero. Definiamo una successione in questo modo:

• - $ \displaystyle a_1 = p $
  - Per ogni $ \displaystyle n\geq 2 $, $ \displaystyle a_{n+1} $ è uguale al doppio del periodo di $ \displaystyle \frac{1}{a_n} $

Determinare $ \displaystyle a_{2003} $

[Marco]

Notazione Dato un intero $ a>1 $, indico con $ \pi(a) $ il periodo di lunghezza minima di $ 1/a $. Indico con $ \lambda(a) $ la lunghezza di tale periodo minimo. Esempio: $ \lambda(7) = 6 $, $ \pi(7)=142857 $.

Fatto 1 Se $ a $ e' un intero positivo coprimo con 10, e $ \lambda $ e' l'ordine moltiplicativo di 10 $ \pmod a $, allora $ \lambda(a) = \lambda $ e
$ \pi(a) = \frac{10^\lambda - 1}{a} $.

Dim.: Segue dall'algoritmo della divisione in colonna. []

Fatto 2 Se $ a $ e $ \lambda $ sono come sopra, e $ a>5 $, allora $ 5/a $ ha pure periodo minimo lungo $ \lambda(a) $ cifre e il periodo e' dato da
$ 5 \pi(a) $.

Dim.: Stessa dimostrazione del Fatto 1, tenendo presente che 5 e' invertibile $ \pmod a $. L'ipotesi $ a>5 $ serve per garantire che non ci sia "overflow" nel moltiplicare per 5.[]

Fatto 3 Moltiplicando o dividendo un numero razionale periodico per 10, il periodo non cambia. []

Lemma chiave Se $ p $ e' primo e contiene almeno una cifra diversa da 0 e 1, allora $ \pi \big( \pi(p) \big) = p $.

Dimostrazione in seguito.

Soluzione
Con la mia notazione si ha che
$ a_1 = p $
$ a_{n+1} = \pi\left(2 a_n \right) $.

Dimostro per induzione che nella successione, i termini di posto dispari sono tutti $ p $.

Intanto noto che $ p $ e' maggiore di 5, non ha cifre 0 e non e' fatto da sole cifre 1 (ha esattamente 300 cifre, e se fossero 300 cifre 1, sarebbe divisibile per 11).

Sia $ a_n=p $.

Tenendo presente il Fatto 3, si ha che $ a_{n+1} $ e' anche il periodo di $ 5/p $ e, per il fatto 2, $ a_{n+1} = 5 \pi(p) $.

A questo punto, $ a_{n+2} = \pi \big( 10 \pi(p) \big) $. Per il fatto 3, cio' vale $ \pi \big( \pi(p) \big) $; per il lemma chiave, $ a_{n+2} = p $. []

Dim. del lemma chiave
Sia $ q = \pi(p) $. Per il Fatto 1, posso dire che

$ pq = 10^{\lambda(p)} - 1 $

Ne segue che $ 1/q $ ha un periodo - non necessariamente di lunghezza minima - lungo $ \lambda(p) $.

Dico che non esistono periodi piu' corti. Infatti: sia $ t $ t.c.

$ qt = 10^{\lambda(q)} - 1 $.

Risolvendo per $ p $, per un opportuno $ z $, si ha

$ p = \frac{10^{\lambda(p)} -1}{10^{\lambda(q)}-1} t = zt $. (**)

$ z $ e' intero, infatti ho osservato prima che $ 1/q $ ha un periodo di lunghezza $ \lambda(p) $, quindi $ \lambda(p) $ e' un multiplo di $ \lambda(q) $. Ne segue che la frazione che compare in (**) in verita' e' impropria, dato che

$ z = \frac{10^{\lambda(p)} -1}{10^{\lambda(q)}-1} = 1 + 10^{\lambda(q)} + 10^{2 \lambda(q)} + \cdots + 10^{\lambda(p)-\lambda(q)} $.

Quindi, in (**) ho scritto $ p $, che e' primo, come prodotto di due interi positivi. Ne segue che uno dei due deve essere 1.

Non puo' essere $ t=1 $. Se lo fosse, si avrebbe $ p=z $. Ma $ z $ e' un numero che si scrive con sole cifre 0 e 1, quindi non soddisfa le ipotesi del lemma.

Allora $ z=1 $ e $ \lambda(q) = \lambda(p) $. Il resto segue dal Fatto 1. []

-------------------------

Notate che le ipotesi sulle cifre di $ p $ sono necessarie. Il controesempio piu' semplice e' per $ p=11 $.

$ \pi(11) = 9 $, ma $ \pi(9) = 1 $.