Matematyka.pl

Mam obliczyć resztę z dzielenia przez \(\displaystyle{ 13}\) liczby \(\displaystyle{ 2016^{2015}}\).

Oczywiście w tym celu wykorzystuję kongruencje i działanie \(\displaystyle{ \pmod{13}}\).
Akurat \(\displaystyle{ 13 | 2016}\). Czy to oznacza wtedy, że mogę zapisać: \(\displaystyle{ 2016^{2015} \equiv 2016^{0} \equiv 1}\) i mam już gotowy wynik?

Ale trzynastka nie dzieli \(\displaystyle{ 2016}\), bo \(\displaystyle{ 2016 = 13 \cdot 155 + 1}\). Rozwiązanie wygląda więc tak:

\(\displaystyle{ 2016^{2015} \equiv 1^{2015} \equiv 1 \pmod {13}}\).

Chodziło mi o to, że trzynastka dzieli \(\displaystyle{ 2015}\). Zrobiłam literówkę. Miałoby być \(\displaystyle{ 13 | 2015}\).

Wygląda to tak, jakbyś chciała skorzystać z własności: jeśli \(\displaystyle{ x\equiv y\pmod{m}}\), to \(\displaystyle{ a^x\equiv a^y\pmod{m}}\), a taka własność nie jest w ogólności prawdziwa. Sprawdź sobie sama na jakichś małych liczbach.

No faktycznie nie jest, więc ten sposób odpada..

Ale za to implikacja \(\displaystyle{ a \equiv b \Rightarrow a^k \equiv b^k}\) jest prawdziwa.

Tak, i z tego skorzystała Medea 2.

Weź \(\displaystyle{ x = 9}\), \(\displaystyle{ y = 18}\), \(\displaystyle{ a = 2}\) i \(\displaystyle{ m = 9}\). Wtedy \(\displaystyle{ \textstyle a^y - a^x = 261632 = 29070 + \frac 29}\).

Inny kontrprzykład, mniejszy: \(\displaystyle{ x = 1}\), \(\displaystyle{ a = 2}\), \(\displaystyle{ m = 3}\) i \(\displaystyle{ y = 4}\).

A z jakiej własności należałoby skorzystać, gdyby zamiast \(\displaystyle{ 2016^{2015}}\) było \(\displaystyle{ 2017^{2015}}\)?

Wtedy \(\displaystyle{ 2017 \equiv 2 \pmod{13} \Rightarrow 2017^{2015} \equiv 2^{2015}}\), ale co dalej?

Dalej \(\displaystyle{ \phi(13)=12}\) (\(\displaystyle{ \phi}\) to funkcja Eulera, możesz o niej poczytać, przyporządkowuje ona liczbie naturalnej \(\displaystyle{ \ge 2}\) liczbę liczb całkowitych dodatnich względnie z nią pierwszych), więc z twierdzenia Eulera \(\displaystyle{ 2^{12}\equiv 1\pmod{13}}\), bo \(\displaystyle{ \NWD(2,13)=1}\).

Warto zaznaczyć, że w definicji funkcji Eulera chodzi o liczby nie większe niż \(\displaystyle{ n}\), bo inaczej dla każdego \(\displaystyle{ n}\) mielibyśmy \(\displaystyle{ \varphi(n)=\infty}\). Poza w tym akurat wypadku wystarczy małe twierdzenie Fermata.

Słuszna uwaga.

No to teraz będzie:
\(\displaystyle{ (2^{12})^{167} \cdot 2^{11} \equiv 1 \cdot 2^{11}}\)

Zgadza się. A \(\displaystyle{ 2^{11}=2048}\) to taka malutka liczba, że resztę z dzielenia tej liczby przez \(\displaystyle{ 13}\) liczy się w pamięci. A jeśli ktoś nie lubi, to \(\displaystyle{ 2^{6}\equiv -1\pmod{13}}\) itd.

Ok, oczywiście \(\displaystyle{ 2^{11}}\) to już "fajna" liczba do rachunków Ale spróbuję też w ten drugi zadany przez Ciebie sposób.

\(\displaystyle{ 2^{11} \equiv 2^{6} \cdot 2^{5} \equiv -1 \cdot 2^{5} \equiv -32 \equiv 7}\)

Dobrze?

Dobrze.