Sposób na wyliczenie reszty z dzielenia

[Przemogmx]

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ć

[kerajs]

Moim zdaniem wykonujesz (utrudnione) pisemne dzielenie. Pomijasz uzyskiwane części całkowite, skupiając się wyłącznie na reszcie.
Czy Twój algorytm nadal będzie działał przy dzieleniu przez liczbę większą od 100?

Pozdrawiam i zachęcam do dalszych spostrzeżeń.

[Przemogmx]

Sprawdzałem i działał dla liczb większych niż 100. Działał też dla mniejszych niż 10.
Ta dziesiątka zależy pewnie od systemu liczbowego jakim się posługujemy. Sprawdzałem ten wzór też w systemie dwójkowym i szóstkowym, gdzie też okazał się skuteczny. Trzeba było podstawić tam na miejsce dziesiątki odpowiednio 2 i 6. Zdaję sobie sprawę, że to jest tylko sposób na uzyskanie odpowiedzi, czy liczba jest podzielna przez inną i ewentualnie poznanie reszty.

Co do samego wzoru, to istnieje możliwość rozpisania go w postaci grafu.
Tutaj przykładowo dla dzielenia przez siedem:

Zaczynamy od zera. Podczas dodawania cyfry poruszamy się zgodnie z ruchem wskazówek zegara na kolejne kółka. Po każdym ruchu (poza ostatnim) przemieszczamy się tam, gdzie pokazuje strzałka od pola na którym się zatrzymaliśmy. Całość powtarzamy, aż do dodania ostatniej cyfry. tam gdzie skończymy jest nasza reszta.

Żeby sporządzić taki diagram dla dzielenia przez liczbę \(\displaystyle{ m}\), mnożymy 1 przez 10 i wyciągamy resztę z dzielenia przez \(\displaystyle{ m}\). Potem rysujemy strzałkę od 1 do otrzymanej reszty. To samo dla 2, 3 i pozostałych liczb do \(\displaystyle{ m}\).

Metoda ta nie zastąpi zwykłego dzielenia, ale pokazuje kwestię podzielności liczb z odmiennej strony.

[Sylwek]

Jest OK, tak naprawdę stosujesz schemat Hornera (ten "informatyczny", do szybkiego obliczania wartości wielomianu) dla wielomianu \(\displaystyle{ 2x^4+8x^3+3x^2+6x+7}\), a następnie bierzesz \(\displaystyle{ x=10}\), jako podstawę systemu dziesiętnego.

Innymi słowy, nawiasujesz sobie tak:
\(\displaystyle{ 28367=((((2 \cdot 10+8)\cdot 10)+3)\cdot 10+6)\cdot 10+7}\),
po czym "od wewnątrz" liczysz modulo kolejnych działań (np. tutaj mod 17).