Matematyka.pl

Zadanie jest nastepujace:
Udowodnij, ze dla kazdej liczby naturalnej s > 0 istnieje podzielna przez s liczba o sumie cyfr równej s.

Próbowałem to ruszyć udowadniajac, ze istnieje taka liczba k, ze suma cyfr k jest rowna s, oraz po pewnej liczbie dołożen zera na jej koniec, k bedzie podzielna przez s - czyli inaczej znalezc cykl modulo s przy mnozeniu k przez 10. Niestety to chyba nie jest dobry pomysł? Mógłby mnie ktoś nakierować?

nie wiem jak nakierować, bo to jest trikowe..

\(\displaystyle{ s=2^p\cdot 5^q\cdot r}\), dzięki czemu mamy \(\displaystyle{ \nwd(r,10)=1}\), czyli korzystamy z twierdzenia Eulera: \(\displaystyle{ 10^{\phi(r)}\equiv_{r}1}\)

to może dalej sam spróbuj? jakoś dostać z tego sumę cyfr równą \(\displaystyle{ s}\), jednocześnie liczbę podzielną przez \(\displaystyle{ r}\), a podzielnością przez \(\displaystyle{ 2^p\cdot 5^q}\) można zając się na koniec dokładając odpowiednią ilość zer, co nam nie popsuje sumy cyfr..