Reszty i podzielność przez 12

[KrolKubaV]

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

Ukryta treść:    

Rozpatrz reszty z dzielenia liczby \(\displaystyle{ 1+3^{n}+ 5^{n}}\) przez \(\displaystyle{ 3, 5, 7}\)

[Premislav]

Faktycznie wystarczy rozważyć reszty z dzielenia przez \(\displaystyle{ 3, \quad 5}\) i \(\displaystyle{ 7}\).

Ponieważ \(\displaystyle{ 5^2\equiv 1\pmod{3}}\), zatem
\(\displaystyle{ 5^{2k}\equiv 1\pmod{3},\\ 5^{2k+1}\equiv 2\pmod{3}}\)
czyli gdy \(\displaystyle{ n}\) jest nieparzyste, to \(\displaystyle{ 1+3^n+5^n\equiv 0\pmod{3}}\), więc aby liczba \(\displaystyle{ 1+3^n+5^n}\) miała szansę być pierwszą, \(\displaystyle{ n}\) musi być parzyste.

Ponieważ \(\displaystyle{ 3^4\equiv 1\pmod{5}}\), więc
\(\displaystyle{ 3^{4k}\equiv 1\pmod{5}, \\3^{4k+1}\equiv 3\pmod{5},\\ 3^{4k+2}\equiv 4\pmod{5},\\ 3^{4k+3}\equiv 2\pmod{5}}\)
Stąd gdy \(\displaystyle{ n=4k+2}\), to \(\displaystyle{ 1+3^n+5^n\equiv 0\pmod{5}}\), czyli \(\displaystyle{ n=4k+2, k \in \NN}\) odpada.

Ponieważ \(\displaystyle{ 3^3\equiv -1\pmod{7}}\) oraz \(\displaystyle{ 5^3\equiv -1 \pmod{7}}\), co łatwo można wyliczyć ręcznie, dostajemy, że
\(\displaystyle{ 1+3^{3k}+5^{3k}\equiv 1+(-1)^k+(-1)^k\pmod{7}}\),
a oczywiście liczba \(\displaystyle{ 1+2(-1)^k}\) nie jest podzielna przez \(\displaystyle{ 7}\) dla żadnego \(\displaystyle{ k}\) naturalnego, bo jest równa \(\displaystyle{ 3}\) albo \(\displaystyle{ -1}\)
Ponadto
\(\displaystyle{ 1+3^{3k+1}+5^{3k+1}\equiv 1+8\cdot (-1)^k\pmod{7}, \\1+3^{3k+2}+5^{3k+2}\equiv 1+(-1)^k \cdot 34\pmod{7}}\)
Już wcześniej uzasadniliśmy, że wykładnik musi być parzysty i nie być postaci \(\displaystyle{ 4k+2}\) dla żadnego \(\displaystyle{ k \in \NN}\), a więc musi być podzielny przez \(\displaystyle{ 4}\).
Jeżeli zaś liczba postaci \(\displaystyle{ 3k+1}\) dzieli się przez \(\displaystyle{ 4}\), to \(\displaystyle{ k}\) musi być nieparzyste (inaczej \(\displaystyle{ 3k+1}\) byłoby nieparzyste), ale gdy \(\displaystyle{ k}\) nieparzyste, to
\(\displaystyle{ 1+8(-1)^k=-7}\), co dzieli się przez \(\displaystyle{ 7}\) - więc wtenczas liczba \(\displaystyle{ 1+3^{3k+1}+5^{3k+1}}\) nie jest pierwsza.
Podobnie gdy liczba postaci \(\displaystyle{ 3k+2}\) dla pewnego \(\displaystyle{ k \in \NN}\) ma być podzielna przez \(\displaystyle{ 4}\), to liczba \(\displaystyle{ 3k}\) musi być parzysta, a więc \(\displaystyle{ k}\) jest parzysta,
a wówczas \(\displaystyle{ 1+3^{3k+2}+5^{3k+2}\equiv 35\pmod{7}}\), więc liczba \(\displaystyle{ 1+3^{3k+2}+5^{3k+2}}\) nie jest pierwszą, bo dzieli się przez \(\displaystyle{ 7}\).
Podsumowując, pokazaliśmy, że aby \(\displaystyle{ 1+3^n+5^n}\) była liczba pierwszą, musi być \(\displaystyle{ 3|n \wedge 4|n}\), a więc \(\displaystyle{ 12|n}\)
Straszna dłubanina. Czy istnieje ładniejsze rozwiązanie? (nie chodzi o zapisanie tego samego krócej, tylko o faktycznie zgrabniejsze i krótsze rozwiązanie).

[KrolKubaV]

Szczerze to nie wiem, ja zrobiłem dokładnie tak jak Ty. Może ktoś inny na coś wpadnie?
Ciekawostka: dla \(\displaystyle{ n=12}\) liczba z zadania jest pierwsza