Sposób na wyliczenie reszty z dzielenia
: 26 lis 2018, o 11:13
Witam!
Jakiś czas temu zauważyłem pewną ciekawą cechę podzielności, przy pomocy której można wyznaczyć resztę z dzielenia. Wiem, że znana jest metoda oparta na tym zjawisku dla dzielenia przez siedem, ale nie znalazłem tego sposobu sformuowanego dla innych liczb. Stosuje się ona do podzielności przez liczby pierwsze poza \(\displaystyle{ 2}\) i \(\displaystyle{ 5}\).
Załóżmy, że \(\displaystyle{ n=ABCDE}\), gdzie litery od A do E to cyfry. Naszym dzielnikiem będzie liczba pierwsza \(\displaystyle{ m}\), która nie równa się \(\displaystyle{ 2}\), ani \(\displaystyle{ 5}\).
Wartość cyfry \(\displaystyle{ A}\) mnożymy przez \(\displaystyle{ 10}\) i wyciągamy \(\displaystyle{ \mod m}\). Następnie do wyniku dodajemy wartość cyfry \(\displaystyle{ B}\) i powtarzamy proces. Po dodaniu ostatniej cyfry już nie mnożymy przez \(\displaystyle{ 10}\), ale tylko wyciągamy modulo.
Na przykładzie \(\displaystyle{ 28367 \mod 17}\):
\(\displaystyle{ (2 \cdot 10)\mod17=3\mod17 \\
((3+8) \cdot 10)\mod17=8\mod17 \\
((8+3) \cdot 10)\mod17=8\mod17 \\
((8+6) \cdot 10)\mod17=4\mod17 \\
((4+7)\mod17=11\mod17}\)
Tak więc reszta z dzielenia \(\displaystyle{ 28367}\) przez \(\displaystyle{ 17}\) to \(\displaystyle{ 11}\).
Dodam na koniec, że miałem wątpliwości, czy nie zamieścić tego posta w dziale "podzielność" z podstaw matematyki.
Jeśli ktoś wie co nieco na ten temat, albo czy taka metoda istnieje, to proszę pisać
Jakiś czas temu zauważyłem pewną ciekawą cechę podzielności, przy pomocy której można wyznaczyć resztę z dzielenia. Wiem, że znana jest metoda oparta na tym zjawisku dla dzielenia przez siedem, ale nie znalazłem tego sposobu sformuowanego dla innych liczb. Stosuje się ona do podzielności przez liczby pierwsze poza \(\displaystyle{ 2}\) i \(\displaystyle{ 5}\).
Załóżmy, że \(\displaystyle{ n=ABCDE}\), gdzie litery od A do E to cyfry. Naszym dzielnikiem będzie liczba pierwsza \(\displaystyle{ m}\), która nie równa się \(\displaystyle{ 2}\), ani \(\displaystyle{ 5}\).
Wartość cyfry \(\displaystyle{ A}\) mnożymy przez \(\displaystyle{ 10}\) i wyciągamy \(\displaystyle{ \mod m}\). Następnie do wyniku dodajemy wartość cyfry \(\displaystyle{ B}\) i powtarzamy proces. Po dodaniu ostatniej cyfry już nie mnożymy przez \(\displaystyle{ 10}\), ale tylko wyciągamy modulo.
Na przykładzie \(\displaystyle{ 28367 \mod 17}\):
\(\displaystyle{ (2 \cdot 10)\mod17=3\mod17 \\
((3+8) \cdot 10)\mod17=8\mod17 \\
((8+3) \cdot 10)\mod17=8\mod17 \\
((8+6) \cdot 10)\mod17=4\mod17 \\
((4+7)\mod17=11\mod17}\)
Tak więc reszta z dzielenia \(\displaystyle{ 28367}\) przez \(\displaystyle{ 17}\) to \(\displaystyle{ 11}\).
Dodam na koniec, że miałem wątpliwości, czy nie zamieścić tego posta w dziale "podzielność" z podstaw matematyki.
Jeśli ktoś wie co nieco na ten temat, albo czy taka metoda istnieje, to proszę pisać