Sposób na wyliczenie reszty z dzielenia

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
Przemogmx
Użytkownik
Użytkownik
Posty: 6
Rejestracja: 9 wrz 2018, o 12:52
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 3 razy

Sposób na wyliczenie reszty z dzielenia

Post autor: Przemogmx » 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ć
Ostatnio zmieniony 26 lis 2018, o 11:22 przez Jan Kraszewski, łącznie zmieniany 3 razy.
Powód: Poprawa wiadomości. Symbol mnożenia to \cdot.

Awatar użytkownika
kerajs
Użytkownik
Użytkownik
Posty: 7175
Rejestracja: 17 maja 2013, o 10:23
Płeć: Mężczyzna
Podziękował: 205 razy
Pomógł: 2852 razy

Re: Sposób na wyliczenie reszty z dzielenia

Post autor: kerajs » 27 lis 2018, o 13:51

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
Użytkownik
Użytkownik
Posty: 6
Rejestracja: 9 wrz 2018, o 12:52
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 3 razy

Re: Sposób na wyliczenie reszty z dzielenia

Post autor: Przemogmx » 29 lis 2018, o 20:20

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.

Awatar użytkownika
Sylwek
Gość Specjalny
Gość Specjalny
Posty: 2707
Rejestracja: 21 maja 2007, o 14:24
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 154 razy
Pomógł: 648 razy

Re: Sposób na wyliczenie reszty z dzielenia

Post autor: Sylwek » 30 lis 2018, o 13:18

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).

ODPOWIEDZ