Udowodnić podzielność liczb

[icK]

Wiem, pewnie było 100 razy, przeczytałem kilka podobnych tematów ale dalej mam z tym problem :/

Pokazać że \(\displaystyle{ 2^{50} + 3^{50}}\) jest podzielne przez 13

[Premislav]

\(\displaystyle{ 2^{50}=(2^{2})^{25}+(3^2)^{25}}\)
i skorzystaj ze wzorku
\(\displaystyle{ a^{2n+1}+b^{2n+1}=(a+b)(a^{2n}-a^{2n-1}b+\dots- ab^{2n-1}+b^{2n})}\),
oczywiście \(\displaystyle{ 2n+1=25}\)

-- 7 cze 2017, o 17:25 --

Inaczej:
\(\displaystyle{ 3^3\equiv 1\pmod{13}}\), więc \(\displaystyle{ 3^{48}\equiv 1\pmod{13}}\)
i \(\displaystyle{ 3^{50}=3^2\cdot 3^{48}\equiv 9\pmod{13}}\)
Analogicznie
\(\displaystyle{ 2^6\equiv -1 \pmod{13}\\ (2^6)^{8} \equiv (-1)^8 \pmod{13}}\)
i tak dalej.
Zatem \(\displaystyle{ 2^{50}+3^{50}\equiv 0\pmod{13}}\)

-- 7 cze 2017, o 17:28 --

Jak komuś wygodniej wykorzystać teorię zamiast zgadywać, to można też od razu z małego twierdzenia Fermata: \(\displaystyle{ 13}\) jest liczbą pierwszą i \(\displaystyle{ \NWD(2,13)=1}\) i \(\displaystyle{ \NWD(3,13)=1}\), zatem
\(\displaystyle{ 2^{12} \equiv 1\pmod{13}, \ 3^{12}\equiv 1\pmod{13}}\)
no i zapisujemy
\(\displaystyle{ 2^{50}=2^2\cdot (2^{12})^4}\)
oraz
\(\displaystyle{ 3^{50}=3^2\cdot(3^{12})^4}\)

[0Mniac]

Można to zrobić w taki sposób:

\(\displaystyle{ 2=2\pmod{13} \Rightarrow 2^{12} = 2^{12} \pmod{7}}\)

Ogólnie sprawdź jaka potęga dwójki daje \(\displaystyle{ 1\pmod{13}}\)

\(\displaystyle{ 2^{12}=1\pmod{13}}\)

\(\displaystyle{ 50=4 \cdot 12 + 2}\)

\(\displaystyle{ 2^{12} ^{ \cdot 4} =2^{48}= 1^{48} =1\pmod{13}}\)

\(\displaystyle{ 2^{48} \cdot 2^{2}=2^2=4}\)

Więc reszta z dzielenia \(\displaystyle{ 2^{50}}\) przez \(\displaystyle{ 13}\) to 4. Podobnie policzyć dla 2 liczby- powinno wyjść \(\displaystyle{ 9}\).

[Jan Kraszewski]

Można to zrobić w taki sposób:

\(\displaystyle{ 2=2\pmod{13} \Rightarrow 2^{12} = 2^{12} \pmod{7}}\)

No cóż, chociaż formalnie to prawda, to sensowność tego jest umiarkowana.

JK