# Simplify expressions with modulo 2 (Boolean algebra)

Suppose I have a (Boolean algebra) expression

a = p1 x^2 + p2 x (x-1) + 3 p3 + 4 p4 x


where p1, ..., p4 are either 0 or 1, and x is an integer. I want to simplify Mod[a,2] (the motivation is that a Pi is the phase angle of some complex number, so a Pi can be shifted by integer multiples of 2 Pi). Since x(x-1) and 4x are always even numbers, and x^2, x have the same parity, we have the simpler expression

a = p1 x + p3   ( mod 2 )


How can I achieve such simplifications in Mathematica?

• Factor[a , Modulus -> 2]? Commented Aug 21, 2023 at 10:48
• This gives p1 x^2 + p2 x(x+1) + p3, which is not the simplest possible expression. Commented Aug 21, 2023 at 12:15

You are working in a Boolean algebra (this should be stated explicitly). So there are reduction relations. We'll compute those first.

a = p1 x^2 + p2 x (x - 1) + 3 p3 + 4 p4 x;
vars = Variables[a];
reductions = Map[#^2 + # &, vars]

(* Out[83]= {p3 + p3^2, p4 + p4^2, x + x^2, p2 + p2^2, p1 + p1^2} *)


Now use PolynomialReduce to apply these relations.

PolynomialReduce[a, reductions, vars, Modulus -> 2][[2]]

(* Out[84]= p3 + p1 x *)