Liczenie po chińsku, czyli ilu jest policjantów?
13.08.2009 - Agata Murawska
Liczby 2, 5 i 9 są parami względnie pierwsze, to znaczy żadne dwie z nich nie mają wspólnych dzielników. Dlaczego jest to takie ważne? To dzięki tej własności możemy udowodnić, że zagadka ma dokładnie jedną poprawną odpowiedź (której wcale nie musimy znać).
Ale zaraz zaraz. Jaka liczba mniejsza od jest podzielna przez 9, 5 oraz 2? Całkiem dobrze znamy najmniejszą taką liczbę - 0 i najmniejszą dodatnią - to najmniejsza wspólna wielokrotność () tych trzech liczb. Być może wiesz już, że skoro 5 i 9 nie mają wspólnych dzielników, to . Ale 45 nie dzieli się przez 2, więc nie jest to szukana wartość . Poprawmy: . Coś tu się nie zgadza, prawda? Chcieliśmy dostać liczbę mniejszą od 90, a dostaliśmy dokładnie 90. Co to znaczy? Wśród liczb z rozważanego przedziału: [0, 90) jedyną możliwą wartością różnicy jest 0, a zatem . Rozwiązanie jest dokładnie jedno! Przedstawione powyżej rozumowanie to przykład wykorzystania własności liczb o której mówi chińskie twierdzenie o resztach. Wrócimy jeszcze do tego tematu, żeby nauczyć się mądrzej szukać najmniejszego rozwiązania. Będzie to trochę trudniejsze, niż rozważania o policjantach, ale niezwykle przydatne - niektóre obliczenia łatwiej wykonuje się na liczbach pierwszych (lub ich potęgach). Rozłożenie liczby na czynniki pierwsze i zastosowanie chińskiego twierdzenia o resztach upraszcza tego typu zadania pod warunkiem, że potrafimy odzyskać ostateczny wynik. CToR (matematycy i informatycy lubią takie skróty) jest też przydatnym narzędziem w kryptografii - między innymi przy jego pomocy dowodzi się poprawności algorytmu RSA. Ale to już zupełnie inna historia.. (2 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com