Matematyka.pl

Witam, znowu walczę z prostymi podzielnościami. Zadanie jest sforułowane tak:
Wykaż, że dla każdego \(\displaystyle{ n \in \mathbb{N}}\)
(a) \(\displaystyle{ 13|n^{13}-n}\)
(b) \(\displaystyle{ 8|5^n + 2\cdot 3^{n-1} + 1}\)

(a) Przede wszystkim dla n = 1 nie zachodzi - \(\displaystyle{ 1^{13}-1 \neq 13k,\; k \in \mathbb{Z}}\)
Wzruszam ramionami, sprawdzam że dla \(\displaystyle{ n=2}\) zachodzi \(\displaystyle{ 2^{13}-2 = 8190 = 13 \cdot 630}\) więc zakładam że zachodzi dla pewnego \(\displaystyle{ m \geq 2}\) naturalnego.
Hipoteza: \(\displaystyle{ 13| \left( m+1 \right) ^{13}- \left( m+1 \right)}\).
Tutaj trochę się głowiłem czy nie ma inteligentniejszego sposobu niż liczenie \(\displaystyle{ \left( m+1 \right) ^{13}}\) ale ostatecznie - trójkąt Pascala i heja - wyszło:
\(\displaystyle{ \left( m+1 \right) ^{13}- \left( m+1 \right) =}\)
\(\displaystyle{ = m^{13} + 13m^{12} + 78m^{11} + 186m^{10} + 715m^{9} + 1287m^{8} + 1716m^{7} + 1716m^{6} + 1287m^{5} + 715m^{4} + 286m^{3} + 75m^{2} + 13m^{1} + 1 - m - 1}\)
(jedyneczki się skrócą) zostaje
\(\displaystyle{ m^{13} - m + \left( 13m^{12} + 78m^{11} + 186m^{10} + 715m^{9} + 1287m^{8} + 1716m^{7} + 1716m^{6} + 1287m^{5} + 715m^{4} + 286m^{3} + 75m^{2} + 13m^{1} \right)}\)
Teraz korzystam z założenia: \(\displaystyle{ m^{13}-m=13k, k \in \mathbb{Z}}\), mam
\(\displaystyle{ 13k + \left( 13m^{12} + 78m^{11} + 186m^{10} + 715m^{9} + 1287m^{8} + 1716m^{7} + 1716m^{6} + 1287m^{5} + 715m^{4} + 286m^{3} + 75m^{2} + 13m \right) =}\)
\(\displaystyle{ 13k + 13 \left( m^{12} + 6m^{11} + 22m^{10} + 55m^{9} + 99m^{8} + 132m^{7} + 132m^{6} + 99m^{5} + 55m^{4} + 22m^{3} + 6m^{2} + m \right) = 13 \left( k + \left[ \cdots \right] \right)}\)
c. n. d.

I teraz, czy jest dobrze i czy dało się to zrobić jakoś inteligentniej? Bez rozpisywania \(\displaystyle{ \left( m+1 \right) ^{13}}\) na chama?

(b) Tu walczę - znowu indukcyjnie. Dla \(\displaystyle{ n=1}\) jest po prostu \(\displaystyle{ 5^1 + 2\cdot3^0 + 1 = 8}\), zatem teza spełniona.
Zakładam że teza jest spełniona dla pewnego \(\displaystyle{ m \in \mathbb{N}}\). Staram się pokazać że zachodzi dla \(\displaystyle{ m+1}\):
\(\displaystyle{ 5^{m+1} + 2 \cdot 3^{m} + 1 = 5 \cdot 5^m + 2 \cdot 3 \cdot 3^{m-1} + 1}\) no i np. da się do takiej postaci \(\displaystyle{ 4 \cdot 5^m + 4 \cdot 3^{m-1} + \left( 5^{m} + 2 \cdot 3^{m-1} + 1 \right)}\) fajnie jest bo z założenia to jest równe \(\displaystyle{ 4 \left( 5^m+3^{m-1} \right) + 8k, \; k \in \mathbb{Z}}\) i zostaje tylko jakoś przekształcić \(\displaystyle{ 4 \left( 5^m+3^{m-1} \right)}\) żeby się ósemkę jakąś dało wyłączyć...

Do tego miejsca łatwo i tu się powinna pewnie włączyć pomysłowość

