Reszta z dzielenia liczby nie są względnie pierwsze.

[Vardamir]

Mam następujące pytanie odnośnie reszty z dzielenia dwóch liczb, które nie są względnie pierwsze.

Na przykład \(\displaystyle{ r_{35}(7^{320})}\) . Oczywiście znam Małe Twierdzenie Fermata i jego uogólnienie poprzez funkcję Eulera. Ale tutaj nie mają zastosowań.

Zauważyłem, że \(\displaystyle{ r_{35}(7^{320})=7\cdot r_{5}(7^{319})}\). Tylko dlaczego tak się dzieje? Zapewne jest jakieś proste uzasadnienie.

[Zordon]

\(\displaystyle{ 7^{320}=35k+r}\) dla \(\displaystyle{ 0\leq r<35}\)
Lewa strona i \(\displaystyle{ 35k}\) sa podzielne przez \(\displaystyle{ 7}\) zatem \(\displaystyle{ r}\) jest postaci \(\displaystyle{ 7r'}\)
\(\displaystyle{ 7^{320}=35k+r=35k+7r'}\) dla \(\displaystyle{ 0\leq r'<5}\)
\(\displaystyle{ 7^{319}=5k+r'}\)

To takie elementarne wyprowadzenie, ale raczej tak nikt na to nie patrzy. Lepiej zapoznać się z teorią kongruencji modularnych, tam mamy w szczególności chińskie tw. o resztach, które wyjaśnia podobne zjawiska.

[Vardamir]

O coś takiego raczej chodzi.

Nie mieliśmy na wykładzie teorii kongruencji, ani chińskiego twierdzenia o resztach. A takie zadanie pojawiło się mimo to na liście zadań.