← 2021 Paper 2

UPSC 2021 Maths Optional Paper 2 Q1a — Step-by-Step Solution

10 marks · Section A

Groups: definition, axioms, examples · Algebra · asked 3× in 14 yrs · Read the full method →

Question

Let $m_1,\ldots,m_k$ be positive integers, $d>0$ = GCD. Show $\exists$ integers $x_1,\ldots,x_k$ with $d=x_1 m_1+\cdots+x_k m_k$.

Technique

Well-ordering: smallest positive integer linear combination is the GCD.

Solution

Strategy. Consider the set $S=\{a_1 m_1+\cdots+a_k m_k:a_i\in\mathbb Z\}\cap\mathbb Z^+$ of positive linear combinations. By well-ordering, $S$ has a minimum element $\delta$. Show $\delta=d$.

Step 1 — $S$ is non-empty

Take $a_1=1,a_2=\cdots=a_k=0$: gives $m_1>0$, so $m_1\in S$. Hence $S\ne\emptyset$.

Step 2 — Let $\delta=\min S$ by well-ordering

Then $\delta=x_1 m_1+\cdots+x_k m_k>0$ for some integers $x_i$.

Step 3 — $\delta\mid m_i$ for each $i$

By division algorithm: $m_i=q_i\delta+r_i$ with $0\le r_i<\delta$.

If $r_i>0$: $r_i=m_i-q_i\delta=m_i-q_i(x_1 m_1+\cdots+x_k m_k)$, which is also a linear combination of $m_1,\ldots,m_k$ with integer coefficients (subtract $q_i x_j$ from coefficient of $m_j$ for $j\ne i$, and adjust the $m_i$ coefficient). So $r_i\in S$ but $r_i<\delta$, contradicting minimality.

Hence $r_i=0$, so $\delta\mid m_i$ for all $i$.

Step 4 — $\delta$ is the GCD

Since $\delta$ divides each $m_i$, $\delta\le d$ (the GCD is the largest common divisor).

Conversely, any common divisor $d$ of $m_1,\ldots,m_k$ also divides every integer linear combination, in particular $\delta$. So $d\le\delta$.

Hence $\delta=d$.

Answer