udowodnij korzystając z kongruencji
\(\displaystyle{ 21|2^{4^{n}}+5}\) Proszę o wytłumaczenie najdokładniej jak się tylko da, bo dopiero zaczynam swoją przygode z kongruencjami
Udowodnij korzystając z kongruencji
-
Tristan
- Użytkownik
- Posty: 2333
- Rejestracja: 24 kwie 2005, o 14:28
- Płeć: Mężczyzna
- Podziękował: 27 razy
- Pomógł: 557 razy
Udowodnij korzystając z kongruencji
Skoro \(\displaystyle{ 21=3 7}\), to mamy pokazać, że dane wyrażenie dzieli się przez 3 i przez 7.
Pokażę wpierw, jak wykazać to pierwsze:
Oczywiście zachodzi \(\displaystyle{ 2^2 \equiv 1 ( mod\ 3)}\). Podnieśmy to obustronnie do potęgi \(\displaystyle{ \frac{ 4^n }{2}}\). Ponieważ\(\displaystyle{ \frac{4^n}{2}=\frac{2^{2n}}{2}=2^{2n-1}}\) jest liczbą naturalną, więc możemy tak zrobić. Otrzymujemy, że \(\displaystyle{ 2^{4^n}} \equiv 1 ( mod\ 3)}\). Dodając stronami 5 dostajemy \(\displaystyle{ 2^{4^{n}} +5 \equiv 6 \equiv 0 ( mod\3)}\).
Wykazaliśmy więc, że istotnie \(\displaystyle{ 3 | 2^{4^{n}}+5}\).
Aby pokazać, że 7 dzieli to wyrażenie zauważmy, że \(\displaystyle{ 4^n \equiv 1 ( mod\ 3)}\).
Dowód indukcyjny:
1. Spr. dla n=1
\(\displaystyle{ 4^1=4 \equiv 1 ( mod\ 3)}\)
2. Zał. ind.: \(\displaystyle{ 4^k \equiv 1 ( mod\ 3)}\)
Teza ind.: \(\displaystyle{ 4^{k+1} \equiv 1 ( mod\ 3)}\)
D-d:
\(\displaystyle{ 4^{k+1}=4^k 4 \equiv 1 4=4 \equiv 1 ( mod\ 3)}\)
3. Na mocy zasady indukcji matematycznej własność ta prawdziwa jest dla każdej liczby naturalnej.
Wracając do naszej podzielności... Zauważmy, że \(\displaystyle{ 2^3 \equiv 1 ( mod\ 7)}\). Potęgą dwójki jest 3, a ja chcę mieć w potędzie \(\displaystyle{ 4^n}\). Należy więc się zastanowić do czegóż to przystaje \(\displaystyle{ 4^n}\) modulo 3. My już wcześniej wykazaliśmy, że przystaje do 1. Czyli innymi słowy \(\displaystyle{ 4^n=3 m +1}\).
Podnieśmy więc kongrunecję \(\displaystyle{ 2^3 \equiv 1 (mod\ 7)}\) do potęgi m-tej stronami. Otrzymujemy, że \(\displaystyle{ 2^{3m} \equiv 1 ( mod\ 7)}\). Pomnóżmy obustronnie przez \(\displaystyle{ 2^1}\). Mamy, że \(\displaystyle{ 2^{3m+1} \equiv 1 2^1=2 ( mod\ 7)}\). Ponieważ \(\displaystyle{ 4^n=3m +1}\) teraz już na pewno widać, że istotnie \(\displaystyle{ 2^{4^{n}} \equiv 2 ( mod\ 7)}\). Dodając do tej kongruencji stronami 5, dostajemy, że \(\displaystyle{ 2^{4^{n}} \equiv 7 \equiv 0 ( mod\ 7)}\).
Wykazaliśmy więc, że \(\displaystyle{ 3 | 2^{4^{n}} +5}\) oraz \(\displaystyle{ 7 | 2^{4^{n}}+5}\). Czyli rzeczywiście \(\displaystyle{ 21 | 2^{4^n}}+5}\) cbdw.
Pokażę wpierw, jak wykazać to pierwsze:
Oczywiście zachodzi \(\displaystyle{ 2^2 \equiv 1 ( mod\ 3)}\). Podnieśmy to obustronnie do potęgi \(\displaystyle{ \frac{ 4^n }{2}}\). Ponieważ\(\displaystyle{ \frac{4^n}{2}=\frac{2^{2n}}{2}=2^{2n-1}}\) jest liczbą naturalną, więc możemy tak zrobić. Otrzymujemy, że \(\displaystyle{ 2^{4^n}} \equiv 1 ( mod\ 3)}\). Dodając stronami 5 dostajemy \(\displaystyle{ 2^{4^{n}} +5 \equiv 6 \equiv 0 ( mod\3)}\).
Wykazaliśmy więc, że istotnie \(\displaystyle{ 3 | 2^{4^{n}}+5}\).
Aby pokazać, że 7 dzieli to wyrażenie zauważmy, że \(\displaystyle{ 4^n \equiv 1 ( mod\ 3)}\).
Dowód indukcyjny:
1. Spr. dla n=1
\(\displaystyle{ 4^1=4 \equiv 1 ( mod\ 3)}\)
2. Zał. ind.: \(\displaystyle{ 4^k \equiv 1 ( mod\ 3)}\)
Teza ind.: \(\displaystyle{ 4^{k+1} \equiv 1 ( mod\ 3)}\)
D-d:
\(\displaystyle{ 4^{k+1}=4^k 4 \equiv 1 4=4 \equiv 1 ( mod\ 3)}\)
3. Na mocy zasady indukcji matematycznej własność ta prawdziwa jest dla każdej liczby naturalnej.
Wracając do naszej podzielności... Zauważmy, że \(\displaystyle{ 2^3 \equiv 1 ( mod\ 7)}\). Potęgą dwójki jest 3, a ja chcę mieć w potędzie \(\displaystyle{ 4^n}\). Należy więc się zastanowić do czegóż to przystaje \(\displaystyle{ 4^n}\) modulo 3. My już wcześniej wykazaliśmy, że przystaje do 1. Czyli innymi słowy \(\displaystyle{ 4^n=3 m +1}\).
Podnieśmy więc kongrunecję \(\displaystyle{ 2^3 \equiv 1 (mod\ 7)}\) do potęgi m-tej stronami. Otrzymujemy, że \(\displaystyle{ 2^{3m} \equiv 1 ( mod\ 7)}\). Pomnóżmy obustronnie przez \(\displaystyle{ 2^1}\). Mamy, że \(\displaystyle{ 2^{3m+1} \equiv 1 2^1=2 ( mod\ 7)}\). Ponieważ \(\displaystyle{ 4^n=3m +1}\) teraz już na pewno widać, że istotnie \(\displaystyle{ 2^{4^{n}} \equiv 2 ( mod\ 7)}\). Dodając do tej kongruencji stronami 5, dostajemy, że \(\displaystyle{ 2^{4^{n}} \equiv 7 \equiv 0 ( mod\ 7)}\).
Wykazaliśmy więc, że \(\displaystyle{ 3 | 2^{4^{n}} +5}\) oraz \(\displaystyle{ 7 | 2^{4^{n}}+5}\). Czyli rzeczywiście \(\displaystyle{ 21 | 2^{4^n}}+5}\) cbdw.