Iterative Binary Divisibility Criterion for Odd Divisors

A deterministic algorithm for testing the divisibility of an integer N by a given odd divisor d is proposed. The algorithm uses exclusively the operations of addition of d and division by 2 (right bitwise shift), thereby avoiding the costly computation of the remainder Nmod dNmodd. The method preserves correctness through an invariant congruence modulo dd and terminates in O(log N) iterations. Its primary practical value lies in its efficiency for large integers (big integers) and hardware-oriented implementations (FPGA/ASIC), where addition and shift are substantially cheaper operations than division. The paper provides a proof of correctness, complexity analysis, and application examples. Предлагается детерминированный алгоритм для проверки делимости целого числа N на заданный нечётный делитель d. Алгоритм использует исключительно операции сложения d и деления на 2 (побитового сдвига вправо), что позволяет избежать дорогостоящей операции взятия остатка N mod d . Метод сохраняет корректность благодаря инварианту сравнения по модулю d и завершается за O(log N) итераций. Основная практическая ценность заключается в эффективности для больших целых чисел (big integers) и аппаратно-ориентированных реализаций (FPGA/ASIC), где сложение и сдвиг являются существенно более дешёвыми операциями, чем деление. Приводятся доказательство корректности, оценка сложности и примеры применения. Бүтін N санының берілген тақ d бөлгішіне бөлінгіштігін тексеруге арналған детерминирленген алгоритм ұсынылады. Алгоритм тек d-ді қосу және 2-ге бөлу (оңға қарай биттік ығысу) амалдарын ғана қолданады, бұл N mod d қалдығын есептеудің қымбат операциясын болдырмайды. Әдіс d модулі бойынша салыстырылу инварианты арқылы дұрыстығын сақтайды және O(log N) итерацияда аяқталады. Оның негізгі практикалық құндылығы үлкен бүтін сандар (big integers) және аппараттық-бағдарланған іске асырылулар (FPGA/ASIC) үшін тиімділігінде жатыр, мұнда қосу мен ығысу бөлуге қарағанда едәуір арзан операциялар болып табылады. Жұмыста дұрыстық дәлелі, күрделілік талдауы және қолдану мысалдары келтірілген.