Podzielność przez 7

[michas-__]

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.

[Elminster]

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.

[michas-__]

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`