Consider , the set of integers. Of course, we re familiar with standard addition and subtraction on . I am going to say that two integers are "related" if their difference is divisible by 2. Therefore, and $1408$ are related, as are and . But and are not related. We can divide up the integers into classes of integers that are all related two each other. It shouldn't be too hard to see that all of the even integers are related to each other, and all of the odd integers are related to each other, but even and odd integers are not related to each other. We will represent the class of even numbers by choosing one of them, and putting it in brackets, like so: . Similarly, we will represent the class of odd numbers by . Thus, , and We can define addition between these classes by . So This is addition modulo 2. We are taking all of the integers in the first class and adding them to all the integers in the second class and seeing what class we get as a result.

Eventually, we get tired of writing the brackets, so as long as it is clear from context that means addition modulo 2, we simply write Even though it looks like we are adding numbers, remember that we are really adding classes of numbers together.

We can generalize this concept to arithmetic modulo by saying that two integers are related if their difference is divisible by . Then we get classes of integers which we can add, subtract, and multiply in the same way.

Mod just means you take the remainder after performing the division. Since 4 goes into 2 zero times, you end up with a remainder of 2.

What exactly does a modulo 2 addition stand for?

It means that numbers are considered congruent (often stated as "equal" or "equal... mod 2") when they have the same remainder when divided by two.

For example, we write $$ 1 = 3 \;\text{mod }2 $$ since $$ 3 = 1 + 2 = 1 + 2n\;, $$ where n is the integer 1.

For example, we write $$ 1 = 5 \;\text{mod }2 $$ since $$ 5 = 1 + 4 = 1 + 2n\;, $$ where n is the integer 2.

For any number that is equal to $1 + 2n$, where $n$ is an integer, we say that number "equals 1 mod 2."

For any number that is equal to $0 + 2n$, where $n$ is an integer, we say that number "equals 0 mod 2."

$$ 1 + 2n = 1 \;\text{mod }2 \\ 0 + 2n = 0 \;\text{mod }2 $$

You can consider modular arithmetic with respect to any number. It just happens that mod 2 is useful when dealing with binary numbers, since that is the base of the number system.

For example, why does A⊕A⊕B=B?

If $\oplus$ generally means addition, then the equality does not hold (in general). The equality holds when $\oplus$ means addition "mod 2," e.g., when $A$ and $B$ are bits. (Addition mod 2 on classical bits is equivalent to an XOR gate on classical bits.)

Regardless of whether $A$ is 0 or 1, we have: $$ A\oplus A = 0\;\text{mod }2 $$ since (where $A=1$ and $n=1$) $$ 1 + 1 = 2 = 0 + 2 = 0 \;\text{mod }2 $$ and (where $A=0$ and $n=0$) $$ 0 + 0 = 0 = 0 + 0 = 0 \;\text{mod }2\;. $$

Then, use that fact that modular arithmetic is associative and also $$ 0 \oplus B = B $$ for any number B.

The confusion here stems from a missing word. A correct statement is "The result of XORing two bits is the same as that of adding those two bits mod 2."

For example, $(0+1)\bmod 2 = 1\bmod 2 = 1=(0\text{ XOR }1)$

and

$(1+1) \bmod 2= 2\bmod 2 = 0 =(1\text{ XOR }1)$

He meant that taking number mod 2^n is equivalent to stripping off all but the n lowest-order (right-most) bits of number.

For example, if n == 2,

number      number mod 4
00000001      00000001
00000010      00000010
00000011      00000011
00000100      00000000
00000101      00000001
00000110      00000010
00000111      00000011
00001000      00000000
00001001      00000001
etc.

So in other words, number mod 4 is the same as number & 00000011 (where & means bitwise-and)

Note that this works exactly the same in base-10: number mod 10 gives you the last digit of the number in base-10, number mod 100 gives you the last two digits, etc.