Wykaż podzielność przez 19

[anka35155]

Witajcie,
potrzebuję do dalszej części zadania wykazać następującą zależność: liczba \(\displaystyle{ 3 ^{64}+3}\) ma być podzielna przez \(\displaystyle{ 19}\). Jak to pokazać? Z góry dziękuję za pomoc
Anka

[Pakro]

Na mocy tw. Eulera \(\displaystyle{ 19}\) dzieli \(\displaystyle{ 3^{18}\equiv 1 \pmod{19}}\). Zatem również \(\displaystyle{ (3^{18})^3=3^{54}\equiv 1 \pmod{19}}\). Mamy również \(\displaystyle{ 3^{10}=(3^3)^3 \cdot 3 \equiv 8^3 \cdot 3 \equiv 64 \cdot 8 \cdot 3\pmod{19}\equiv 7\cdot 8 \cdot 3 \pmod{19} \equiv 16 \pmod{19}}\)
Ostatecznie:
\(\displaystyle{ 3^{64}+3=3^{10} \cdot 3^{54} +3\equiv 16+3\pmod{19}\equiv 0 \pmod{19}}\)