Number TheoryDifficulty 5-451456 tagged problems

Parity

Parity is the habit of using odd and even structure as the simplest modular arithmetic argument. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$\text{even} \pm \text{even} = \text{even}, \quad \text{odd} \pm \text{odd} = \text{even}, \quad \text{even} \pm \text{odd} = \text{odd}$$

Tracking only whether numbers are odd or even — arithmetic modulo $2$ — is often enough to prove something is impossible.

Why It Works

1
Every integer is even ($\equiv 0 \pmod 2$) or odd ($\equiv 1 \pmod 2$); parity is just the residue mod $2$.
2
Adding residues mod $2$: $0+0=0$, $1+1=0$, $0+1=1$, which is exactly the even/odd addition table above.
3
A sum of integers is odd if and only if it contains an odd number of odd terms.
4
If a required outcome has the wrong parity, no arrangement of moves can reach it — parity is an invariant.

Worked Examples

Example 1

Can the numbers $1, 2, 3, \dots, 9$ be split into two groups whose sums are equal?

1
Equal sums would each be half of the total $1 + 2 + \cdots + 9 = 45$.
2
Half of $45$ is $22.5$, which is not an integer.
3
Each group sum must be a whole number, so equal integer sums are impossible.
4
Equivalently, the total $45$ is odd, and an odd number cannot be split into two equal integers.

Answer:

No — the total $45$ is odd, so equal halves are impossible.

Warm-up

The numbers $1$ through $10$ are written on a board. In one move you erase two numbers $a, b$ and write their difference $|a - b|$. After nine moves one number remains. Can it be $0$?

1
Each move replaces $a, b$ by $|a-b|$, which has the same parity as $a + b$ since $a - b$ and $a + b$ differ by the even number $2b$.
2
So the parity of the sum of all numbers on the board is invariant under every move.
3
The initial sum is $1 + 2 + \cdots + 10 = 55$, which is odd.
4
The final lone number equals that invariant sum mod $2$, so it is odd. Since $0$ is even, the answer is no.

Answer:

No — the sum stays odd, so the final number can never be $0$.

Contest level

A knight starts on a corner of an $8 \times 8$ chessboard and makes a sequence of legal knight moves. Can it return to its starting square after exactly $2025$ moves?

1
Color the board black and white as usual. Every knight move goes from a square of one color to a square of the other color.
2
So after an even number of moves the knight is on its starting color, and after an odd number of moves it is on the opposite color.
3
Returning to the start requires landing on the starting square, which has the starting color — so the number of moves must be even.
4
But $2025$ is odd, so the knight ends on the opposite color and cannot be home.

Answer:

No — returning home requires an even number of moves.

Olympiad / Challenge

Prove that the equation $x^2 + y^2 + z^2 = 2xyz$ has no solution in positive integers.

1
Prove the stronger claim that $x^2 + y^2 + z^2 = c\,xyz$ has no positive solution for any even $c$ (our equation is $c = 2$). Suppose one exists for some even $c$ and pick a solution with $x + y + z$ minimal.
2
Work mod $4$. The right side $c\,xyz$ is even, so $x^2+y^2+z^2$ is even, meaning $0$ or $2$ of $x,y,z$ are odd. Odd squares are $\equiv 1 \pmod 4$ and even squares are $\equiv 0 \pmod 4$, so '$2$ odd, $1$ even' gives $x^2+y^2+z^2 \equiv 1+1+0 = 2 \pmod 4$ — yet the even variable makes $c\,xyz \equiv 0 \pmod 4$. That contradiction ($2 \equiv 0$) rules out the $2$-odd case.
3
So all of $x, y, z$ are even: write $x = 2x_1$, $y = 2y_1$, $z = 2z_1$.
4
Substituting gives $4(x_1^2 + y_1^2 + z_1^2) = 8c\,x_1 y_1 z_1$, i.e. $x_1^2 + y_1^2 + z_1^2 = (2c)\,x_1 y_1 z_1$ — the same form with the still-even constant $2c$ and a strictly smaller sum $x_1 + y_1 + z_1$. This contradicts minimality, so no positive solution exists; in particular $x^2+y^2+z^2 = 2xyz$ has none.

Answer:

No positive-integer solutions exist (mod-$4$ parity forces infinite descent).

Going Deeper

Generalization: parity is arithmetic mod $2$, the simplest case of a coloring / invariant argument. The same idea scales to mod $3$, mod $4$, or a two-coloring of a grid: assign each state a residue or color that no allowed move can change, then show the goal has the wrong value.
Where it appears: chessboard tiling and domino problems, 'erase two and replace' process invariants, impossibility proofs for splitting sets equally, and as a first filter on Diophantine equations (check both sides mod $2$ before anything harder).
Pitfall: parity proves impossibility, never possibility. Correct parity is necessary but not sufficient — an even total does not guarantee a set can be split equally, and the right color does not guarantee a tour exists. Always supply a construction separately to prove the achievable case.

Spot the Signal

Look for problems where the key step is using odd and even structure as the simplest modular arithmetic argument.
You can describe the hard part as using odd and even structure as the simplest modular arithmetic argument, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for parity, then rewrite the givens around it.
Name the relation that makes Parity legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Parity just because the surface looks familiar; verify the required condition first.
Applying Parity because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let parity reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using odd and even structure as the simplest modular arithmetic argument.

Back to techniques

Number TheoryDifficulty 5-451456 tagged problems

