podzielnosc liczb, kongruencje

[17inferno]

Wykaz, ze dla kazdej liczby naturalnej \(\displaystyle{ n}\) liczba:

a) \(\displaystyle{ 2^{n+2}+3^{2n+1}}\) jest podzielna przez \(\displaystyle{ 7}\)

b) \(\displaystyle{ 3^{3n+1}+9^{3n+1}+1}\) jest podzielna przez \(\displaystyle{ 13}\)

[adambak]

1) indukcja, dla \(\displaystyle{ n=0}\) działa.. załóżmy, że dla pewnego \(\displaystyle{ n}\) zachodzi \(\displaystyle{ 2^{n+2}+3^{2n+1}=7k \Rightarrow 3^{2n+1}=7k-2^{n+2}, \ k\in\mathbb{Z}}\)
sprawdźmy co jest dla \(\displaystyle{ n+1}\):
\(\displaystyle{ 2^{n+3}+3^{2n+3}=2\cdot 2^{n+2}+3^2\cdot 3^{2n+1}=2\cdot 2^{n+2}+3^2(7k-2^{n+2})=3^2\cdot 7k - 7\cdot 2^{n+2}}\), co się dzieli przez \(\displaystyle{ 7}\), bo każdy składnik się dzieli..

2) można tak samo, ale ja wolę tak: wypisz sobie kolejne potęgi \(\displaystyle{ 3}\) modulo \(\displaystyle{ 13}\) (zacznij od wykładnika równego \(\displaystyle{ 0}\)).. zauważ, jak szybko się zapętlają, następnie \(\displaystyle{ 3^{3n+1}+9^{3n+1}+1=3^{3n+1}(3^{3n+1}+1)+1}\), czyli interesują nas wykładniki które dają resztę z dzielenia przez \(\displaystyle{ 3}\) równą jeden.. z wypisanych wcześniej informacji zobacz ile to jest \(\displaystyle{ 3^{3n+1}\mod{13}}\) i ostatecznie korzystając z podstawowych własności kongruencji zobacz jaki wynik modulo \(\displaystyle{ 13}\) daje całe to wyrażenie - wychodzi \(\displaystyle{ 0}\), czyli jest podzielne przez \(\displaystyle{ 13}\)..

[17inferno]

jak zrobuc to zadanie bez indukcji, tylko za pomoca kongruencji

[adambak]

proszę bardzo.. da się podobnie jak zrobiłem podpunkt b), tylko trzy rodzaje wykładników do sprawdzenia (bo tak szybko reszty dwójki się zapętlają) i wychodzi ładnie, że zawsze jest podzielne

[Vax]

\(\displaystyle{ 2^{n+2}+3^{2n+1} \equiv 2^{n+2}+3\cdot 9^n \equiv 2^{n+2}+3\cdot 2^n \equiv 2^n(4+3) \equiv 2^n\cdot 7 \equiv 0\pmod{7}}\)

[17inferno]

dzieki za pomoc