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}\)
podzielnosc liczb, kongruencje
podzielnosc liczb, kongruencje
Ostatnio zmieniony 30 maja 2012, o 09:18 przez Qń, łącznie zmieniany 1 raz.
Powód: Temat umieszczony w złym dziale.
Powód: Temat umieszczony w złym dziale.
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
podzielnosc liczb, kongruencje
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}\)..
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}\)..
-
- Użytkownik
- Posty: 1272
- Rejestracja: 8 sty 2011, o 18:18
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 295 razy
- Pomógł: 115 razy
podzielnosc liczb, kongruencje
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
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
podzielnosc liczb, kongruencje
\(\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}}\)