Parity of Integers
Contents
Definition
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 . An even number has parity because the remainder after dividing by is , while an odd number has parity because the remainder after dividing by is .
Here are a few arithmetic rules of parity that are extremely useful:
- even even = even
- odd odd = even
- even odd = odd
- even even = even
- even odd = even
- odd 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 is an integer, what is the parity of ?
Since is an integer, is also an integer. Thus, shows that the parity of is .
If are integers, what is the parity of ?
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)
If is an integer, what is the parity of ?
. Note that and have different parities. Hence, by the arithmetic rules of parity, the parity of is .
Do you know what's odd? Integers that aren't divisible by ! Another way of stating this is that a number is odd iff . Integers congruent to 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]
Find all integers such that the roots of are integers.
Let be the integral roots of then
Since are integers and at least one of is even, or But doesn’t give integral roots. Then, since and thus it's not possible that two or three of are even, it follows that only one of them is even.
Without loss of generality, let be even, then is even, which implies is odd. Then since for an integer is also an integer.
Note that, with the term disappears in Then plugging into gives Since is even, or where is the essential case as makes even.
So is a root of Plugging into we get
which matches our condition that are all odd.
Problem Solving
Parity appears in problem solving and can prove basic, but interesting results:
John had boxes of chocolates, where is an odd number, and each box contained chocolates, where for some positive integer .
John's friend Alex stole 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 remaining (unstolen) boxes. He thought that John would not notice anything since 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 boxes of chocolates "without the 1 chocolate incident." We don't know if 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 + ... 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.