How Does Modulo 2 Long Division Work with XOR Operations?

[fran1942]

Hello, I am trying to understand the following modulo 2 long division.
I understand that 1101 goes into 1111, so you write a 1 on the top.
The next stage after 'XOR'ing is to bring down the 1.
Now, 1101 does not go into 101, so you write a 0 at the top. So far so so good.
Now you bring down another 1 and 1101 still does not go into 1011, so how come they wrote a 1 in the third position at the top ? Shouldn't that be a zero ?

If someone could please explain where I am going wrong, I would most grateful.

 

[rcgldr]

Since modulo 2 math uses xor instead of add or subtract, then only the most sigificant bit of the divisor and current remainder / dividend matter, so 1101 "goes into" 1011 because you're using xor, not subtract. The goal during the division process is to zero out the most significant bit(s) of the current remainder / dividend.

Consider what would happen if you didn't treat 1101 as "going into" 1011, you'd be stuck with a 5 bit number (10110) and since there are no borrows when doing xor, you would never be able to clear that uppermost bit left in the remainder with an xor of 10110 and 1101.

Another way to look at these numbers is to consider them to be polynomials with 1 bit finite field (modulo 2) coefficients. This would mean that

1101 = 1 x³ + 1 x² + 0 x + 1
1011 = 1 x³ + 0 x² + 1 x + 1

So when doing modulo 2 division, then 1101 goes into any number where the x^3 coefficient is a 1.