Dowód cechy podzielności przez 13
: 20 lis 2018, o 21:58
Witam, proszę o pokazanie lub przeprowadzenie zadania z dowodem podzielności przez \(\displaystyle{ 13}\) opierającym się na kongruencji.
Jako że \(\displaystyle{ \NWD(4,13)=1}\) to stwierdzenia
\(\displaystyle{ 10x+y\equiv0\bmod13}\)
\(\displaystyle{ 4(10x+y)\equiv0\bmod13}\)
są równoważne. A to drugie z nich upraszcza się do \(\displaystyle{ x+4y\equiv0\bmod13}\). Kładąc teraz
\(\displaystyle{ x=a_n10^{n-2}+a_{n-1}10^{n-3}+...+a_1}\)
\(\displaystyle{ y=a_0}\)
dostajemy że liczba
\(\displaystyle{ a_n10^{n-1}+a_{n-1}10^{n-2}+...+a_110+a_0\equiv0\bmod13}\)
wtedy i tylko wtedy gdy
\(\displaystyle{ a_n10^{n-2}+a_{n-1}10^{n-3}+...+a_1+4a_0\equiv0\bmod13}\)
No i to oczywiście rekurencyjnie działa. Więc na przykład liczba \(\displaystyle{ 19799}\) jest podzielna przez \(\displaystyle{ 13}\) bo
\(\displaystyle{ 19799 \rightarrow 1979+4 \cdot 9=2015 \rightarrow 201+4 \cdot 5=221 \rightarrow 22+4 \cdot 1=26}\)
\(\displaystyle{ 26}\) jest podzielne to już widać.