# Divisibility represented by Boolean logic

Some context: I was thinking about the feasibility of using SAT solvers to prove primality, especially of Mersenne primes, by showing that there exists no Boolean sequence $$d_1,d_2, ..., d_{b'}$$ that can represent a divisor of the prime (i.e. UNSAT).

Given a Boolean list $$d_1,d_2, ..., d_{b'}$$, where $$d$$ is the base-2 representation of a base-10 positive integers $$D$$, does there exist a Boolean predicate that evaluates to True if and only if $$2^b-1 \equiv 0 ($$mod D)$? (Assume $$1 < D < N$$, and hence, $$b' < b$$. Also assume $$b$$ is prime.) Any help is greatly appreciated. • Isn't it just the case that any boolean-valued function of$b+b'$boolean variables can be represented using Boolean algebra operations? – Daniel Schepler Feb 13 at 0:46 ## 1 Answer You could use a circuit which performs a modular reduction as explained in this lecture note (chapter 2.6.4 on page 32). The modular reduction computes the remainder of the division $$N/D$$. Use a digital comparator circuit to check for zero remainder. When the remainder vanishes to zero, the predicate becomes true. From the cited lecture note: Note that this might not fully answer your question as it assumes $$D$$ to be a constant rather than a variable. • Close. However, can this be directly evaluated with Boolean logic? I want to implement the predicate directly (i.e. a sequence of logical operations). This is an interesting idea, though. – Baaing Cow Feb 12 at 22:52 • Yes. An alternative would be to calculate the remainder$R$as$R = N - D * (N/D)\$. But that would require a divider, a subtractor and a multiplier. – Axel Kemper Feb 12 at 22:55
• Subtraction and multiplication of Boolean arrays can be done as if it was in base-2. (subtraction is trivial XOR and NAND for carrying, multiplication can be expanded into addition, i.e. XOR and AND) This question concerns division. – Baaing Cow Feb 12 at 23:12
• Divider circuits are actually described in the above-mentioned book Basic Arithmetic Circuits. My point ist that modular reduction is less complex than the classic remainder calculation. – Axel Kemper Feb 13 at 7:54