KONGRUENCJE

[tukan]

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

I teraz w rozwiązaniu jest:

\(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 \(5^m,\) a \(10^m\) ma ich więcej.

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

[Panko]

Najprościej : w zadaniu rządzi \(\\) \(\\)\(m\).

Oznaczmy \(L (5^m)\) to liczba cyfr liczby \(5^m\)
\(L(5^m) \le L(10^m)\) dokładnie \(\\) \(1+ [m \cdot \log 5] \le m+1\)
Czyli w \(m+1\) ostatnich cyfrach liczby \(5^n\) można zmieścić cyfry liczby\(\\) \(5^m\).

Co widać na obrazku poniżej : \(5^{12} \equiv\)\(5^4\)\((\) \(mod\) \(10^4\) \()\) . Czyli dla \(m=4\)

Bo \(\\) \(5^{12}= 24414\)0625 , gdzie \(5^4=625\)

[octahedron]

Takie obustronne dzielenie nie jest tutaj prawidłowe. Można to rozwiązać tak:

\(5^n\equiv 5^m\pmod{10^m}\Rightarrow\begin{cases}5^n\equiv 5^m\pmod{5^m}\\5^n\equiv 5^m\pmod{2^m}\end{cases}\Rightarrow\begin{cases}n>m\\5^{n-m}\equiv 1\pmod{2^m}\end{cases}\\\)

i np. dla \(n=2m\) jest to spełnione

[tukan]

(1) Czy ta równoważność (rozbicie na układ kongruencji) wynika z chinskiego tw ?
(2) Czy to prawda: zawsze można podzielić obie strony i modulnik przez ten sam dzielnik
(3) Czy to prawda: można podzielić obie strony przez liczbę względnie pierwszą z modulnikiem
(4) Nadal nie rozumiem skąd wiadomo, że liczba \(5^m\) ma \(m\) cyfr ?

[octahedron]

1) To nie jest równoważność, tylko oczywista implikacja, wstawiłem niewłaściwe strzałki.
2) Tak
3) Tak
4) Na pewno \(5^m\) mieści się w \(m\) cyfrach. Jeśli jakieś cyfry są wolne, to w \(5^n\) będą to zera.