kongrunecja - pytanie co do zadania.

[matinf]

Wykazać, że dla każdej liczby naturalnej m istnieje taka liczba naturalna n, że w zapisie
dziesiętnym liczb \(\displaystyle{ 5^m}\)oraz\(\displaystyle{ 5^n}\) zapis dziesiętny\(\displaystyle{ 5^n}\)kończy się zapisem dziesiętnym \(\displaystyle{ 5^m}\)

I teraz w rozwiązaniu jest:

\(\displaystyle{ 5^n \equiv 5^m (\mod 10^m)}\)
Dlaczego taki modulnik ? Ja sie zgodzę że musi być potega 10tki - wszak chcemy wyłuskać ostatnie cyfry - ale potęga powinna wynieść dokładnie tyle ile ma cyfr \(\displaystyle{ 5^m,}\) a \(\displaystyle{ 10^m}\) ma ich więcej.

Ponadto, dlaczego \(\displaystyle{ 5^n \equiv 5^m (\mod 10^m)}\) legalne jest podzielenie stronami przez \(\displaystyle{ 5^m}\) ?

[Hydra147]

Modulnik jest dobry. Zauważ: to do czego przystaje liczba (dodatnia) modulo \(\displaystyle{ 10}\) to jej ostatnia cyfra. Podobnie to do czego przystaje modulo \(\displaystyle{ 10^{n}}\) to jej ostatnie \(\displaystyle{ n}\) cyfr (a raczej liczba z nich utworzona). Co do podzielenia kongruencji stronami to można tylko wtedy, gdy liczba przez którą chcesz podzielić jest względnie pierwsza z modulnikiem (czyli w sposób proponowany przez Ciebie nie możesz). Zrób to tak:
\(\displaystyle{ 5^n \equiv 5^m (\mod 10^m) \Rightarrow 10^{m}| 5^{n}- 5^{m} \Rightarrow 2^{m}| 5^{n-m} -1}\).

[matinf]

No wszystko co mówisz jest jasne.

Ale zobacz:
Chcemy, żeby \(\displaystyle{ 5^n}\) kończyło się liczbą \(\displaystyle{ 5^m}\). Czyli, żeby :
\(\displaystyle{ 5^n \equiv 5^m (\mod 10^{a})}\)
Gdzie \(\displaystyle{ a}\) jest liczbą cyfr liczby \(\displaystyle{ 5^m}\). A kto powiedział, że ta liczba ma \(\displaystyle{ m}\) cyfr ?

[Hydra147]

Aaa, nie zrozumiałem po prostu twojego pytania ale OK. Weź sobie prosty przykład do tego twierdzenia. Niech \(\displaystyle{ m=4}\) czyli chcemy znaleźć taką liczbę \(\displaystyle{ n}\), aby \(\displaystyle{ 5^n \equiv 625 (\mod 10000)}\). Moglibyśmy wziąć \(\displaystyle{ 1000}\) ale jeśli weźmiemy większy modulnik to nic się nie stanie. Zależy nam co prawda, aby trzy ostatnie cyfry pewnej potęgi piątki różnej od \(\displaystyle{ 625}\) kończyły się cyframi \(\displaystyle{ 625}\), ale przecież jeżeli wykażemy, że istnieje taka, która kończy się cyframi \(\displaystyle{ 0625}\) to nic się nie stanie. Nie zależy nam bowiem na znalezieniu najmniejszego \(\displaystyle{ n}\), jakim jest w tym przypadku \(\displaystyle{ 6}\) (\(\displaystyle{ 5^{6}=15625}\)), a na znalezieniu jakiegoś w ogóle. Znajdujemy np. takie: \(\displaystyle{ 5^{8}=390625}\), które kończy się na \(\displaystyle{ 0625}\) ale nas interesuje tylko samo \(\displaystyle{ 625}\). Mam nadzieję, że rozumiesz o co mi chodzi. Wzięcie większego modulnika nie sprawia, że nasz dowód staje się nieprawdziwy, a wręcz niejako wzmacnia naszą tezę.

[matinf]

Dzięki.