Dowody podzielności

[ajlofmath]

Jak udowodnić cechy podzielności? Oczywiście nie chodzi mi o takie trywialne rzeczy jak 2, 5 czy 10...Wymyśliłem tylko co robić, dla potęg dwójki i 3, 9. Nie wiem jak to zrobić dla 7 czy 11. Pokazałby ktoś Najbardziej chciałbym za pomocą kongruencji.

[squared]

Każdą podzielność robi się podobnie. Pewną liczbę zapisujemy w postaci:

\(\displaystyle{ a_0+10a_1+10^2a_2+\ldots+10^ma_m, \ \ m\in \NN, a_j\in\left\{ 0,1,\ldots,9\right\}}\) .
I wtedy bierzesz tę liczbę modulo np. \(\displaystyle{ \mod 11}\)

\(\displaystyle{ a_0+10a_1+10^2a_2+\ldots+10^ma_m \equiv_{11} 0}\).
I zastanawiasz się kiedy tak jest.

Każdorazowo trzeba sprawdzić ile \(\displaystyle{ \mod 11}\) (lub \(\displaystyle{ \mod}\) każda inna liczba) wynosi \(\displaystyle{ 10, 10^2, 10^3, 10^4, 10^5, \ldots}\).

Przykładowo:
\(\displaystyle{ 10 \equiv_{11} -1 \\
10^2 \equiv_{11} 1 \\
10^3 \equiv_{11} -1}\)
itd.

Indukcyjnie można pokazać, że \(\displaystyle{ 10^n\equiv_{11} \begin{cases} 1 \ \ \ \text{gdy n parzyste} \\ -1 \ \ \ \text{gdy n nieparzyste} \end{cases}}\)

Zatem (z własności kongruencji):
\(\displaystyle{ a_0+10a_1+10^2a_2+\ldots+10^ma_m \equiv_{11} 0 \Leftrightarrow a_0 - a_1 + a_2 - a_3 + \dots \equiv_{11} 0}\), co interpretujemy, że naprzemienna suma cyfr musi być podzielna przez \(\displaystyle{ 11}\), wtedy wyjściowa liczba jest podzielna przez \(\displaystyle{ 11}\).

Podobnie każdą inną podzielność się robi.