Cyclic behaviour

This chapter delves into the fundamental principles of cyclic behaviour within Number Theory, providing essential tools for analyzing repeating patterns in integers and sequences. A strong grasp of these concepts, encompassing residue class reasoning, periodicity, and modular exponentiation, is critical for successfully tackling advanced problems in the CMI examinations.

Chapter Contents

| Topic |

|---|-------| | 1 | Residue class reasoning | | 2 | Periodicity | | 3 | Powers modulo n | | 4 | Last digit problems |

We begin with Residue class reasoning.

Part 1: Residue class reasoning

Residue Class Reasoning

Overview

Residue class reasoning means solving a number theory problem by splitting integers according to their remainders modulo some fixed number. Instead of working with all integers at once, we work with a small number of residue classes. This method is especially useful for impossibility proofs, quadratic residue checks, and pattern detection. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Use residue classes modulo $m$ to simplify number-theoretic problems.

Test expressions by checking all possible residues.

Prove impossibility statements using modular contradictions.

Recognise the common residues of squares, cubes, and simple polynomial expressions.

Choose a useful modulus intelligently.

---

Core Idea

📖 Residue Classes

Modulo $m$ , every integer belongs to exactly one residue class

$\qquad 0,1,2,\dots,m-1$

So to understand a number-theoretic statement modulo $m$ , it is enough to check these finitely many cases.

---

Standard Residue Sets

📐 Squares Mod Small Numbers

modulo $2$ : squares are $\qquad 0,1$

modulo $3$ : squares are $\qquad 0,1$

modulo $4$ : squares are $\qquad 0,1$

modulo $5$ : squares are $\qquad 0,1,4$

modulo $8$ : squares are $\qquad 0,1,4$

These are extremely useful in impossibility proofs. ---

Choosing a Modulus

💡 Pick the Modulus That Matches the Structure

Good choices often come from:

parity $\to$ modulus $2$

squares or even/odd structure $\to$ modulus $4$ or $8$

divisibility by $3$ $\to$ modulus $3$

last digit or decimal patterns $\to$ modulus $10$

quadratic forms $\to$ modulus $4,8,3,5$

---

Minimal Worked Examples

Example 1 Can

n^2

ever be congruent to

2

modulo

4

? Squares modulo

4

are only

\qquad 0,1

\qquad n^2\equiv 2 \pmod 4

is impossible. --- Example 2 Show that no integer square is of the form

\qquad 3k+2

. Modulo

3

, a square is always

\qquad 0

1

So it can never be

\qquad 2 \pmod 3

Hence no square is of the form

\qquad 3k+2

. --- Example 3 Determine all residues of

\qquad n^2+n+1 \pmod 3

Check residues:

if $\qquad n\equiv 0$ , then $\qquad n^2+n+1\equiv 1$

if $\qquad n\equiv 1$ , then $\qquad n^2+n+1\equiv 1+1+1\equiv 0$

if $\qquad n\equiv 2$ , then $\qquad n^2+n+1\equiv 1+2+1\equiv 1$

So the expression is never congruent to

2

modulo

3

. ---

Impossibility by Residues

❗ Standard Contradiction Method

To prove an equation has no integer solution:

reduce both sides modulo a suitable integer

list all possible residues of each side

show they cannot match

This is one of the most common uses of residue classes. ---

Common Patterns

📐 Patterns to Recognise

prove a number is not a square

prove an equation has no integer solution

classify possible remainders of a sequence

show divisibility or non-divisibility

reduce a polynomial expression modulo a small number

---

Common Mistakes

⚠️ Avoid These Errors

❌ Choosing a modulus that gives no useful restriction

✅ Pick a modulus linked to the structure

❌ Forgetting to test all residue classes

✅ Check each case systematically

❌ Assuming all residues occur for squares or cubes

✅ List them explicitly

❌ Mixing ordinary equality with congruence

---

CMI Strategy

💡 How to Use Residue Classes

Look for structure: square, cube, parity, divisibility, last digit.

Choose a small modulus that sharply restricts possibilities.

Compute the possible residue set.

Compare with the claimed form.

Use contradiction if the target residue is impossible.

---

Practice Questions

:::question type="MCQ" question="Which of the following can be a square modulo

4

?" options=["

0

","

2

","

3

","Only

2

and

3

"] answer="A" hint="List the square residues modulo

4

." solution="Squares modulo

4

are only

\qquad 0,1

So among the listed options,

0

can occur, but

2

and

3

cannot. Hence the correct option is

\boxed{A}

." ::: :::question type="NAT" question="Find the remainder when

n^2+n+1

is divided by

3

n\equiv 1\pmod 3

." answer="0" hint="Substitute the residue directly." solution="If

\qquad n\equiv 1 \pmod 3

, then

\qquad n^2+n+1 \equiv 1+1+1 \equiv 0 \pmod 3

Hence the remainder is

