Problemi Normale AA 1988/89 N3

[Sk_Anonymous]

Si considerino i numeri naturali 1, 11, 111, 1111, . . . e, in generale, si in-dichi con α_n il numero che si ottiene giustapponendo n cifre uguali a 1
(a) Si provi che se α_n è un numero primo allora n è primo
b) Si provi che, assegnato comunque un numero naturale r, non divisibile né per 2 né per 5, si può trovare un α_n che è multiplo di r.
c) Si scriva un algoritmo o un programma per calcolatore (in un qualunque linguaggio di programmazione) che, a partire da r, calcoli il minimo n per cui vale la (b).

[Pachisi]

Non so programmare, quindi per la c) non ho niente.

a) Notiamo che possiamo scrivere $a_n=10^(n-1)+10^(n-2)+...+10+1=\frac{10^n-1}{9}$. Supponiamo che $n=xy$ con $x$ e $y$ interi maggiori di 1. Allora, $a_n=\frac{10^(xy)-1}{9}=\frac{(10^x-1)(10^(x(y-1))+10^(x(y-2))+...+1)}{9}$ è un numero composto. Però $a_n$ deve essere primo, dunque abbiamo un assurdo. Segue che se $a_n$ è primo, $n$ deve essere primo.
b) Siano $n>m$ due naturali distinti, allora visto che $a_n mod r$ e $a_m mod r$ variano tra $0$ e $r-1$, possiamo trovare $n$ e $m$ tali che $a_n - a_m = 0 mod r$. Ossia, per qualche intero positivo $t$, $a_n-a_m=rt$. Quindi, $rt=\frac{10^n-1}{9}-\frac{10^m-1}{9}=\frac{10^n-10^m}{9}=\frac{10^m(10^(n-m)-1)}{9}=10^ma_{n-m}$. Visto che $r$ e 10 sono coprimi, $a_{n-m}$ dovrà essere multiplo di $r$.

[Sk_Anonymous]

"Pachisi":Non so programmare, quindi per la c) non ho niente.

non credo sia richiesto un sorgente che "giri" su qualche compilatore o interprete.
credo che basti solo l'algoritmo in un qualsiasi pseudo-linguaggio.
In effetti ce n'è uno molto, ma moooolto elementare

[Sk_Anonymous]

a) Provo una tesi equivalente: la contronominale. Cioè che se $n$ è composto allora $a_n$ è composto.
Sia $n=k*r$, quindi $a_n =a_k(10^{k(r-1)}+ 10^{k(r-2)}+…+ 10^k+1)$

b) Dato $r$, utilizzando uno dei modi indicati nella discussione ne resterà solo uno, si può trovare una potenza del $10$ congrua a $1$ modulo $r$. Sia $10^k$ questa potenza. Il numero $a_k(10^{k(r-1)}+ 10^{k(r-2)}+…+ 10^k+1)$ è multiplo di $r$.

c) ci sono diversi modi di ottenere un $a_n$ multiplo di $r$. Il più elementare risale a quello usato alle scuole omonime. il punto b) assicura che l'algoritmo termina in un numeor finito di passi