Parity and structure

This chapter rigorously explores the fundamental concepts of parity and structural properties within number theory. Mastery of these techniques is crucial for constructing elegant proofs and solving complex problems frequently encountered in CMI examinations, particularly those involving divisibility and integer properties.

---

Chapter Contents

| Topic |

|---|-------| | 1 | Even-odd arguments | | 2 | Mixed modular-parity problems | | 3 | Prime-power structure | | 4 | Contradiction via divisibility |

---

We begin with Even-odd arguments.

Part 1: Even-odd arguments

Even-Odd Arguments

Overview

Parity arguments use the distinction between even and odd integers to prove divisibility, impossibility, and structural properties. They are among the simplest tools in number theory, but at exam level they become powerful because they often give a contradiction immediately when other methods look complicated. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Use parity to simplify equations and expressions.

Track the parity of sums, products, and powers.

Detect contradictions by comparing both sides modulo $2$ or $4$ .

Recognise when an argument needs only parity and not heavier modular arithmetic.

Solve structural number theory problems using even-odd reasoning.

---

Core Facts

📐 Parity Rules

For integers:

even $\pm$ even = even

even $\pm$ odd = odd

odd $\pm$ odd = even

even $\times$ anything = even

odd $\times$ odd = odd

📐 Squares and Parity

square of an even integer is even

square of an odd integer is odd

In fact,

even square $\equiv 0 \pmod 4$

odd square $\equiv 1 \pmod 4$

---

Minimal Worked Examples

Example 1 Can

\qquad x+y

be odd if both

x

and

y

are odd? Yes, because

\qquad \text{odd}+\text{odd}=\text{even}

So it cannot be odd. --- Example 2 Show that if

\qquad n^2

is even, then

n

is even. If

n

were odd, then

n^2

would also be odd, contradiction. So

n

must be even. --- Example 3 Show that there are no integers satisfying

\qquad x^2+y^2=4k+3

Squares modulo

4

are only

\qquad 0

1

\qquad x^2+y^2

can only be

\qquad 0,1,2 \pmod 4

It can never be

\qquad 3 \pmod 4

Hence such an equation has no integer solution. ---

Standard Uses of Parity

📐 Common Parity Applications

proving existence or nonexistence of integer solutions

showing an expression is divisible by $2$

checking whether a square/root can exist

distinguishing cases by even/odd structure

proving one variable must have a certain parity

---

Common Patterns

❗ Typical Moves

write an integer as $\qquad 2k$ if even

write an integer as $\qquad 2k+1$ if odd

compare parity of both sides of an equation

reduce modulo $2$ or $4$ when squares are involved

---

Common Mistakes

⚠️ Avoid These Errors

❌ Thinking odd + odd is odd

✅ It is even

❌ Using only modulo $2$ for square problems when modulo $4$ is sharper

✅ Odd squares are

1

modulo

4

❌ Forgetting that product parity is easier than sum parity

✅ One even factor makes the whole product even

---

CMI Strategy

💡 How to Use Even-Odd Arguments

First ask whether only parity is enough.

If squares appear, think modulo $4$ quickly.

If a product appears, inspect whether any factor must be even.

Try contradiction by assuming the “wrong” parity.

---

Practice Questions

:::question type="MCQ" question="If

n

is odd, then

n^2

is" options=["even","odd","a multiple of

4

","always prime"] answer="B" hint="Use the parity of odd products." solution="If

n

is odd, then

n\cdot n

is odd times odd, which is odd. Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="What is the remainder when the square of an odd integer is divided by

4

?" answer="1" hint="Write the odd integer as

2k+1

." solution="Let the odd integer be

\qquad 2k+1

Then its square is

\qquad (2k+1)^2 = 4k^2+4k+1 = 4(k^2+k)+1

So the remainder upon division by

4

