Liczby pierwsze Z twierdzenia, że liczba jest podzielna przez jeśli jest ona podzielna przez i oraz i są względnie pierwsze, wiemy, że aby sprawdzić podzielność liczby, należy sprawdzić podzielność przez każdy z czynników dzielnika, np. podzielność 25116 przez 84 oznacza, że liczba ta powinna dzielić się przez każdą z liczb: 4, 3 i 7 (bo rozkład dzielnika na czynniki pierwsze ma postać: ) W tym kontekście ważne staje się ustalenie cech podzielności dla liczb pierwszych.
Dość ogólną metodę konstruowania takich cech podzielności podaje Stephen Froggatt w serwisie Math Forum. Oto algorytm budowania cechy podzielności dla dowolnej liczby pierwszej p: Szukamy najmniejszej liczby naturalnej dla której jest podzielne przez (inaczej: dla pewnego liczba ) Wówczas, jak łatwo sprawdzić, także dzieli się przez Mamy do wyboru dwa sposoby postępowania: a) od badanej liczby oddzielamy cyfrę jedności, mnożymy przez i dodajemy do pozostałej części liczby albo b) od oddzielamy cyfrę jedności, mnożymy ją przez i odejmujemy od pozostałej części liczby
Jeśli otrzymana (mniejsza) liczba dzieli się przez to i dzieli się przez Jeśli otrzymana liczba jest jeszcze zbyt duża, można to postępowanie stosować wielokrotnie.
Zbudujmy np.