Parity

Practice this technique Match my level

The Key Result

$$\text{even} \pm \text{even} = \text{even}, \quad \text{odd} \pm \text{odd} = \text{even}, \quad \text{even} \pm \text{odd} = \text{odd}$$

Tracking only whether numbers are odd or even — arithmetic modulo $2$ — is often enough to prove something is impossible.

Why It Works

1
Every integer is even ($\equiv 0 \pmod 2$) or odd ($\equiv 1 \pmod 2$); parity is just the residue mod $2$.
2
Adding residues mod $2$: $0+0=0$, $1+1=0$, $0+1=1$, which is exactly the even/odd addition table above.
3
A sum of integers is odd if and only if it contains an odd number of odd terms.
4
If a required outcome has the wrong parity, no arrangement of moves can reach it — parity is an invariant.

Worked Examples

Example 1

Can the numbers $1, 2, 3, \dots, 9$ be split into two groups whose sums are equal?

1
Equal sums would each be half of the total $1 + 2 + \cdots + 9 = 45$.
2
Half of $45$ is $22.5$, which is not an integer.
3
Each group sum must be a whole number, so equal integer sums are impossible.
4
Equivalently, the total $45$ is odd, and an odd number cannot be split into two equal integers.

Answer:

No — the total $45$ is odd, so equal halves are impossible.

Warm-up

The numbers $1$ through $10$ are written on a board. In one move you erase two numbers $a, b$ and write their difference $|a - b|$. After nine moves one number remains. Can it be $0$?

1
Each move replaces $a, b$ by $|a-b|$, which has the same parity as $a + b$ since $a - b$ and $a + b$ differ by the even number $2b$.
2
So the parity of the sum of all numbers on the board is invariant under every move.
3
The initial sum is $1 + 2 + \cdots + 10 = 55$, which is odd.
4
The final lone number equals that invariant sum mod $2$, so it is odd. Since $0$ is even, the answer is no.

Answer:

No — the sum stays odd, so the final number can never be $0$.

Contest level

A knight starts on a corner of an $8 \times 8$ chessboard and makes a sequence of legal knight moves. Can it return to its starting square after exactly $2025$ moves?

1
Color the board black and white as usual. Every knight move goes from a square of one color to a square of the other color.
2
So after an even number of moves the knight is on its starting color, and after an odd number of moves it is on the opposite color.
3
Returning to the start requires landing on the starting square, which has the starting color — so the number of moves must be even.
4
But $2025$ is odd, so the knight ends on the opposite color and cannot be home.

Answer:

No — returning home requires an even number of moves.

Olympiad / Challenge

Prove that the equation $x^2 + y^2 + z^2 = 2xyz$ has no solution in positive integers.

1
Prove the stronger claim that $x^2 + y^2 + z^2 = c\,xyz$ has no positive solution for any even $c$ (our equation is $c = 2$). Suppose one exists for some even $c$ and pick a solution with $x + y + z$ minimal.
2
Work mod $4$. The right side $c\,xyz$ is even, so $x^2+y^2+z^2$ is even, meaning $0$ or $2$ of $x,y,z$ are odd. Odd squares are $\equiv 1 \pmod 4$ and even squares are $\equiv 0 \pmod 4$, so '$2$ odd, $1$ even' gives $x^2+y^2+z^2 \equiv 1+1+0 = 2 \pmod 4$ — yet the even variable makes $c\,xyz \equiv 0 \pmod 4$. That contradiction ($2 \equiv 0$) rules out the $2$-odd case.
3
So all of $x, y, z$ are even: write $x = 2x_1$, $y = 2y_1$, $z = 2z_1$.
4
Substituting gives $4(x_1^2 + y_1^2 + z_1^2) = 8c\,x_1 y_1 z_1$, i.e. $x_1^2 + y_1^2 + z_1^2 = (2c)\,x_1 y_1 z_1$ — the same form with the still-even constant $2c$ and a strictly smaller sum $x_1 + y_1 + z_1$. This contradicts minimality, so no positive solution exists; in particular $x^2+y^2+z^2 = 2xyz$ has none.

Answer:

No positive-integer solutions exist (mod-$4$ parity forces infinite descent).

Going Deeper

Generalization: parity is arithmetic mod $2$, the simplest case of a coloring / invariant argument. The same idea scales to mod $3$, mod $4$, or a two-coloring of a grid: assign each state a residue or color that no allowed move can change, then show the goal has the wrong value.
Where it appears: chessboard tiling and domino problems, 'erase two and replace' process invariants, impossibility proofs for splitting sets equally, and as a first filter on Diophantine equations (check both sides mod $2$ before anything harder).
Pitfall: parity proves impossibility, never possibility. Correct parity is necessary but not sufficient — an even total does not guarantee a set can be split equally, and the right color does not guarantee a tour exists. Always supply a construction separately to prove the achievable case.

Spot the Signal

Look for problems where the key step is using odd and even structure as the simplest modular arithmetic argument.
You can describe the hard part as using odd and even structure as the simplest modular arithmetic argument, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by identify the integer constraint that calls for parity, then rewrite the givens around it.
Name the relation that makes Parity legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Do not use Parity just because the surface looks familiar; verify the required condition first.
Applying Parity because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

Let parity reveal the integer structure; then compute only what remains.

Try it on:

Practice a contest problem where the key step is using odd and even structure as the simplest modular arithmetic argument.