\boxed{1}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["Even + odd = odd","Odd + odd = even","Odd × odd = odd","If

n^2

is even, then

n

is odd"] answer="A,B,C" hint="Use the standard parity rules." solution="1. True.

True.

False. If

n^2

is even, then

n

must be even.

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Show that there are no integers

x,y

such that

x^2+y^2=4k+3

for some integer

k

." answer="Squares modulo

4

are only

0

1

, so the sum cannot be

3

modulo

4

." hint="Reduce both squares modulo

4

." solution="For any integer, its square is congruent to either

\qquad 0

1 \pmod 4

\qquad x^2+y^2

can only be

\qquad 0+0,\ 0+1,\ 1+0,\ 1+1 \pmod 4

That is, the possible residues are

\qquad 0,1,2 \pmod 4

It can never be

\qquad 3 \pmod 4

Hence there do not exist integers

x,y

such that

\qquad x^2+y^2=4k+3

So the statement is proved." ::: ---

Summary

❗ Key Takeaways for CMI

Parity is often the quickest number-theoretic tool.

Sums and products behave differently under parity.

Squares are especially well-controlled modulo $4$ .

Many impossibility proofs begin with an even-odd contradiction.

Always try parity before using heavier machinery.

---

💡 Next Up

Proceeding to Mixed modular-parity problems.

---

Part 2: Mixed modular-parity problems

Mixed Modular-Parity Problems

Overview

Mixed modular-parity problems combine two of the strongest elementary tools in number theory:

parity — whether numbers are even or odd,

modular arithmetic — what remainders numbers leave upon division by a fixed modulus.

These problems are common in proof-based exams because they often let you prove strong impossibility statements without long computations. The PYQ for this topic is a good example: the real heart of the problem is to track when something can be a perfect square, and that usually means checking parity of exponents and modular restrictions on squares. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

combine parity reasoning with modular arithmetic,

identify the possible residues of squares modulo $4$ and $8$ ,

prove that certain numbers cannot be perfect squares,

use parity of prime exponents to test square-ness,

handle proof-style number theory questions using contradiction and casework.

---

Core Idea

📖 Parity

An integer is:

even if it is of the form $2k$ ,

odd if it is of the form $2k+1$ ,

for some integer

k

📖 Congruence

For integers $a,b,m$ with $m\ge 1$ , we write

$\qquad a \equiv b \pmod m$

if $m$ divides $a-b$ .

This means

a

and

b

leave the same remainder on division by

m

. ---

Why These Two Tools Work Well Together

❗ Main Strategy

Parity gives coarse structure:

even or odd,

divisible by $2$ or not.

Modular arithmetic refines that:

modulo $4$ ,

modulo $8$ ,

modulo other useful bases.

In many exam problems, parity alone gives the first idea, and modular arithmetic finishes the contradiction.

---

Squares and Their Residues

📐 Possible Squares Modulo

4

Every integer square is congruent to either

$\qquad 0 \quad \text{or} \quad 1 \pmod 4$

Reason: If

n

is even, write

n=2k

. Then

\qquad n^2=4k^2 \equiv 0 \pmod 4

n

is odd, write

n=2k+1

. Then

\qquad n^2=(2k+1)^2=4k(k+1)+1 \equiv 1 \pmod 4

So a square can never be congruent to

2

3

modulo

4

. ---

📐 Possible Squares Modulo

8

Every integer square is congruent to one of

$\qquad 0,\ 1,\ 4 \pmod 8$

In particular, every odd square satisfies

\qquad n^2 \equiv 1 \pmod 8

::: Reason: If

n

is odd, write

n=2k+1

. Then

\qquad n^2 = 4k(k+1)+1

Since one of

k

and

k+1

is even,

k(k+1)

is even, so

4k(k+1)

is divisible by

8

. Hence

\qquad n^2 \equiv 1 \pmod 8

::: ---

Standard Consequences

📐 Immediate Consequences

No integer of the form $4k+2$ or $4k+3$ can be a perfect square.

The square of an odd integer is always $1$ modulo $8$ .

If $a$ and $b$ are odd, then

\qquad a^2+b^2 \equiv 1+1 \equiv 2 \pmod 8

Since a square cannot be $2$ modulo $8$ , the sum of two odd squares is never a square.

---

Perfect Squares and Parity of Prime Exponents

📐 Perfect Square Criterion

A positive integer

$\qquad N = p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$

is a perfect square if and only if every exponent $e_i$ is even.

❗ Valuation Language

If $v_p(N)$ denotes the exponent of the prime $p$ in the factorization of $N$ , then

$\qquad N \text{ is a perfect square } \iff v_p(N)\text{ is even for every prime }p$

This is one of the most important bridges between parity and factorization. ---

Why This Matters in Harder Problems

The PYQ attached to this topic is not a routine remainder question. It is really about deciding when a large factorial expression becomes a square. In such problems, modular arithmetic may guide the idea, but the decisive step is often:

track the exponent of a prime,

check whether that exponent is even or odd.

So mixed modular-parity reasoning often means:

use modular thinking to guess the right structure,

use parity of exponents to complete the proof.

::: ---

Minimal Worked Examples

Example 1 Show that no integer of the form

4k+3

is a square. Every square is congruent to

0

1

modulo

4

. But

\qquad 4k+3 \equiv 3 \pmod 4

So it cannot be a square. --- Example 2 Show that if

a

and

b

are odd, then

a^2+b^2

is not a square. Since

a,b

are odd,

\qquad a^2 \equiv 1 \pmod 8,\qquad b^2 \equiv 1 \pmod 8

Hence

\qquad a^2+b^2 \equiv 2 \pmod 8

But a square can only be

0,1,

4

modulo

8

. So

a^2+b^2

is not a square. ---

Standard Methods

💡 Method 1: Even-Odd Case Split

When the expression depends strongly on parity:

assume the variable is even or odd,

compute the expression in each case,

derive the required conclusion.

💡 Method 2: Modulo Contradiction

To show a number cannot have a property:

assume it does,

compute its residue modulo $4$ or $8$ ,

compare with the allowed residues.

💡 Method 3: Exponent-Parity Test

When perfect squares or perfect powers are involved:

factor the number,

inspect the parity of prime exponents,

conclude whether the number can be a square.

---

Common Patterns

📐 Patterns to Recognize

prove a number is not a square using modulo $4$ or $8$ ,

show some expression is always even or always odd,

determine whether a sum of squares can be a square,

use prime-exponent parity to test square-ness,

combine congruence with contradiction in proof questions.

---

Common Mistakes

⚠️ Avoid These Errors

❌ using parity alone when modulus $4$ or $8$ is needed,

✅ refine the argument with stronger congruences

❌ forgetting that not every non-square is detected by modulo $4$ ,

✅ try modulo

8

or prime exponents if needed

❌ saying "odd square is odd" and stopping there,

✅ often the stronger fact

n^2\equiv 1 \pmod 8

is needed

❌ checking only the exponent of $2$ when proving square-ness,

✅ every prime exponent must be even

---

CMI Strategy

💡 How to Attack Mixed Modular-Parity Questions

First ask what the expression looks like modulo $2$ , $4$ , or $8$ .

If perfect squares are involved, remember the allowed square residues.

If modular checks are not decisive, switch to prime-exponent parity.

In proof problems, write the contradiction clearly.

Keep the reasoning short and structural; these problems reward clean ideas more than computation.

---

Practice Questions

:::question type="MCQ" question="Which of the following cannot be the remainder of a perfect square upon division by

8

?" options=["

0

","

1

","

4

","

5

"] answer="D" hint="List all possible square residues modulo

8

." solution="Every integer square is congruent to

0

1

, or

4

modulo

8

. Therefore

5

cannot be the remainder of a perfect square modulo

8

. Hence the correct option is

\boxed{D}

." ::: :::question type="NAT" question="If

n

is an odd integer, find the remainder when

n^2

is divided by

8

." answer="1" hint="Write

n=2k+1

." solution="Let

n=2k+1

. Then

\qquad n^2=(2k+1)^2=4k(k+1)+1

Since one of

k

and

k+1

is even,

k(k+1)

is even. So

4k(k+1)

is divisible by

8

. Therefore

\qquad n^2 \equiv 1 \pmod 8

Hence the answer is

\boxed{1}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["If

n

is odd, then

n^2 \equiv 1 \pmod 8

","If

n^2

is even, then

n

is even","There exists an integer

n

such that

n^2 \equiv 3 \pmod 4

","Consecutive integers always have opposite parity"] answer="A,B,D" hint="Recall the possible square residues modulo

4

and

8

." solution="1. True. Every odd square is congruent to

1

modulo

8

True. If

n

were odd, then

n^2

would be odd, so

n^2

even forces

n

even.

False. Squares modulo

4

can only be

0

1

True. Consecutive integers always have opposite parity.

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Prove that no integer of the form

4k+3

can be a perfect square." answer="A square is congruent only to

0

1

modulo

4

, never to

3

modulo

4

" hint="Check the two parity cases for an integer." solution="Let

n

be any integer. There are two cases. If

n

is even, then

n=2m

for some integer

m

, so

\qquad n^2=4m^2 \equiv 0 \pmod 4

n

is odd, then

n=2m+1

, so

\qquad n^2=(2m+1)^2=4m(m+1)+1 \equiv 1 \pmod 4

Thus every square is congruent to either

0

1

modulo

4

. But any integer of the form

4k+3

satisfies

\qquad 4k+3 \equiv 3 \pmod 4

Therefore no integer of the form

4k+3

can be a perfect square." ::: ---

Summary

❗ Key Takeaways for CMI

Squares modulo $4$ are only $0$ or $1$ .

Squares modulo $8$ are only $0$ , $1$ , or $4$ .

Every odd square is $1$ modulo $8$ .

A positive integer is a perfect square exactly when all prime exponents are even.

Mixed modular-parity problems often combine remainder checks with exponent parity.

---

💡 Next Up

Proceeding to Prime-power structure.

---

Part 3: Prime-power structure

Prime-Power Structure

Overview

Prime-power structure means studying an integer through the exponents in its prime factorisation. This is one of the deepest structural ideas in elementary number theory. At exam level, it is used in divisibility, gcd/lcm problems, perfect powers, and counting divisors. Instead of treating a number as a single object, we study the power of each prime separately. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Write integers in prime-power factorised form.

Use prime exponents to study divisibility.

Compute gcd, lcm, and number of divisors from factorisation.

Recognise perfect squares and perfect cubes from exponent conditions.

Solve structural problems by comparing prime powers.

---

Prime Factorisation

📖 Prime-Power Form

Every integer $n>1$ can be written uniquely as

$\qquad n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$

where the $p_i$ are distinct primes and the $e_i$ are positive integers.

This is the fundamental theorem of arithmetic. ---

Divisibility by Comparing Exponents

📐 Divisibility Criterion

If

$\qquad n=\prod p_i^{e_i},\qquad m=\prod p_i^{f_i}$

then

$\qquad m\mid n$

if and only if

$\qquad f_i \le e_i$

for every prime involved.

So divisibility is exponent-wise comparison. ---

gcd and lcm

📐 Prime-Power Rules

If
$\qquad n=\prod p_i^{e_i}$ and $\qquad m=\prod p_i^{f_i}$ , then

$\gcd(m,n)=\prod p_i^{\min(e_i,f_i)}$

$\operatorname{lcm}(m,n)=\prod p_i^{\max(e_i,f_i)}$

These formulas are among the most useful in number theory. ---

Number of Divisors

📐 Divisor Count Formula

If
$\qquad n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$

then the number of positive divisors of $n$ is

$\qquad d(n)=(e_1+1)(e_2+1)\cdots(e_k+1)$

Each exponent in a divisor can range independently from

0

up to the exponent in

n

. ---

Perfect Powers

📐 When Is a Number a Square or Cube?

$n$ is a perfect square iff every prime exponent in its factorisation is even

$n$ is a perfect cube iff every prime exponent is divisible by $3$

More generally:

$n$ is a perfect $k$ th power iff every prime exponent is divisible by $k$

::: ---

Minimal Worked Examples

Example 1 Factorise

\qquad 360

We have

\qquad 360=36\cdot 10=2^3\cdot 3^2\cdot 5

So:

prime factorisation is $\qquad 2^3\cdot 3^2\cdot 5^1$

number of divisors is $\qquad (3+1)(2+1)(1+1)=24$

--- Example 2 Find

\qquad \gcd(72,120)

Factor:

\qquad 72=2^3\cdot 3^2

\qquad 120=2^3\cdot 3\cdot 5

Take minimum exponents:

\qquad \gcd(72,120)=2^3\cdot 3=24

--- Example 3 Determine whether

\qquad 540

is a perfect square. Factor:

\qquad 540=2^2\cdot 3^3\cdot 5

The exponents are

\qquad 2,3,1

Not all are even, so

540

is not a perfect square. ---

Common Patterns

📐 Patterns to Recognise

count divisors

test divisibility

compute gcd or lcm

test for square/cube/perfect power

find the smallest multiplier to make a square or cube

---

Smallest Multiplier Idea

💡 Make a Number a Square or Cube

To make a number a perfect square, multiply by whatever primes are needed to make every exponent even.

To make a number a perfect cube, multiply by whatever primes are needed to make every exponent a multiple of $3$ .

Example:

\qquad 2^3\cdot 3^2\cdot 5^1

needs one more factor of

\qquad 3\cdot 5

to become a square. ---

Common Mistakes

⚠️ Avoid These Errors

❌ Forgetting primes with exponent $0$ when comparing gcd/lcm

✅ Missing primes matter too

❌ Using addition of exponents in gcd

✅ gcd uses minimum, lcm uses maximum

❌ Thinking a number is a square because “most” exponents are even

✅ Every exponent must satisfy the condition

---

CMI Strategy

💡 How to Use Prime-Power Structure

Factor early and factor cleanly.

Translate the question into exponent language.

Work prime by prime.

Reassemble the answer only at the end.

In divisor problems, think of independent exponent choices.

---

Practice Questions

:::question type="MCQ" question="The number of positive divisors of

2^3\cdot 3^2

is" options=["

6

","

8

","

12

","

16

"] answer="C" hint="Use the divisor count formula." solution="The number of positive divisors is

\qquad (3+1)(2+1)=4\cdot 3=12

Hence the correct option is

\boxed{C}

." ::: :::question type="NAT" question="Find

\gcd(12,18)

." answer="6" hint="Factor both numbers or use common divisors directly." solution="We have

\qquad 12=2^2\cdot 3

and

\qquad 18=2\cdot 3^2

\qquad \gcd(12,18)=2^1\cdot 3^1=6

Hence the answer is

\boxed{6}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["A perfect square has all prime exponents even","The gcd uses minimum exponents","The lcm uses maximum exponents","Every number of the form

2^a3^b

is a perfect cube"] answer="A,B,C" hint="Use the exponent interpretation of factorisation." solution="1. True.

True.

False. A number is a perfect cube only if each exponent is divisible by

3

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Find the smallest positive integer by which

2^3\cdot 3^2\cdot 5

must be multiplied to become a perfect square." answer="

15

" hint="Make each exponent even." solution="The exponents in

\qquad 2^3\cdot 3^2\cdot 5^1

are

\qquad 3,2,1

To make a perfect square, all exponents must be even.

exponent of $2$ needs one more factor of $2$

exponent of $3$ is already even

exponent of $5$ needs one more factor of $5$

So the smallest multiplier is

\qquad 2\cdot 5=10

Therefore the answer is

\boxed{10}

." ::: ---

Summary

❗ Key Takeaways for CMI

Prime-power form reveals the structure of an integer.

Divisibility, gcd, and lcm are all exponent comparisons.

Divisor counting comes from exponent choices.

Perfect powers are determined by divisibility of exponents.

Working prime by prime often turns a hard problem into a routine one.

---

💡 Next Up

Proceeding to Contradiction via divisibility.

---

Part 4: Contradiction via divisibility

Contradiction via Divisibility

Overview

This topic is about proving that an integer equation has no nontrivial solution by showing that any supposed solution must become smaller in a controlled way, or must satisfy impossible divisibility conditions. In CMI-style number theory, this often appears through modular arithmetic, parity, divisibility by primes, and infinite descent. The central pattern is:

assume a nonzero integer solution exists

choose one with smallest possible size

prove that all variables must be divisible by some integer

divide through and obtain a smaller solution

contradiction

This is one of the cleanest forms of proof by contradiction in number theory. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Use modular arithmetic to restrict square values.

Force divisibility of variables from an equation.

Apply contradiction using a minimal counterexample.

Recognize infinite descent structure in Diophantine equations.

Use parity and modular residues together in a proof.

---

Core Idea

📖 Proof by Contradiction

To prove a statement is true, assume it is false and derive an impossibility.

In this topic, the contradiction usually comes from showing that if a nonzero integer solution exists, then a smaller nonzero integer solution also exists. That cannot happen if we began with the smallest one.

📖 Infinite Descent

Infinite descent is a method where a supposed positive or nonzero integer solution gives rise to another strictly smaller solution of the same type, and then another smaller one, and so on. This is impossible in the integers.

---

Minimal-Value Setup

❗ Standard Starting Point

When proving that an equation has only the trivial integer solution, a common setup is:

Assume there exists a nonzero integer solution. Among all such solutions, choose one for which

$\qquad |x|+|y|+|z|$

is as small as possible.

This lets you use contradiction later by constructing a new solution with smaller total size. ---

Square Residues Modulo Small Integers

📐 Squares Modulo 2

A perfect square modulo $2$ can only be

$\qquad 0 \text{ or } 1$

📐 Squares Modulo 3

A perfect square modulo $3$ can only be

$\qquad 0 \text{ or } 1$

Reason:

$0^2 \equiv 0 \pmod 3$

$1^2 \equiv 1 \pmod 3$

$2^2 \equiv 1 \pmod 3$

📐 Squares Modulo 4

A perfect square modulo $4$ can only be

$\qquad 0 \text{ or } 1$

📐 Squares Modulo 8

A perfect square modulo $8$ can only be

$\qquad 0,1,4$

📐 Squares Modulo 5

A perfect square modulo $5$ can only be

$\qquad 0,1,4$

📐 Squares Modulo 7

A perfect square modulo $7$ can only be

$\qquad 0,1,2,4$

These small residue sets are the backbone of divisibility contradictions. ---

Standard Forcing Pattern

💡 How Divisibility Gets Forced

Suppose an equation implies

$\qquad x^2+y^2 \equiv 0 \pmod 3$

Since squares mod $3$ are only $0$ or $1$ , the only way for a sum of two squares to be divisible by $3$ is

$\qquad 0+0 \equiv 0 \pmod 3$

So both $x^2$ and $y^2$ are divisible by $3$ , which implies

$\qquad 3\mid x \quad \text{and} \quad 3\mid y$

Once two variables are divisible by

3

, substitute back into the original equation and often the third variable also becomes divisible by

3

. That is the key mechanism behind many descent proofs. ---

Example Structure: Equation of the Form $x^2+y^2=nz^2$

❗ Typical Strategy

For an equation like

$\qquad x^2+y^2=nz^2$

the standard path is:

choose a nonzero solution with smallest possible size

reduce modulo a prime dividing $n$ or otherwise useful

force divisibility of $x$ and $y$

substitute back to force divisibility of $z$

divide all variables by that prime

obtain a smaller solution

contradiction

This is especially effective when the coefficient

n

has a prime factor whose square residues are restrictive. ---

Why Divisibility of a Square Implies Divisibility of the Number

📐 Basic Fact

If a prime $p$ divides $x^2$ , then $p$ divides $x$ .

For small-prime problems, this is used constantly. Examples:

if $3\mid x^2$ , then $3\mid x$

if $5\mid x^2$ , then $5\mid x$

---

Minimal Worked Example

Example 1 Show that the only integer solution to

\qquad x^2+y^2=3z^2

\qquad x=y=z=0

Assume a nonzero integer solution exists and choose one with smallest value of

\qquad |x|+|y|+|z|

. Now reduce modulo

3

. Squares mod

3

are only

0

1

. Since

\qquad x^2+y^2=3z^2

, the left side must be divisible by

3

. The only possible sum of two square residues giving

0

mod

3

\qquad 0+0

. So

\qquad 3\mid x \quad \text{and} \quad 3\mid y

. Write

\qquad x=3a,\quad y=3b

. Then

\qquad 9a^2+9b^2=3z^2

\qquad 3a^2+3b^2=z^2

. Hence

\qquad 3\mid z^2

, so

\qquad 3\mid z

. Thus all of

x,y,z

are divisible by

3

. Dividing by

3

gives a smaller nonzero integer solution, contradicting minimality. Therefore the only integer solution is

\qquad \boxed{x=y=z=0}

. ---

Modulo Choice Matters

⚠️ Not Every Modulus Helps

In contradiction-via-divisibility proofs, the modulus must be chosen intelligently.

A useful modulus is one where the set of square residues is restrictive enough to force a variable or variables to be divisible by that modulus.

Sometimes:

modulo $3$ works

modulo $5$ does not

modulo $7$ gives weaker information

So the best modulus is not always the largest divisor.

---

Common Patterns

💡 Recognize These Problem Types

Show a Diophantine equation has only the trivial solution.

Show an equation has no integer solution.

Prove a number cannot be represented in a certain form.

Use parity first, then a modulus such as $3$ or $4$ .

Use a prime divisor of a coefficient to start infinite descent.

---

Common Mistakes

⚠️ Avoid These Errors

❌ assuming a modulus works without listing square residues

✅ compute the square residues first

❌ proving only one variable is divisible by a prime when actually both are forced

✅ check all residue combinations carefully

❌ dividing by a number without first proving divisibility

✅ every division step must be justified

❌ forgetting to explain why the new solution is smaller

✅ minimal-counterexample proofs need this explicitly

❌ confusing “divisible by $p$ ” with “congruent to $0$ mod $p$ ” without context

✅ connect the two carefully

---

CMI Strategy

💡 How to Attack These Problems

Assume a nontrivial integer solution exists.

Choose one of minimal size.

Compute square residues modulo a useful prime.

Force divisibility of variables.

Substitute back into the equation.

Show all variables share the divisor.

Divide to get a smaller solution.

Contradict minimality.

---

Practice Questions

:::question type="MCQ" question="A perfect square modulo

3

can have which of the following remainders?" options=["

0,1

","

0,2

","

1,2

","

0,1,2

"] answer="A" hint="Check the residues of

0^2,1^2,2^2

modulo

3

." solution="Modulo

3

\qquad 0^2\equiv 0,\quad 1^2\equiv 1,\quad 2^2\equiv 1

So the only possible square residues mod

3

are

\boxed{0,1}

. Hence the correct option is

\boxed{A}

." ::: :::question type="NAT" question="How many possible square residues are there modulo

4

?" answer="2" hint="Check

0^2,1^2,2^2,3^2

modulo

4

." solution="Modulo

4

\qquad 0^2\equiv 0,\quad 1^2\equiv 1,\quad 2^2\equiv 0,\quad 3^2\equiv 1

So the possible square residues mod

4

are

\{0,1\}

, which has

\boxed{2}

elements." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["If

3\mid x^2

, then

3\mid x

","A proof by infinite descent starts from a smallest positive or nonzero solution","Squares modulo

5

can only be

0,1,4

","If

x^2+y^2\equiv 0\pmod 3

, then automatically

x\equiv y\equiv 0\pmod 3

"] answer="A,B,C,D" hint="Use square residues modulo

3

and

5

." solution="1. True.

True.

True, since the square residues mod

5

are

0,1,4

True, because mod

3

squares are only

0

1

, and the only way to get sum

0

mod

3

0+0

Hence the correct answer is

\boxed{A,B,C,D}

." ::: :::question type="SUB" question="Show that there is no nonzero integer solution to

x^2+y^2=3z^2

." answer="All variables become divisible by

3

, giving infinite descent." hint="Use a minimal nonzero solution and reduce modulo

3

." solution="Assume there exists a nonzero integer solution and choose one with smallest value of

\qquad |x|+|y|+|z|

. Squares modulo

3

are only

0

and

1

. Since

\qquad x^2+y^2=3z^2

, the left side is divisible by

3

. The only way for a sum of two square residues modulo

3

to be

0

\qquad 0+0

. Hence

\qquad 3\mid x \quad \text{and} \quad 3\mid y

. Write

\qquad x=3a,\quad y=3b

. Then

\qquad 9a^2+9b^2=3z^2

\qquad 3a^2+3b^2=z^2

Thus

\qquad 3\mid z^2

and therefore

\qquad 3\mid z

. So all of

x,y,z

are divisible by

3

, and dividing by

3

gives a smaller nonzero integer solution, contradicting minimality. Hence no nonzero integer solution exists." ::: ---

Summary

❗ Key Takeaways for CMI

Contradiction via divisibility often works through infinite descent.

Square residues modulo small integers are essential tools.

Minimal-counterexample arguments must end with a smaller valid solution.

The choice of modulus is strategic, not automatic.

Many Diophantine impossibility results come from repeated forced divisibility.

Chapter Summary

❗ Parity and structure — Key Points

Parity arguments (even/odd analysis, modulo 2) are fundamental for proving existence, non-existence, or properties of integer solutions.
Many problems involving sums, products, or differences of integers can be significantly simplified by examining their parity or congruence modulo 2.
The prime-power structure of integers, particularly factorials and binomial coefficients, is precisely determined by Legendre's formula, $v_p(n!) = \sum_{k=1}^{\infty} \lfloor n/p^k \rfloor$ .
Understanding $v_p(n)$ (the exponent of the highest power of prime $p$ dividing $n$ ) is crucial for divisibility proofs and finding the largest power of an integer dividing a product.
Problems combining parity with other modular arithmetic concepts often require careful analysis of congruences modulo small primes or powers of 2.
Proof by contradiction, especially when applied through divisibility or parity arguments, is a powerful technique to establish the impossibility of certain conditions.

Chapter Review Questions

:::question type="MCQ" question="Can the equation $x^2 + y^2 = 2023$ have integer solutions for $x$ and $y$ ?" options=["Yes, for specific integers $x,y$ .","Yes, for any integers $x,y$ .","No, because $2023$ is an odd number.","No, because $2023 \equiv 3 \pmod 4$ ."] answer="No, because $2023 \equiv 3 \pmod 4$ ." hint="Consider the possible values of squares modulo 4." solution="The square of any integer $n$ satisfies $n^2 \equiv 0 \pmod 4$ if $n$ is even, and $n^2 \equiv 1 \pmod 4$ if $n$ is odd. Therefore, $x^2+y^2 \pmod 4$ can only be $0+0=0$ , $0+1=1$ , or $1+1=2$ . The number $2023 = 4 \times 505 + 3$ , so $2023 \equiv 3 \pmod 4$ . Since $x^2+y^2$ can never be congruent to $3 \pmod 4$ , there are no integer solutions for $x^2+y^2=2023$ ."
:::

:::question type="NAT" question="Find the largest integer $k$ such that $3^k$ divides $100!$ ." answer="48" hint="Apply Legendre's formula for $v_p(n!)$ ." solution="Using Legendre's formula, $k = v_3(100!) = \lfloor 100/3 \rfloor + \lfloor 100/3^2 \rfloor + \lfloor 100/3^3 \rfloor + \lfloor 100/3^4 \rfloor + \dots$
$k = \lfloor 33.33 \rfloor + \lfloor 11.11 \rfloor + \lfloor 3.70 \rfloor + \lfloor 1.23 \rfloor + \dots$
$k = 33 + 11 + 3 + 1 = 48$ .
Thus, the largest integer $k$ is 48."
:::

:::question type="MCQ" question="Which statement correctly proves that there are no integers $x, y$ such that $x^2 - y^2 = 2022$ ?" options=["This statement is false; such integers exist.","The equation implies $x-y$ and $x+y$ have different parities, which is impossible.","The equation implies $x-y$ and $x+y$ are both even, leading to a contradiction modulo 4.","The equation implies $x-y$ and $x+y$ are both odd, which is impossible."] answer="The equation implies $x-y$ and $x+y$ are both even, leading to a contradiction modulo 4." hint="Factor the left-hand side and analyze the parities of the factors." solution="We have $x^2 - y^2 = (x-y)(x+y) = 2022$ .
Since $2022$ is an even number, its factors $(x-y)$ and $(x+y)$ must either both be even or one is even and one is odd.
Consider the sum and difference of the factors: $(x-y) + (x+y) = 2x$ and $(x+y) - (x-y) = 2y$ .
If one factor were even and the other odd, then $2x$ and $2y$ would be odd, which is impossible for integers $x,y$ .
Therefore, both $(x-y)$ and $(x+y)$ must be even.
Let $x-y = 2a$ and $x+y = 2b$ for some integers $a,b$ .
Substituting these into the equation: $(2a)(2b) = 2022 \implies 4ab = 2022$ .
Dividing by 2, we get $2ab = 1011$ .
However, $1011$ is an odd number, while $2ab$ must always be an even number. This is a contradiction.
Thus, no such integers $x,y$ exist."
:::

:::question type="NAT" question="What is the largest integer $n$ such that $5^n$ divides the product of the first 100 positive even integers?" answer="24" hint="Rewrite the product in terms of a factorial and then apply Legendre's formula." solution="The product of the first 100 positive even integers is $P = 2 \cdot 4 \cdot 6 \cdots 200$ .
This can be written as $P = (2 \cdot 1) \cdot (2 \cdot 2) \cdot (2 \cdot 3) \cdots (2 \cdot 100) = 2^{100} \cdot (1 \cdot 2 \cdot 3 \cdots 100) = 2^{100} \cdot 100!$ .
We need to find the largest $n$ such that $5^n$ divides $P$ . This is equivalent to finding $v_5(P) = v_5(2^{100} \cdot 100!)$ .
Using the property $v_p(ab) = v_p(a) + v_p(b)$ , we have $v_5(P) = v_5(2^{100}) + v_5(100!)$ .
Since $5$ is not a factor of $2^{100}$ , $v_5(2^{100}) = 0$ .
So we need to calculate $v_5(100!)$ using Legendre's formula:
$v_5(100!) = \lfloor 100/5 \rfloor + \lfloor 100/5^2 \rfloor + \lfloor 100/5^3 \rfloor + \dots$
$v_5(100!) = \lfloor 20 \rfloor + \lfloor 4 \rfloor + \lfloor 0.8 \rfloor + \dots$
$v_5(100!) = 20 + 4 + 0 = 24$ .
Thus, the largest integer $n$ is 24."
:::

What's Next?

💡 Continue Your CMI Journey

Having mastered parity and prime-power structures, you are well-equipped to tackle more advanced topics. The concepts learned here are foundational for Diophantine Equations, where integer solutions are sought, often leveraging modular arithmetic and divisibility. Furthermore, the understanding of $v_p(n)$ is directly applicable to Number Theoretic Functions (e.g., $\tau(n), \sigma(n)$ ) and advanced Modular Arithmetic involving higher powers and orders. Continue your exploration by applying these tools to complex problems in these interconnected domains.

Parity and structure

Parity and structure

Chapter Contents

| Topic |

Part 1: Even-odd arguments

Even-Odd Arguments

Overview

Learning Objectives

Core Facts

Minimal Worked Examples

Standard Uses of Parity

Common Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 2: Mixed modular-parity problems

Mixed Modular-Parity Problems

Overview

Learning Objectives

Core Idea

Why These Two Tools Work Well Together

Squares and Their Residues

Standard Consequences

Perfect Squares and Parity of Prime Exponents

Why This Matters in Harder Problems

Minimal Worked Examples

Standard Methods

Common Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 3: Prime-power structure

Prime-Power Structure

Overview

Learning Objectives

Prime Factorisation

Divisibility by Comparing Exponents

gcd and lcm

Number of Divisors

Perfect Powers

Minimal Worked Examples

Common Patterns

Smallest Multiplier Idea

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 4: Contradiction via divisibility

Contradiction via Divisibility

Overview

Learning Objectives

Core Idea

Minimal-Value Setup

Square Residues Modulo Small Integers

Standard Forcing Pattern

Example Structure: Equation of the Form x2+y2=nz2x^2+y^2=nz^2x2+y2=nz2

Why Divisibility of a Square Implies Divisibility of the Number

Minimal Worked Example

Modulo Choice Matters

Common Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Chapter Summary

Chapter Review Questions

What's Next?

🎯 Key Points to Remember

Related Topics in Number Theory

Congruences

GCD and LCM

Divisor-based problems

Cyclic behaviour

More Resources

Study Notes

Short Notes

Test Series

Mock Tests

Example Structure: Equation of the Form $x^2+y^2=nz^2$