Dla \(\displaystyle{ m=1, 2, 3}\), samo \(\displaystyle{ 4 \left( 5^m+3^{m-1} \right)}\) jest podzielne przez \(\displaystyle{ 8}\) - dobry znak, może droga do rozwiązania jest ok.
Co dalej próbowałem:
- powyłączać 5-ki i 3-ki z \(\displaystyle{ 5^m}\) i \(\displaystyle{ 3^m}\) żeby wyciągnąć tę 8-kę przed nawias(bezskutecznie). Obiecujące było \(\displaystyle{ 4 \cdot 3^{m-1} = 16 \cdot 3^{m-2}}\) ale już wyłączanie potęg 5-tęk i iloczyn z 4-ką nie da oczywiście nic podzielnego przez 8... chyba
- niedawno(mój zeszły temat ) załapałem, że można dodać do wyrażenia jakąś wielokrotność \(\displaystyle{ k}\) i wtedy podzielność przez \(\displaystyle{ k}\) tego nowego wyrażenia jest równoważna podzielności wyjściowego wyrażenia. Próbowałem dodać jakąś wielokrotność \(\displaystyle{ 8 \left( 5^m+3^{m-1} \right)}\) i podobnie jak w punkcie wyżej... możliwe że nieumiejętnie...
- Dopuszczalne by było: \(\displaystyle{ 4 \left( 5^m+3^{m-1} \right) = 8 \left( \left( \frac{5}{2} \right) ^m+ \left( \frac{3}{2} \right) ^{m-1} \right)}\) ?? Raczej nie, bo dla \(\displaystyle{ m=1, 2}\) wychodzi \(\displaystyle{ 8 \cdot \hbox{liczba-nie-całkowita}}\)

Wolałbym jakieś wskazówki, naprowadzenie czy w ogóle idę w dobrym kierunku niż gotowiec, ale jeśli rozwiązanie jest oczywiste a ja go po prostu nie widzę to zadowolę się gotowym rozwiązaniem i będę miał nadzieję że się z niego czegoś nauczę

-- edit: --
Przyszło mi jeszcze do głowy że może coś da próba udowodnienia \(\displaystyle{ 8|4 \left( 5^m+3^{m-1} \right)}\) ponownie - indukcją? :-/

(a) to przeformułowanie małego twierdzenia Fermata (dla \(\displaystyle{ n = 1}\) weź \(\displaystyle{ k = 0}\)).

b) Co powiesz o parzystości \(\displaystyle{ 5^m+3^{m-1}}\)?

b) tutaj wystarczy zauważyć, że \(\displaystyle{ 5^2 \equiv 1\pmod{8}}\) oraz \(\displaystyle{ 3^2\equiv 1\pmod{8}}\), stąd mamy dla wszystkich \(\displaystyle{ k \in \NN}\) co następuje:
\(\displaystyle{ 5^{2k}\equiv 1\pmod{8}, 5^{2k+1}\equiv 5\pmod{8}, 3^{2k+1} \equiv 3\pmod{8}, 3^{2k}\equiv 1\pmod{8}}\)
Przyjrzyj się wyrażeniu
\(\displaystyle{ 5^n + 2*3^{n-1} + 1}\)
i zastanów się, co będzie gdy \(\displaystyle{ n=2k, k \in \NN^+}\), a co gdy \(\displaystyle{ n=2k+1, k \in \NN^+}\)
(jakie wtedy będzie \(\displaystyle{ n-1}\)? itd. - skorzystaj z powyższych spostrzeżeń).-- 27 sie 2016, o 19:44 --

Zaratustra pisze:(a) Przede wszystkim dla\(\displaystyle{ n = 1}\) nie zachodzi -\(\displaystyle{ 1^{13}-1 \neq 13k,\; k \in \mathbb{Z}}\)

a od kiedy to \(\displaystyle{ 0 \notin \ZZ}\)?

Santiago A pisze:(a) to przeformułowanie małego twierdzenia Fermata (dla \(\displaystyle{ n = 1}\) weź \(\displaystyle{ k = 0}\)).

Faktycznie, chociaż w książce z której to zadanie wziąłem małe tw. fermata pojawia się trochę później(zresztą z jego użyciem, dla odmiany, to faktycznie łatwe z tego co teraz widzę);
Niemniej dzięki, nie pomyślałem o tym - właściwie właśnie się staram nadrobić braki w teorii liczb .

Lukasz19281 pisze:b) Co powiesz o parzystości \(\displaystyle{ 5^m+3^{m-1}}\)?

Auć... suma dwóch liczb nieparzystych... jest parzysta. Lol.(oczywiście oba czynniki sumy są potęgami liczb nieparzystych czyli są nieparzyste)
Czyli \(\displaystyle{ 4(5^m+3^{m-1})=4(2k')=8k'}\)... ok.

Premislav pisze:a od kiedy to \(\displaystyle{ 0 \notin \ZZ}\)?

Ojć!!! Masz rację! (będę utrzymywał że już dziś tyle zadań natrzaskałem że już mi się koncentracja wyłącza... a tak serio to ździebko pojechałem )

Premislav; No i oczywiście dużo zgrabniej będzie z twoimi "zauważeniami":
Dla \(\displaystyle{ n=2k; k \in \mathbb{Z}}\) mamy
\(\displaystyle{ 5^{2k}+2\cdot3^{2k-1}+1=1 + 8t +2(3+8\tilde{t})+=2+6+8t+8\tilde{t} = 8(1+t+\tilde{t})}\)
Dla \(\displaystyle{ n=2k+1; k \in \mathbb{Z}}\) mamy
\(\displaystyle{ 5^{2k+1}+2\cdot3^{2k}+1=5+8t+2(1+8\tilde{t})+1=8(1+t+\tilde{t})}\)
c.n.d.

Ok. Wielkie dzięki ludzie.