Parity of Integers

Parity is a term we use to express if a given integer is even or odd. The parity of a number depends only on its remainder after dividing by \( 2\). An even number has parity \(0\) because the remainder after dividing by \(2\) is \(0\), while an odd number has parity \(1\) because the remainder after dividing by \(2\) is \(1\).

Here are a few arithmetic rules of parity that are extremely useful:

1. even \( \pm\) even = even
2. odd \( \pm\) odd = even
3. even \( \pm\) odd = odd
4. even \( \times\) even = even
5. even \(\times\) odd = even
6. odd \( \times\) odd = odd.

Parity is often useful for verifying whether an equality is true or false by using the parity rules of arithmetic to see whether both sides have the same parity.

If  \(n\) is an integer, what is the parity of \(2n+2\)?

---

Since \(n\) is an integer, \(n+1\) is also an integer. Thus, \(2n+2 = 2(n+1) + 0\) shows that the parity of \(2n+2\) is \(0\). \(_\square\)

If \(a, b\) are integers, what is the parity of \(a \times b\)?

---

We know that an odd number multiplied by an odd number remains odd, an even number multiplied an odd number is even, and an even number multiplied by an even number is even. This can be summarized as (check for yourself)

\[(\mbox{Parity of } a) \times (\mbox{Parity of } b) = (\mbox{Parity of } ab). \ _\square \]

If \(k\) is an integer, what is the parity of \( k^2 + k\)?

---

\( k^2 + k = k (k+1)\). Note that \( k\) and \( (k+1)\) have different parities. Hence, by the arithmetic rules of parity, the parity of \( k(k+1)\) is \( 0\). \(_\square\)

Do you know what's odd? Integers that aren't divisible by \(2\)! Another way of stating this is that a number \(n\) is odd iff \(n \equiv 1 \pmod2\). Integers congruent to \(0 \pmod2\) are called even.

In mathematical problem solving, parity is often useful. There are several properties of odd and even numbers that can be extremely useful in problem solving.

[RMO 2016]
\[f(x)=x^{3}-(k-3)x^{2}-11x+(4k-8)\]

Find all integers \(k\) such that the roots of \(f(x)\) are integers.

---

Let \(a,b,c\) be the integral roots of \(f(x),\) then

\[a+b+c=(k-3),\quad ab+bc+ac=-11,\quad abc=4(2-k).\]

Since \(a,b,c\) are integers and \(abc=4(2-k),\) at least one of \(a, b, c\) is even, or \(k=2.\) But \(k=2\) doesn’t give integral roots. Then, since \(ab+bc+ac=-11\) and thus it's not possible that two or three of \({a,b,c}\) are even, it follows that only one of them is even.

Without loss of generality, let \(a\) be even, then \(a+b+c=k-3\) is even, which implies \(k\) is odd. Then since \(f(x)=(x-a)(x-b)(x-c),\) for an integer \(x,\) \(f(x)\) is also an integer.

Note that, with \(x=2,\) the \(k\) term disappears in \(f(x)=x^{3}-(k-3)x^{2}-11x+(4k-8).\) Then plugging \(x=2\) into \(f(x)\) gives \(f(2)=(2-a)(2-b)(2-c)=-10.\) Since \(a\) is even, \((2-a)=-2\) or \((2-a)=2,\) where \(2-a=-2\) is the essential case as \(2-a=2\) makes \(k\) even.

So \(a=4\) is a root of \(f(x).\) Plugging \(x=4\) into \(f(x),\) we get

\[k=5,\quad b=1,\quad c=-3,\]

which matches our condition that \({k,b,c}\) are all odd. \(_\square\)

Parity appears in problem solving and can prove basic, but interesting results:

John had \(r\) boxes of chocolates, where \(r\) is an odd number, and each box contained \(m\) chocolates, where \(m=2n\) for some positive integer \(n\).

John's friend Alex stole \(w\) boxes from John. Alex was in such a hurry that he mistakenly put 1 chocolate from one of the stolen boxes into one of those \(r-w\) remaining (unstolen) boxes. He thought that John would not notice anything since \(r\) was quite a big number. However, John mathematically proved something was wrong and immediately pointed out his mischievous friend Alex.

Can you tell how?

---

Tricky question? Not quite! We have a very powerful tool in math, parity.

Initially, John had an odd number of boxes. Each box contained an even number of chocolates. So the total number of chocolates must have been even (EVEN + EVEN + EVEN + ... odd times = EVEN).

Now, let's assume for a moment that Alex just stole \(w\) boxes of chocolates "without the 1 chocolate incident." We don't know if \(w\) is even or odd. But that does not matter. Whether it was even or odd, the number of chocolates stolen would have even (EVEN + EVEN + EVEN + ... \(w\) times = EVEN), and so would have been the number of chocolates remaining.

However, because Alex put 1 chocolate from one of the stolen boxes to one of the remaining boxes, he made the parity of the final chocolates left out odd, that is, 1, opposite from the initial parity which was 0.

John must have had some kind of system to check the parity of the number of all the chocolates, and that way he must have spotted out the difference. \(_\square\)