Ostatnie cyfry wielkich liczb

[etyre]

Cześć.
Ostatnimi czasy natrafiłem na kilka zadań o treści mniej więcej takiej: Wyznacz x ostatnich cyfry liczby n. Zastanawia mnie, jak mogę takie zadania rozwiązywać, czego używać etc.?

Jak np. zrobić te przykłady:
1. Wyznacz 2 ostatnie cyfry liczby \(\displaystyle{ 23!}\)
2. Jaka jest ostatnia cyfra wyrażenia \(\displaystyle{ {2008 \choose 10}}\) ?

i w podobnym klimacie:
3. Mamy liczbę, np. \(\displaystyle{ 100!}\). Sumujemy wszystkie cyfry, otrzymując pewną liczbę. Cyfry tej liczby też sumujemy i tak dalej. Jaka będzie pierwsza jednocyfrowa liczba, którą otrzymamy?

Dzięki za pomoc

[atimor]

Możesz spróbować z kongruencjami, bo przecież x ostatnich cyfr liczby n, to nic innego, jak reszta z dzielenia n przez \(\displaystyle{ 10^{x}}\).

[etyre]

Wielokrotnie widziałem zastosowania kongruencji w zadaniach na ostatnie x cyfr. Z tymże, dla takich dużych liczb może być trochę problemów w dostosowaniu kongruencji, więc jestem ciekawy, czy jest może inny sposób/sposoby?

[smigol]

ponieważ w rozkładzie liczby 23 na czynniki występuje
2 i 5 czyli ostatnią cyfrą jest 0
ponieważ występuje też 4 i 10
to mamy 2*2*2*5 i znów musi być podzielna przez 10, czyli reasumując jest podzielna przez 100więc dwie ostatnie cyfry liczby 23! to dwa zera.
podobnie z drugim
mamy 1999*2000*...*2008
2000 jest podzielne przez 10, a zatem i liczba 1999*2000*...*2008 jest podzielna przez 10, zatem ostatnią cyfrą tego wyrażenia jest o.

[timon92]

3. Operacja dodawania cyfr liczby zachowuje resztę z dzielenia przez 9, więc startując od liczby 100! dostaniemy dziewiątkę

[etyre]

timon92, byłbym wdzięczny, jakbyś rozwinął swoje sformułowanie (czyt. bardziej łopatologicznie) . Gdzie mogę znaleźć takie ciekawe i jakże przydatne fakty z teorii liczb, jak np. ten od timona92?

[6hokage]

Każda potęga 10 daje resztę 1 przy dzieleniu przez 9, zatem każda liczba postacii \(\displaystyle{ n10 ^{k}}\)
daje resztę n przy dzieleniu przez 9. Każdą liczbę da się przedstawić w postaci sumy : \(\displaystyle{ a_110 ^{k}+a_210 ^{k-1}..+a_k}\) gdzie liczby a1,a2,....ak to cyfry tej liczby w zapisie dziesiętnym.
Zatem jeśli
\(\displaystyle{ n=a_110 ^{k}+a_210 ^{k-1}..+a_k}\)

to \(\displaystyle{ n=a_110 ^{k}+a_210 ^{k-1}..+a_k \approx a_1+a_2+...a_k(modulo 9)}\)

Więc jeśli \(\displaystyle{ n \approx 0(modulo 9)}\) to \(\displaystyle{ a_1+a_2+...a_k \approx 0(modulo 9)}\)
czyli suma cyfr liczby podzielnej przez 9 jest podzielna przez 9.
100! jest podzielne przez 9.
Spróbuj teraz zrobić 3 zadanie.