← 2020 Paper 2

UPSC 2020 Maths Optional Paper 2 Q2a — Step-by-Step Solution

15 marks · Section A

Cyclic groups · Algebra · asked 8× in 13 yrs · Read the full method →

Question

Let $G$ be a finite cyclic group of order $n$. Then prove that $G$ has $\phi(n)$ generators (where $\phi$ is Euler’s $\phi$-function).

Technique

Order formula $\operatorname{ord}(a^k)=n/\gcd(n,k)$; generator $\iff$ order $n$ $\iff$ $\gcd(k,n)=1$; count by definition of $\phi$.

Solution

Let $G=\langle a\rangle$ be cyclic of order $n$, so $G=\{e,a,a^2,\dots,a^{n-1}\}$ and $a$ has order $n$ (i.e. $a^n=e$ and no smaller positive power equals $e$).

Step 1 — Order of an arbitrary element $a^k$

Claim. For $0\le k\le n-1$, the order of $a^k$ is

Proof. $(a^k)^m=e\iff a^{km}=e\iff n\mid km$. Let $d=\gcd(n,k)$, $n=dn'$, $k=dk'$ with $\gcd(n',k')=1$. Then $n\mid km\iff dn'\mid dk'm\iff n'\mid k'm\iff n'\mid m$ (since $\gcd(n',k')=1$). The least positive such $m$ is $n'=n/d$. Hence $\operatorname{ord}(a^k)=n/\gcd(n,k)$. $\square$

Step 2 — Characterize the generators

$a^k$ generates $G$ iff $\langle a^k\rangle=G$ iff $\operatorname{ord}(a^k)=|G|=n$. By Step 1,

So $a^k$ is a generator iff $\gcd(k,n)=1$.

Step 3 — Count the generators

The generators correspond exactly to the exponents $k\in\{0,1,2,\dots,n-1\}$ (a complete residue system modulo $n$, equivalently $k\in\{1,\dots,n\}$) with $\gcd(k,n)=1$. By the definition of Euler’s totient function, the number of such $k$ is precisely $\phi(n)$:

Distinct admissible exponents give distinct elements $a^k$ (since $a^0,\dots,a^{n-1}$ are the distinct elements of $G$), so the count of generators equals the count of admissible exponents.

Answer