\boxed{0}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["Every square is congruent to

0

1

modulo

3

","Every square is congruent to

0

1

modulo

4

","An integer square can be congruent to

2

modulo

4

","Residue class reasoning can be used for impossibility proofs"] answer="A,B,D" hint="Use the standard residue lists for squares." solution="1. True.

True.

False.

True.

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Show that no integer square is congruent to

2

modulo

3

." answer="Squares modulo

3

are only

0

1

." hint="Check all residues modulo

3

." solution="Any integer is congruent to one of

\qquad 0,1,2 \pmod 3

Now:

if $\qquad n\equiv 0$ , then $\qquad n^2\equiv 0$

if $\qquad n\equiv 1$ , then $\qquad n^2\equiv 1$

if $\qquad n\equiv 2$ , then $\qquad n^2\equiv 4\equiv 1$

So an integer square modulo

3

can only be

\qquad 0

1

Hence no integer square is congruent to

\boxed{2 \pmod 3}

." ::: ---

Summary

❗ Key Takeaways for CMI

Residue classes reduce infinite integer problems to finitely many cases.

Squares have very restricted residues modulo small integers.

A good modulus is chosen from the structure of the problem.

Residue class reasoning is especially strong for impossibility proofs.

Systematic case-checking is more important than clever algebra here.

---

💡 Next Up

Proceeding to Periodicity.

---

Part 2: Periodicity

Periodicity

Overview

Periodicity is the study of patterns that repeat after a fixed number of steps. In number theory, this appears in residues, last digits, powers modulo

m

, and cyclic sequences. In harder CMI-style problems, the same idea also appears geometrically: if a process “wraps around” and returns to an old state, then the motion is periodic. The key skill is to convert the problem into a repeating-state model. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Recognize periodic and eventually periodic sequences.

Find periods of powers modulo $m$ and last-digit cycles.

Use modular arithmetic to detect repetition.

Interpret wrap-around motion as periodic motion modulo $1$ .

Distinguish rational-slope periodic behaviour from irrational-slope non-repetition.

---

Core Idea

📖 Period of a sequence

A sequence $(a_n)$ is periodic with period $T>0$ if

$\qquad a_{n+T}=a_n$

for all relevant $n$ .

The smallest positive such $T$ is called the fundamental period.

📖 Eventually periodic

A sequence is eventually periodic if it becomes periodic after some initial terms.

This is common in modular arithmetic because there are only finitely many possible residues. ---

Why Modulo Sequences Repeat

❗ Finite-State Principle

If a sequence takes values only from a finite set, then some value must repeat. After that, the pattern often becomes periodic.

For example, a sequence modulo $m$ can take only $m$ residue values.

This is the main reason that residue patterns and last digits cycle. ---

Powers Modulo $m$

📐 Cyclic Behaviour of Powers

For fixed integers $a,m$ with $m\ge 2$ , the sequence

$\qquad a,\ a^2,\ a^3,\dots \pmod m$

is eventually periodic.

If $\gcd(a,m)=1$ , the sequence is often purely periodic from the start, and the smallest positive integer $t$ satisfying

$\qquad a^t\equiv 1 \pmod m$

is called the order of $a$ modulo $m$ .

---

Last-Digit Cycles

📐 Standard Last-Digit Periods

Because last digits are just residues modulo $10$ , powers of a fixed integer have cyclic last digits.

Examples:

powers of $2$ : $\qquad 2,4,8,6$ with period $4$

powers of $3$ : $\qquad 3,9,7,1$ with period $4$

powers of $7$ : $\qquad 7,9,3,1$ with period $4$

powers of $9$ : $\qquad 9,1$ with period $2$

These are among the fastest periodicity questions in school-level number theory. ---

Linear Periodicity Modulo $m$

📐 Simple Linear Cycles

The sequence

$\qquad a_n = rn \pmod m$

is periodic.

Its period is

$\qquad \dfrac{m}{\gcd(r,m)}$

This is useful in arithmetic progressions modulo

m

and cyclic stepping problems. ---

Geometric Wrap-Around as Modulo $1$

❗ The Unit-Square Wrap-Around Model

In the square-wrap problem, instead of imagining jumps at the boundary, it is cleaner to let the particle continue in the plane and then look only at its coordinates modulo $1$ .

If the slope is $s$ , then after horizontal travel $t$ , the particle is at

$\qquad (t,st)$

in the unfolded plane.

Inside the square-with-jumps model, the visible position is

$\qquad (\{t\},\{st\})$

where $\{x\}$ denotes the fractional part of $x$ .

So the motion is a periodicity problem modulo

1

. ---

When Does the Trajectory Repeat?

📐 Repetition Condition

A repeated point occurs when

$\qquad (\{t_1\},\{st_1\})=(\{t_2\},\{st_2\})$

for some $t_2>t_1$ .

Let $T=t_2-t_1$ . Then repetition means

$\qquad T\in \mathbb{Z} <br>\quad\text{and}\quad <br>sT\in \mathbb{Z}$

So exact repetition happens if and only if there exists a positive integer

T

such that

sT

is also an integer. ---

Rational vs Irrational Slope

❗ Most Important Dichotomy

If the slope $s$ is rational, say

\qquad s=\dfrac{p}{q}

in lowest terms, then choosing

\qquad T=q

gives

\qquad sT=p\in\mathbb{Z}

so the trajectory repeats.

If the slope $s$ is irrational, then there is no positive integer $T$ for which $sT$ is an integer, so the trajectory never exactly repeats.

This is the core periodicity idea in the 2025-style trajectory problem. ---

Finite Trajectories in the Wrap Problem

📐 Reduced Rational Slope

If

$\qquad s=\dfrac{p}{q}$

with positive coprime integers $p,q$ , then the first repetition occurs after horizontal travel

$\qquad T=q$

and vertical rise

$\qquad sT=p$

So the unfolded straight-line length before repeating is

$\qquad \sqrt{q^2+p^2}$

Since at

T=q

the visible point is

\qquad (\{q\},\{p\})=(0,0)

, every finite trajectory returns to the origin. So the only possible stopping point for a finite trajectory is

\qquad (0,0)

::: ---

Integer Lengths of Finite Trajectories

💡 Pythagorean Link

For rational slope $p/q$ in lowest terms, the finite trajectory length is

$\qquad \sqrt{p^2+q^2}$

So integer lengths occur exactly when $(p,q,\ell)$ form a Pythagorean triple.

The smallest possible integer length is

\qquad 5

coming from

(p,q)=(3,4)

(4,3)

. The next one is

\qquad 13

coming from

(5,12)

(12,5)

. ::: ---

Minimal Worked Examples

Example 1 Find the period of the last digits of powers of

2

. The last digits go

\qquad 2,4,8,6,2,4,8,6,\dots

So the period is

\boxed{4}

. --- Example 2 A particle has slope

\dfrac{1}{2}

in the wrap-around square model. Since the slope is rational, the trajectory is finite. Here

p=1,\ q=2

, so the length before return is

\qquad \sqrt{1^2+2^2}=\sqrt{5}

Hence the finite trajectory length is

\boxed{\sqrt{5}}

. ---

Common Patterns

📐 What Gets Asked Often

period of last digits of powers

least $n$ such that $a^n\equiv 1\pmod m$

periodicity of linear sequences modulo $m$

rational vs irrational behaviour in cyclic motion

integer lengths arising from periodic trajectories

---

Common Mistakes

⚠️ Avoid These Errors

❌ assuming every modular sequence is purely periodic from the start

❌ confusing “eventually periodic” with “periodic”

❌ forgetting to reduce the rational slope $\dfrac{p}{q}$ to lowest terms

❌ treating irrational slope as if it might still return exactly

❌ forgetting that the wrap-around model is really modulo $1$

---

CMI Strategy

💡 How to Solve Smart

First identify the repeating state space: mod $m$ or mod $1$ .

For power cycles, compute a few terms and look for the smallest return.

In wrap-around geometry, replace “jump” language by fractional parts.

Check whether the key parameter is rational or irrational.

For finite trajectory lengths, look for Pythagorean triples.

---

Practice Questions

:::question type="MCQ" question="The period of the last digits of powers of

3

is" options=["

1

","

2

","

3

","

4

"] answer="D" hint="Write the last digits of

3^1,3^2,3^3,3^4

." solution="The last digits are

\qquad 3,9,7,1

and then the pattern repeats. So the period is

\boxed{4}

. Hence the correct option is

\boxed{D}

." ::: :::question type="NAT" question="Find the least positive integer

n

such that

2^n\equiv 1\pmod 7

." answer="3" hint="Check the small powers of

2

modulo

7

." solution="We compute:

\qquad 2^1\equiv 2\pmod 7

\qquad 2^2\equiv 4\pmod 7

\qquad 2^3\equiv 8\equiv 1\pmod 7

So the least such

n

\boxed{3}

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

m

takes values in a finite set","If the slope in the wrap-around square model is irrational, then the trajectory never exactly repeats","If the slope is

\dfrac{p}{q}

in lowest terms, then the finite trajectory length is

\sqrt{p^2+q^2}

","A finite trajectory in the wrap-around square model can stop at a point other than

(0,0)

"] answer="A,B,C" hint="Use finite-state logic and the rational/irrational split." solution="1. True. Modulo

m

, there are only

m

residue classes.

True. Exact repetition would require a nonzero integer multiple of an irrational number to become an integer, which is impossible.

True. The first return occurs after horizontal travel

q

and vertical rise

p

, so the length is

\sqrt{p^2+q^2}

False. In the reduced rational case, the first repeat is the return to

(0,0)

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Suppose the wrap-around square trajectory has slope

\dfrac{p}{q}

, where

p,q

are positive coprime integers. Show that the trajectory is finite and its length is

\sqrt{p^2+q^2}

." answer="The trajectory repeats after horizontal travel

q

, so the finite length is

\sqrt{p^2+q^2}

." hint="Write the visible position using fractional parts." solution="In the unfolded plane, after horizontal travel

t

, the particle is at

\qquad (t,\dfrac{p}{q}t)

. In the wrapped model, the visible point is

\qquad \left(\{t\},\left\{\dfrac{p}{q}t\right\}\right)

. Take

t=q

. Then

\qquad \{q\}=0

and

\qquad \left\{\dfrac{p}{q}\cdot q\right\}=\{p\}=0

. So after horizontal travel

q

, the particle returns to

(0,0)

, and hence the trajectory is finite. In the unfolded plane, the particle has moved from

(0,0)

(q,p)

, so the total traveled length is

\qquad \sqrt{q^2+p^2}

. Therefore the trajectory is finite and its length is

\boxed{\sqrt{p^2+q^2}}

." ::: ---

Summary

❗ Key Takeaways for CMI

Periodicity is repetition after a fixed step size.

Residues modulo $m$ force cyclic behaviour because the state space is finite.

Powers modulo $m$ and last digits are standard periodicity questions.

Wrap-around motion in a square is periodicity modulo $1$ .

Rational slope gives finite periodic motion; irrational slope gives no exact repetition.

---

💡 Next Up

Proceeding to Powers modulo n.

---

Part 3: Powers modulo n

Powers modulo $n$

Overview

A sequence of powers modulo

n

almost never behaves randomly for long. Because there are only finitely many residue classes modulo

n

, powers such as

a^1,a^2,a^3,\dots

eventually become periodic, and when

\gcd(a,n)=1

they are usually purely periodic from the start. This topic is central in olympiad-style number theory because it turns enormous exponents into small cycle questions. The most common exam uses are:

finding remainders of large powers,

counting how many exponents give a certain residue,

proving divisibility statements of the form $n \mid a^m-1$ ,

identifying cycle lengths and multiplicative orders.

---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Compute large powers modulo $n$ using cyclic patterns.

Define and use the multiplicative order of $a$ modulo $n$ .

Count exponents that hit a particular residue class.

Use Euler/Fermat ideas to shorten periods.

Build infinite divisibility families like $n \mid a^n-1$ in special cases.

---

Core Congruence Language

📖 Congruence modulo

n

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

$\qquad a \equiv b \pmod n$

if $n$ divides $a-b$ .

📐 Power Compatibility

If
$\qquad a \equiv b \pmod n$

then for every positive integer $k$ ,

$\qquad a^k \equiv b^k \pmod n$

So once a base is reduced modulo

n

, all further power work can be done using that reduced base. ---

Why Cycles Appear

❗ Finite residue classes force repetition

Modulo $n$ , there are only $n$ possible residue classes. So the sequence

$\qquad a^0, a^1, a^2, a^3, \dots \pmod n$

must eventually repeat. After a repeat begins, the sequence becomes periodic.

When

\gcd(a,n)=1

, the repeating behavior is especially clean. ---

Multiplicative Order

📖 Order of

a

modulo

n

If $\gcd(a,n)=1$ , the order of $a$ modulo $n$ , written $\operatorname{ord}_n(a)$ , is the smallest positive integer $d$ such that

$\qquad a^d \equiv 1 \pmod n$

📐 Main Consequence of Order

If
$\qquad d = \operatorname{ord}_n(a)$

then

$\qquad a^m \equiv a^r \pmod n \iff m \equiv r \pmod d$

So once the order is known, any huge exponent can be reduced modulo

d

. ---

Standard Example: Powers of $2$ modulo $7$

📐 Cycle for

2^k \pmod 7

Compute:

$\qquad 2^1 \equiv 2 \pmod 7$

$\qquad 2^2 \equiv 4 \pmod 7$

$\qquad 2^3 \equiv 8 \equiv 1 \pmod 7$

So the cycle is

$\qquad 2,4,1,2,4,1,\dots$

and

$\qquad \operatorname{ord}_7(2)=3$

Therefore:

if $k \equiv 0 \pmod 3$ , then $\qquad 2^k \equiv 1 \pmod 7$

if $k \equiv 1 \pmod 3$ , then $\qquad 2^k \equiv 2 \pmod 7$

if $k \equiv 2 \pmod 3$ , then $\qquad 2^k \equiv 4 \pmod 7$

This is exactly the kind of cycle-counting needed in the frog-style PYQ. ---

Counting Exponents in a Cycle

💡 How to count visits to a residue

Suppose powers repeat with period $d$ , and you know exactly which exponents modulo $d$ give the desired residue. Then the count over a range is just the count of those congruence classes inside the index interval.

Example: To count how many times

2^i \equiv 1 \pmod 7

for

0 \le i \le 99

, use the fact that this happens exactly when

\qquad i \equiv 0 \pmod 3

So the valid indices are

\qquad 0,3,6,\dots,99

which gives

\qquad \dfrac{99}{3}+1 = 34

---

Euler and Fermat as Period Bounds

📐 Euler's theorem

If $\gcd(a,n)=1$ , then

$\qquad a^{\varphi(n)} \equiv 1 \pmod n$

Hence the order of

a

modulo

n

always divides

\varphi(n)

. :::

📐 Fermat's little theorem

If $p$ is prime and $p \nmid a$ , then

$\qquad a^{p-1} \equiv 1 \pmod p$

So modulo a prime

p

, the order of

a

divides

p-1

. ::: These theorems often do not give the exact order, but they give a very useful upper bound. ---

When $\gcd(a,n)\ne 1$

⚠️ Do not assume pure cyclic behavior blindly

If $\gcd(a,n)\ne 1$ , then powers can behave differently. They may:

become $0$ modulo $n$ ,

stabilize in a smaller set,

fail to have a multiplicative order.

Example:

\qquad 2^1 \equiv 2 \pmod 8

\qquad 2^2 \equiv 4 \pmod 8

\qquad 2^3 \equiv 0 \pmod 8

and then all later powers stay

0

modulo

8

So the concept of order is used only when

\gcd(a,n)=1

. ---

Divisibility of the Form $n \mid a^n-1$

📐 Translate divisibility into congruence

The statement

$\qquad n \mid a^n - 1$

is equivalent to

$\qquad a^n \equiv 1 \pmod n$

So these questions are really about powers modulo

n

. ::: For the PYQ base

2023

, the small odd solutions start as:

$\qquad n=3$

$\qquad n=9$

because

\qquad 2023 \equiv 1 \pmod 3

and

\qquad 2023 \equiv 7 \pmod 9

with

7^3 \equiv 1 \pmod 9

, hence

7^9 \equiv 1 \pmod 9

. ---

Infinite Family from the PYQ

💡 A useful infinite family

A very important observation is that all powers of $3$ work:

$\qquad n = 3^k \quad (k\ge 1)$

Indeed, one can show

$\qquad 3^k \mid 2023^{3^k} - 1$

for every $k \ge 1$ .

A valuation argument gives even more:

$\qquad v_3(2023^{3^k}-1) = v_3(2023-1) + v_3(3^k) = 1+k$

so in fact

$\qquad 3^{k+1} \mid 2023^{3^k}-1$

This proves there are infinitely many odd integers $n>1$ such that

$\qquad n \mid 2023^n - 1$

---

Minimal Worked Examples

Example 1 Find the remainder of

3^{100}

modulo

7

. Since

\qquad 3^6 \equiv 1 \pmod 7

we reduce the exponent modulo

6

\qquad 100 \equiv 4 \pmod 6

\qquad 3^{100} \equiv 3^4 = 81 \equiv 4 \pmod 7

Hence the remainder is

\boxed{4}

. --- Example 2 Find the least positive

k

such that

\qquad 5^k \equiv 1 \pmod{11}

Compute:

\qquad 5^1 \equiv 5

\qquad 5^2 \equiv 25 \equiv 3

\qquad 5^3 \equiv 15 \equiv 4

\qquad 5^4 \equiv 20 \equiv 9

\qquad 5^5 \equiv 45 \equiv 1 \pmod{11}

Hence the least such

k

\boxed{5}

. ---

Common Mistakes

⚠️ Avoid These Errors

❌ Reducing the base incorrectly before powering.

❌ Using order without checking $\gcd(a,n)=1$ .

❌ Assuming the cycle length is always $\varphi(n)$ instead of a divisor of it.

❌ Missing the exponent $0$ when counting visits.

❌ Treating eventual repetition and pure periodicity as the same thing.

---

CMI Strategy

💡 How to attack powers modulo

n

Reduce the base modulo $n$ first.

Check whether $\gcd(a,n)=1$ .

Compute small powers until a cycle appears.

If possible, identify the exact order.

Reduce the exponent modulo the order.

For counting questions, translate the desired residue into congruence conditions on the exponent.

---

Practice Questions

:::question type="MCQ" question="The order of

2

modulo

7

is" options=["

2

","

3

","

6

","

7

"] answer="B" hint="Compute powers of

2

modulo

7

until you get

1

." solution="We compute:

\qquad 2^1 \equiv 2,\quad 2^2 \equiv 4,\quad 2^3 \equiv 8 \equiv 1 \pmod 7

So the smallest positive exponent giving

1

3

. Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="How many integers

i

with

0\le i\le 99

satisfy

2^i \equiv 1 \pmod 7

?" answer="34" hint="Use the cycle of powers of

2

modulo

7

." solution="Since

\qquad 2^3 \equiv 1 \pmod 7

, the powers repeat with period

3

, and

\qquad 2^i \equiv 1 \pmod 7

exactly when

\qquad i \equiv 0 \pmod 3

From

0

99

, the multiples of

3

are

\qquad 0,3,6,\dots,99

This gives

\qquad \dfrac{99}{3}+1 = 34

Hence the answer is

\boxed{34}

." ::: :::question type="MSQ" question="Which of the following statements are true? Assume

\gcd(a,n)=1

whenever

\operatorname{ord}_n(a)

is used." options=["If

\operatorname{ord}_n(a)=d

, then

a^d \equiv 1 \pmod n

","If

a^r \equiv 1 \pmod n

and

\operatorname{ord}_n(a)=d

, then

d

divides

r

","If

a^k \equiv 1 \pmod n

, then necessarily

\operatorname{ord}_n(a)=k

","If

\operatorname{ord}_n(a)=d

, then

a^{d+t} \equiv a^t \pmod n

for all integers

t\ge 0

"] answer="A,B,D" hint="One statement forgets the minimality condition in the definition of order." solution="1. True, by definition of order.

True. The order divides every exponent that gives residue

1

False. The order is the least positive such exponent, so

k

may be a multiple of the order.

True, since

a^{d+t} = a^d a^t \equiv 1\cdot a^t \pmod n

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Prove that the sequence

2^n \pmod 7

is periodic with period

3

, and deduce that

2^n \pmod 7

depends only on

n \pmod 3

." answer="The powers repeat as

2,4,1

with period

3

." hint="Compute the first few powers and use

2^3\equiv 1 \pmod 7

." solution="We compute:

\qquad 2^1 \equiv 2 \pmod 7

\qquad 2^2 \equiv 4 \pmod 7

\qquad 2^3 \equiv 8 \equiv 1 \pmod 7

Now for any

n\ge 0

, write

\qquad n = 3q+r

with

r\in\{0,1,2\}

. Then

\qquad 2^n = 2^{3q+r} = (2^3)^q 2^r \equiv 1^q \cdot 2^r \equiv 2^r \pmod 7

So the residue of

2^n

modulo

7

depends only on

r

, that is, only on

n \pmod 3

. Hence the powers of

2

modulo

7

are periodic with period

3

, cycling through

\qquad 1,2,4

according to the exponent class modulo

3

." ::: ---

Summary

❗ Key Takeaways for CMI

Powers modulo $n$ are controlled by periodicity.

When $\gcd(a,n)=1$ , multiplicative order is the cleanest tool.

Large exponents should be reduced modulo the order.

Counting how often a power hits a given residue is a congruence-class counting problem.

Divisibility questions like $n\mid a^n-1$ are really power-congruence questions.

The PYQ family $n=3^k$ gives infinitely many odd integers with $n\mid 2023^n-1$ .

---

💡 Next Up

Proceeding to Last digit problems.

---

Part 4: Last digit problems

Last Digit Problems

Overview

Last digit problems are modular arithmetic questions modulo

10

. The key fact is that powers of a fixed integer usually develop a repeating cycle in their last digits. Exam-level questions often look large, but the actual task is small: reduce the base modulo

10

, find the cycle, and locate the required position in that cycle. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Find the last digit of large powers quickly.

Detect cyclic patterns of units digits.

Reduce large bases modulo $10$ before computing powers.

Handle expressions involving sums or products of large powers.

Avoid common mistakes in cycle indexing.

---

Core Idea

📖 Last digit as modulo

10

The last digit of an integer $N$ is exactly the remainder when $N$ is divided by $10$ .

So last digit questions are questions modulo $10$ .

\qquad a \equiv b \pmod{10}

, then

a

and

b

have the same last digit. ---

Standard Cycles

📐 Last Digit Cycles of Powers

The units digits of powers repeat in short cycles.

$2^n$ : $\qquad 2,4,8,6$

$3^n$ : $\qquad 3,9,7,1$

$4^n$ : $\qquad 4,6$

$5^n$ : $\qquad 5$

$6^n$ : $\qquad 6$

$7^n$ : $\qquad 7,9,3,1$

$8^n$ : $\qquad 8,4,2,6$

$9^n$ : $\qquad 9,1$

These are periodic from

n=1

onward.

❗ Cycle Lengths

length $1$ : bases ending in $0,1,5,6$

length $2$ : bases ending in $4,9$

length $4$ : bases ending in $2,3,7,8$

---

Standard Method

💡 How to Find a Last Digit

Reduce the base modulo $10$ .

Write the last-digit cycle of its powers.

Find the exponent modulo the cycle length.

Read off the correct term of the cycle.

---

Minimal Worked Examples

Example 1 Find the last digit of

\qquad 3^{17}

. The cycle for

3^n

\qquad 3,9,7,1

This has length

4

. Now

\qquad 17 \equiv 1 \pmod 4

3^{17}

has the same last digit as the first term of the cycle, which is

\boxed{3}

. --- Example 2 Find the last digit of

\qquad 12^{100}

. Since

\qquad 12 \equiv 2 \pmod{10}

, this is the same as the last digit of

2^{100}

. The cycle for

2^n

\qquad 2,4,8,6

and

\qquad 100\equiv 0 \pmod 4

So we take the fourth term, which is

\boxed{6}

. ---

Sums and Products

📐 Working with Combined Expressions

For sums and products:

find the last digit of each part separately

then combine modulo $10$

Example:

\qquad

last digit of

7^{20}+3^{11}

Compute:

$7^{20}$ : cycle length $4$ , and $20\equiv 0\pmod 4$ , so last digit is $1$

$3^{11}$ : cycle length $4$ , and $11\equiv 3\pmod 4$ , so last digit is $7$

So total last digit is

\qquad 1+7=8

---

Common Mistakes

⚠️ Avoid These Errors

❌ Using the exponent directly instead of reducing modulo cycle length

✅ Reduce the exponent modulo the cycle length first

❌ Forgetting that remainder $0$ means the last term of the cycle

✅ Example:

n\equiv 0\pmod 4

means use the 4th term, not the 1st

❌ Not reducing the base modulo $10$

✅ Replace

27

7

43

3

, etc.

❌ Confusing cycle position with exponent value

---

CMI Strategy

💡 Solve Smart

Throw away all digits except the last digit of the base.

Memorise the cycles for $2,3,7,8$ and the short cycles for $4,9$ .

Treat exponent remainder $0$ carefully.

For sums or products, compute component-wise modulo $10$ .

---

Practice Questions

:::question type="MCQ" question="The last digit of

7^{12}

is" options=["

1

","

3

","

7

","

9

"] answer="A" hint="Use the cycle for powers of

7

." solution="The last digits of powers of

7

are

\qquad 7,9,3,1

with period

4

. Since

\qquad 12\equiv 0 \pmod 4

, we take the 4th term of the cycle, which is

1

. Hence the correct option is

\boxed{A}

." ::: :::question type="NAT" question="Find the last digit of

2^{25}

." answer="2" hint="Use the cycle of powers of

2

." solution="The last digits of powers of

2

are

\qquad 2,4,8,6

with period

4

. Since

\qquad 25\equiv 1 \pmod 4

, the last digit is the 1st term of the cycle, which is

\boxed{2}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["The last digit of a number is its remainder modulo

10

","The powers of

5

always end in

5

","The powers of

9

have cycle length

4

","To find the last digit of

27^n

, it is enough to study

7^n

"] answer="A,B,D" hint="Use the standard last-digit cycles." solution="1. True.

True.

False. The powers of

9

have cycle length

2

9,1

True, because

27\equiv 7\pmod{10}

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Find the last digit of

3^{11}+2^{14}

." answer="

3

" hint="Compute each last digit separately." solution="For

3^{11}

, the cycle is

\qquad 3,9,7,1

with period

4

. Since

\qquad 11\equiv 3\pmod 4

, the last digit of

3^{11}

7

. For

2^{14}

, the cycle is

\qquad 2,4,8,6

with period

4

. Since

\qquad 14\equiv 2\pmod 4

, the last digit of

2^{14}

4

. So the last digit of

\qquad 3^{11}+2^{14}

is the last digit of

\qquad 7+4=11

, which is

\boxed{1}

." ::: ---

Summary

❗ Key Takeaways for CMI

Last digit problems are modular arithmetic modulo $10$ .

Power last digits repeat in short cycles.

Reduce the base modulo $10$ first.

Reduce the exponent modulo the cycle length.

Combined expressions are handled term by term modulo $10$ .

---

Chapter Summary

❗ Cyclic behaviour — Key Points

Residue Classes: The integers $\mathbb{Z}$ are partitioned into $n$ distinct residue classes modulo $n$ , denoted $\mathbb{Z}_n = \{[0], [1], \dots, [n-1]\}$ , where $[a] = \{x \in \mathbb{Z} \mid x \equiv a \pmod{n}\}$ .

Modular Arithmetic: Operations of addition, subtraction, and multiplication are well-defined on residue classes. Division is possible if the divisor is coprime to the modulus.

Periodicity of Powers: For any integer $a$ and modulus $n$ , the sequence of powers $a^1, a^2, a^3, \dots \pmod{n}$ eventually becomes periodic.

Order of an Element: If $\operatorname{gcd}(a, n) = 1$ , the order of $a$ modulo $n$ , denoted $\operatorname{ord}_n(a)$ , is the smallest positive integer $k$ such that $a^k \equiv 1 \pmod{n}$ . This order $k$ always divides $\phi(n)$ .

Euler's Totient Theorem: For integers $a$ and $n$ with $\operatorname{gcd}(a, n) = 1$ , $a^{\phi(n)} \equiv 1 \pmod{n}$ , where $\phi(n)$ is Euler's totient function, counting positive integers up to $n$ that are coprime to $n$ .

Fermat's Little Theorem: A special case of Euler's Theorem: if $p$ is a prime number, then for any integer $a$ not divisible by $p$ , $a^{p-1} \equiv 1 \pmod{p}$ .

Applications: These principles are fundamental for simplifying large exponents in modular arithmetic, solving certain types of congruences, and determining the last digits of numbers.

---

Chapter Review Questions

:::question type="MCQ" question="What is the last digit of $3^{2024}$ ?" options=["1","3","7","9"] answer="1" hint="Consider the powers of 3 modulo 10 and identify the cycle length." solution="We need to find $3^{2024} \pmod{10}$ .
The powers of 3 modulo 10 follow a cycle:
$3^1 \equiv 3 \pmod{10}$
$3^2 \equiv 9 \pmod{10}$
$3^3 \equiv 27 \equiv 7 \pmod{10}$
$3^4 \equiv 81 \equiv 1 \pmod{10}$
$3^5 \equiv 3 \pmod{10}$
The cycle length is 4.
To find $3^{2024} \pmod{10}$ , we need to find $2024 \pmod{4}$ .
$2024 \div 4 = 506$ with a remainder of 0.
Since the remainder is 0, we use the last element in the cycle (which corresponds to an exponent of 4).
So, $3^{2024} \equiv 3^4 \equiv 1 \pmod{10}$ .
The last digit is 1."
:::

:::question type="NAT" question="Find the smallest positive integer $x$ such that $5x \equiv 7 \pmod{11}$ ." answer="8" hint="To isolate $x$ , you need to find the multiplicative inverse of 5 modulo 11." solution="We need to solve $5x \equiv 7 \pmod{11}$ .
First, find the multiplicative inverse of $5 \pmod{11}$ . We are looking for an integer $y$ such that $5y \equiv 1 \pmod{11}$ .
By inspection or Extended Euclidean Algorithm:
$5 \times 1 = 5$
$5 \times 2 = 10 \equiv -1 \pmod{11}$
$5 \times (-2) \equiv 1 \pmod{11}$
Since $-2 \equiv 9 \pmod{11}$ , the inverse of 5 modulo 11 is 9.
Multiply both sides of the congruence by 9:
$9 \times (5x) \equiv 9 \times 7 \pmod{11}$
$45x \equiv 63 \pmod{11}$
Since $45 \equiv 1 \pmod{11}$ (as $45 = 4 \times 11 + 1$ ) and $63 \equiv 8 \pmod{11}$ (as $63 = 5 \times 11 + 8$ ):
$1x \equiv 8 \pmod{11}$
$x \equiv 8 \pmod{11}$ .
The smallest positive integer $x$ is 8."
:::

:::question type="MCQ" question="Which of the following is the order of $5$ modulo $13$ ?" options=["3","4","6","12"] answer="4" hint="The order must divide $\phi(13)$ . Test powers of 5 modulo 13." solution="We need to find $\operatorname{ord}_{13}(5)$ .
Since 13 is a prime number, $\phi(13) = 13-1 = 12$ . The order must divide 12. The possible orders are 1, 2, 3, 4, 6, 12.
Let's compute powers of 5 modulo 13:
$5^1 \equiv 5 \pmod{13}$
$5^2 \equiv 25 \equiv 12 \pmod{13}$
$5^3 \equiv 5 \times 12 \equiv 60 \equiv 8 \pmod{13}$
$5^4 \equiv 5 \times 8 \equiv 40 \equiv 1 \pmod{13}$
The smallest positive integer $k$ for which $5^k \equiv 1 \pmod{13}$ is 4.
Therefore, the order of $5$ modulo $13$ is 4."
:::

:::question type="NAT" question="Find the remainder when $2^{200}$ is divided by $17$ ." answer="1" hint="Apply Fermat's Little Theorem or Euler's Totient Theorem." solution="We need to find $2^{200} \pmod{17}$ .
Since 17 is a prime number and $\operatorname{gcd}(2, 17) = 1$ , we can use Fermat's Little Theorem.
Fermat's Little Theorem states that $a^{p-1} \equiv 1 \pmod{p}$ for prime $p$ and integer $a$ not divisible by $p$ .
Here, $a=2$ and $p=17$ , so $2^{17-1} \equiv 2^{16} \equiv 1 \pmod{17}$ .
Now we need to simplify the exponent 200 using the cycle length 16:
$200 \div 16 = 12$ with a remainder of $8$ .
So, $200 = 16 \times 12 + 8$ .
Then, $2^{200} = 2^{16 \times 12 + 8} = (2^{16})^{12} \cdot 2^8 \pmod{17}$ .
Since $2^{16} \equiv 1 \pmod{17}$ :
$2^{200} \equiv (1)^{12} \cdot 2^8 \pmod{17}$
$2^{200} \equiv 1 \cdot 2^8 \pmod{17}$
Now, calculate $2^8 \pmod{17}$ :
$2^1 = 2$
$2^2 = 4$
$2^3 = 8$
$2^4 = 16 \equiv -1 \pmod{17}$
$2^8 = (2^4)^2 \equiv (-1)^2 \equiv 1 \pmod{17}$ .
Therefore, the remainder when $2^{200}$ is divided by $17$ is 1."
:::

---

What's Next?

💡 Continue Your CMI Journey

Having mastered cyclic behaviour, you are well-prepared for deeper topics in Number Theory. The principles of modular arithmetic and periodicity are foundational for understanding Diophantine Equations (particularly linear congruences and their solutions), exploring Primitive Roots (elements whose order is $\phi(n)$ ), and delving into Quadratic Residues and the Law of Quadratic Reciprocity. These concepts are also indispensable for advanced studies in Cryptography, where cyclic groups and modular exponentiation form the bedrock of public-key systems like RSA.

Cyclic behaviour

Cyclic behaviour

Chapter Contents

| Topic |

Part 1: Residue class reasoning

Residue Class Reasoning

Overview

Learning Objectives

Core Idea

Standard Residue Sets

Choosing a Modulus

Minimal Worked Examples

Impossibility by Residues

Common Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 2: Periodicity

Periodicity

Overview

Learning Objectives

Core Idea

Why Modulo Sequences Repeat

Powers Modulo mmm

Last-Digit Cycles

Linear Periodicity Modulo mmm

Geometric Wrap-Around as Modulo 111

When Does the Trajectory Repeat?

Rational vs Irrational Slope

Finite Trajectories in the Wrap Problem

Integer Lengths of Finite Trajectories

Minimal Worked Examples

Common Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 3: Powers modulo n

Powers modulo nnn

Overview

Learning Objectives

Core Congruence Language

Why Cycles Appear

Multiplicative Order

Standard Example: Powers of 222 modulo 777

Counting Exponents in a Cycle

Euler and Fermat as Period Bounds

When gcd⁡(a,n)≠1\gcd(a,n)\ne 1gcd(a,n)=1

Divisibility of the Form n∣an−1n \mid a^n-1n∣an−1

Infinite Family from the PYQ

Minimal Worked Examples

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 4: Last digit problems

Last Digit Problems

Overview

Learning Objectives

Core Idea

Standard Cycles

Standard Method

Minimal Worked Examples

Sums and Products

Common Mistakes

CMI Strategy

Practice Questions

Summary

Chapter Summary

Chapter Review Questions

What's Next?

🎯 Key Points to Remember

Related Topics in Number Theory

Parity and structure

Congruences

GCD and LCM

Divisor-based problems

More Resources

Study Notes

Powers Modulo $m$

Linear Periodicity Modulo $m$

Geometric Wrap-Around as Modulo $1$

Powers modulo $n$

Standard Example: Powers of $2$ modulo $7$

When $\gcd(a,n)\ne 1$

Divisibility of the Form $n \mid a^n-1$