I've been working on a problem and in order to prove the bigger picture, I need to understand how a binary OR function can be computed by a constant fan-in MOD3 gate. I would seem that the output would need to depend on every input bit as just looking at some of them would leave out the possibility that those that weren't looked at could change the answer. Any help is appreciated.
Well a MOD3 gate would output 1 iff the remainder after dividing the sum of the input bits by 3 is non-zero.
Well in this case an OR gate is simply a MOD3 gate with fan-in 2. Consider the truth table:
A B (A + B) % 3 OUT 0 0 0 0 0 1 1 1 1 0 1 1 1 1 2 1