Podzielność przez 12

[soulforged]

Udowodnij, że jeżeli liczba \(\displaystyle{ 1+3^{n}+5^{n}}\) jest pierwsza, to liczba \(\displaystyle{ n}\) jest podzielna przez \(\displaystyle{ 12}\).

Pora na to, prosiłbym o jakąś wskazówkę, bo nawet nie wiem jak zacząć. ;D

[Ponewor]

Na sam początek rozważ reszty z dzielenia przez \(\displaystyle{ 3}\).

[soulforged]

No, reszty z dzielenia przez \(\displaystyle{ 3}\) to \(\displaystyle{ 0,1,2}\).

[Ponewor]

nie. Źle mnie zrozumiałeś.
\(\displaystyle{ 3^{n} \equiv 0 \pmod{3}}\) niezależnie od \(\displaystyle{ n}\).
\(\displaystyle{ 5^{n} \equiv ? \pmod{3}}\) ? będą różne wyniki w zależności od \(\displaystyle{ n}\) i będziesz musiał odrzucić takie \(\displaystyle{ n}\) dla których cała suma będzie podzielna przez \(\displaystyle{ 3}\) (z wyłączeniem \(\displaystyle{ n=0}\)).

[soulforged]

\(\displaystyle{ 5^{1} \equiv 2 \pmod{3}}\)
\(\displaystyle{ 5^{2} \equiv 1 \pmod{3}}\)
\(\displaystyle{ 5^{3} \equiv 2 \pmod{3}}\)
\(\displaystyle{ 5^{4} \equiv 1 \pmod{3}}\)
\(\displaystyle{ 5^{5} \equiv 2 \pmod{3}}\)

\(\displaystyle{ ...}\)

\(\displaystyle{ 5^{2k} \equiv 1 \pmod{3}}\)
\(\displaystyle{ 5^{2k \pm 1} \equiv 2 \pmod{3}}\)
A więc dla \(\displaystyle{ n}\) parzystego, reszta wynosi 1, a dla \(\displaystyle{ n}\) nieparzystego reszta wynosi 2. O to chodziło?

[Ponewor]

Ukryta treść:    

Nie bój się korzystać z liczb ujemnych, bo na nich "lepiej widać" tą zależność:
\(\displaystyle{ 5 \equiv -1 \pmod{3} \\ 5^{2k} \equiv \left( -1 \right)^{2k} \equiv 1 \pmod {3}}\)

Otrzymujesz, że dla \(\displaystyle{ n}\) nieparzystych:
\(\displaystyle{ 1+3^{n}+5^{n} \equiv 1 + 0 + 2 \equiv 0 \pmod{3}}\)
co nie może być liczbą pierwszą. Stąd masz, że \(\displaystyle{ n}\) jest parzyste. Analogicznie rozważ podzielność tego wyrażenia przez \(\displaystyle{ 5}\).

[soulforged]

Właśnie to przed twoim postem zauważyłem. Za 10-15 minut spróbuję spróbuję rozważyć przez 5.

\(\displaystyle{ 5^{n} \equiv 0 \pmod{5}}\) niezależnie od \(\displaystyle{ n}\).

Natomiast dla 3:

\(\displaystyle{ 3^{1} \equiv -2 \pmod{5}}\)
\(\displaystyle{ 3^{2} \equiv 4 \equiv -1\pmod{5}}\)
\(\displaystyle{ 3^{3} \equiv 2 \pmod{5}}\)
\(\displaystyle{ 3^{4} \equiv 1 \pmod{5}}\)
\(\displaystyle{ 3^{5} \equiv 3 \equiv -2 \pmod{5}}\)
\(\displaystyle{ 3^{6} \equiv 4 \equiv -1 \pmod{5}}\)
\(\displaystyle{ 3^{7} \equiv 2 \pmod{5}}\)
\(\displaystyle{ 3^{8} \equiv 1 \pmod{5}}\)

