Uzasadnij, że liczba
\(\displaystyle{ 3^{33} + 1}\)
jest podzielna przez \(\displaystyle{ 7}\).
Jakby to była np. 2 czy 5 to wiadomo od razu po ostatniej cyfrze, ale z 7 nie mam pomysłu za bardzo.
Podzielność przez 7
-
- Użytkownik
- Posty: 162
- Rejestracja: 22 wrz 2006, o 17:54
- Płeć: Mężczyzna
- Lokalizacja: Międzyrzecz
- Podziękował: 5 razy
- Pomógł: 40 razy
Podzielność przez 7
Wyjdźmy z oczywistego założenia, że:
\(\displaystyle{ 3^3=27=28-1 \equiv -1 (mod 7)}\)
Czyli:
\(\displaystyle{ 3^3 \equiv -1 (mod 7)}\)
podnosząc tę kongruencję stronami do potęgi 11:
\(\displaystyle{ 3^{33} \equiv -1 (mod 7)}\)
dodając do obu stron 1:
\(\displaystyle{ 3^{33} +1 \equiv 0 (mod 7)}\)
Co stanowi tezę zadania i kończy dowód.
-----
Po dłuższym zastanowieniu wpadłem na nieco bardziej elementarne rozwiązanie. Korzystając ze znanej tożsamości:
\(\displaystyle{ a^{11}+b^{11}=(a+b)(a^{10}-a^9b+a^8b^2....)}\)
Podsatwaiając pod a = \(\displaystyle{ 3^3}\), a pod b=1, otrzymamy:
\(\displaystyle{ 3^{33}+1=(3^3+1)(3^{10}-3^9+3^8....)= 28(3^{10}-3^9+3^8....)= 7*4*(3^{10}-3^9+3^8....)}\)
Liczba w nawiasie jest oczywiście całkowita, zaś wcześniej występuje cyfra 7, co stanowi dowód.
\(\displaystyle{ 3^3=27=28-1 \equiv -1 (mod 7)}\)
Czyli:
\(\displaystyle{ 3^3 \equiv -1 (mod 7)}\)
podnosząc tę kongruencję stronami do potęgi 11:
\(\displaystyle{ 3^{33} \equiv -1 (mod 7)}\)
dodając do obu stron 1:
\(\displaystyle{ 3^{33} +1 \equiv 0 (mod 7)}\)
Co stanowi tezę zadania i kończy dowód.
-----
Po dłuższym zastanowieniu wpadłem na nieco bardziej elementarne rozwiązanie. Korzystając ze znanej tożsamości:
\(\displaystyle{ a^{11}+b^{11}=(a+b)(a^{10}-a^9b+a^8b^2....)}\)
Podsatwaiając pod a = \(\displaystyle{ 3^3}\), a pod b=1, otrzymamy:
\(\displaystyle{ 3^{33}+1=(3^3+1)(3^{10}-3^9+3^8....)= 28(3^{10}-3^9+3^8....)= 7*4*(3^{10}-3^9+3^8....)}\)
Liczba w nawiasie jest oczywiście całkowita, zaś wcześniej występuje cyfra 7, co stanowi dowód.
-
- Użytkownik
- Posty: 80
- Rejestracja: 3 paź 2009, o 20:03
- Płeć: Mężczyzna
- Lokalizacja: Sosnowiec
- Podziękował: 6 razy
- Pomógł: 14 razy
Podzielność przez 7
wlasnie o ten drugi sposob mi chodziło, bo ten pierwszy jest w sumie latwiejszy, ale to zadanie bylo na jakims konkursie dla klasy 1 liceum, więc to musialo byc cos `bardziej widocznego`