Problema Scuola Galileiana

'' È dato un numero primo p diverso da 1,2 e 5 e si considerano le sue potenze p,p^2, ... ,p^999. Mostrare che, necessariamente: almeno una di queste potenze di p, scritta in notazione decimale deve terminare con le cifre 001. ''

Si può notare chiaramente che ad ogni p, per ogni esponente multiplo di 4 ( ex: p^0, p^4, etc), la potenza termina per 1.
Dopo ciò non saprei come iniziare la dimostrazione. Qualche suggerimento o metodo particolare da utilizzare per esercizi del genere?

Ho trovato due modi per risolverlo. Il primo con Eulero ($n=1000$), l'altro osservando che $p, p^2, p^3, \cdots, p^(999)$ sono 999 numeri da qui discendono due casi:
1) I 999 numeri danno resti distinti e quindi almeno uno di quelli da resto 1 dividendolo per 1000
2) Almeno due hanno lo stesso resto ovvero siano $m>n$ naturali risulta $1000| p^m-p^n$ cioè $1000| p^n(p^{m-n}-1)$ necessariamente $1000|p^{m-n}-1$ e quindi $p^{m-n}$ è una delle potenze che soddisfano la richiesta.

E come si risolverebbe con Eulero? (Scusami se te lo chiedo, ma non l'ho mai ''utilizzato'')

Afferma che dati $a$ e $n$ coprimi risulta $a^{\varphi(n)}-=1 \mod n$ dove $\varphi(n)$ conta i numeri minori di $n$ coprimi con $n$ . Dire che $p^k$ termina con 001 è la stessa cosa che dire che $p^k-= 1\mod 1000$, ora scegliamo $n=1000$, $a=p$ diverso da 2 e 5 così che sia coprimo con 1000 e $k=\varphi(1000)=900$