Czyli mogą być 4 różne reszty:
\(\displaystyle{ -2 \Rightarrow}\) od razu odpada, bo tworzy ją potęga nieparzysta
\(\displaystyle{ 2 \Rightarrow}\) jak wyżej
\(\displaystyle{ -1 \Rightarrow}\) Odpada, bo gdy ją podstawimy do kongruencji, otrzymamy:

\(\displaystyle{ 1+3^{n}+5^{n} \equiv 1 + (-1) + 0 \equiv 0 \pmod{5}}\)

co nie jest liczbą pierwszą

Zostaje więc 1. Analizując powyższe podzielności reszta 1 jest w wykładnikach parzystych podzielnych przez 4 (np. 4,8,12,16...)

a więc dowiedliśmy, że liczba \(\displaystyle{ n}\) musi być parzysta i podzielna przez 4, dobrze mówię? Jeśli tak, to co dalej?

[Ponewor]

liczba musi być parzysta i podzielna przez 4...

a wystarczyło napisać, że podzielna przez \(\displaystyle{ 4}\). Pamiętając o tym, że jest parzysta mogłeś szybciej sprawdzić te podzielności, bo nie musiałbyś sprawdzać nie parzystych wykładników. No dobrze Mamy już wykazaną podzielność przez \(\displaystyle{ 4}\), to wypadałoby zająć się podzielnością przez \(\displaystyle{ 3}\). W tym celu sprawdź reszty z dzielenia przez kolejną liczbę pierwszą, czyli \(\displaystyle{ 7}\)

[soulforged]

Jezu najukochańszy, jeśli takie zadanie trafi się na OMG, to zajmie mi zbyt dużo czasu... A wtedy klapa!

Dla piątki:
\(\displaystyle{ 5^{n} \equiv 0 \pmod{7}}\)

\(\displaystyle{ 5^{4} \equiv 2 \pmod{7}}\)
\(\displaystyle{ 5^{8} \equiv 4 \pmod{7}}\)
\(\displaystyle{ 5^{12} \equiv 1 \pmod{7}}\)
\(\displaystyle{ 5^{16} \equiv 2 \pmod{7}}\)
\(\displaystyle{ 5^{20} \equiv 4 \pmod{7}}\)
\(\displaystyle{ 5^{24} \equiv 1 \pmod{7}}\)
A więc idzie 2,4,1,2,4,1...

Dla trójki:
\(\displaystyle{ 3^{n} \equiv 0 \pmod{7}}\)

\(\displaystyle{ 3^{4} \equiv 4 \pmod{7}}\)
\(\displaystyle{ 3^{8} \equiv 2 \pmod{7}}\)
\(\displaystyle{ 3^{12} \equiv 1 \pmod{7}}\)
\(\displaystyle{ 3^{16} \equiv 4 \pmod{7}}\)
\(\displaystyle{ 3^{20} \equiv 2 \pmod{7}}\)
\(\displaystyle{ 3^{24} \equiv 1 \pmod{7}}\)
A więc idzie 4,2,1,4,2,1...


Niestety muszę spadać, więc dokończę później .

[Ponewor]

A przecież już kończysz. Popatrz na sumy i od razu widać, że \(\displaystyle{ 3|n}\)

[soulforged]

Jakie sumy?

-- 23 gru 2012, o 19:14 --

W pierwszym przypadku \(\displaystyle{ 2+4=6, 6+1=7}\) co nie daje liczby pierwszej bo jest podzielne przez \(\displaystyle{ 7}\). W drugim przypadku analogicznie, dopiero dla \(\displaystyle{ n=12,24...}\) reszta z dzielenia to \(\displaystyle{ 3}\). Niestety nie mogę tego zapisać latexem bo piszę z telefonu, ale mam nadzieję, że rozumiesz mój tok myślenia... Nie dało się tego zadania zrobić prościej?

[Ponewor]

To jest w gruncie rzeczy naprawdę proste rozwiązanie, jakby to ładnie i elegancko zapisać. Czy da się inaczej? Ja w danej chwili nie potrafię.

[soulforged]

proste, ale czasochłonne... Tyle wymnażania...

[Ponewor]

Jakiego wymnażania? Liczyłeś te potęgi?

[soulforged]

Tak... A jak inaczej sprawdzać reszty?