Exercises — HCF (GCD) — prime factorization method, Euclidean algorithm

(a) TRUE. "$6\mid 42$" reads "$6$ divides $42$", meaning $42=6\times k$ with $k$ a whole number. Here $42=6\times 7$, remainder $0$. ✅ (b) FALSE. $42=4\times 10+2$, remainder $2\ne 0$, so $4$ does not divide $42$ ($4\nmid 42$). (c) FALSE. The convention is $\gcd (a,0)=a$, not $0$. Every number divides $0$ (since $0=a\times 0$), so the biggest divisor of $a$ still wins. Hence $\gcd (a,0)=a$. (d) FALSE. A common divisor must divide both numbers, so it cannot exceed the smaller one. Therefore $\gcd (a,b)\le \min (a,b)$ always.

Line the primes up and take the minimum exponent for each (missing prime = exponent $0$):

• prime $2$: $\min (3,1)=1$
• prime $3$: $\min (1,2)=1$
• prime $5$: $\min (1,0)=0$ → dropped
• prime $7$: $\min (0,1)=0$ → dropped

$\gcd (a,b)=2^1\cdot 3^1=6.$ (Check: $a=120$, $b=126$; $\gcd (120,126)=6$. ✅)

Careful edge case. The convention $\gcd (a,0)=a$ was stated for $a>0$. For $\gcd (0,0)$ there is no largest common divisor, because every positive integer divides $0$ — there is no biggest one to pick. By universal convention we therefore define $\gcd (0,0)=0$. (Reason: $0$ is the number that every integer divides, so $0$ is the natural "top" element under the divisibility order — it is the greatest common divisor in that ordering sense.)

Factor $180$: $180=18\times 10=(2\cdot 3^2)(2\cdot 5)=2^2\cdot 3^2\cdot 5$. Factor $168$: $168=8\times 21=2^3\cdot (3\cdot 7)=2^3\cdot 3\cdot 7$. Take min exponents:

• $2:\min (2,3)=2$
• $3:\min (2,1)=1$
• $5:\min (1,0)=0$, $7:\min (0,1)=0$ → both dropped

$\gcd (180,168)=2^2\cdot 3=12.$

Each step is "$a=bq+r$" — fit $q$ whole copies of the smaller $b$ into the bigger $a$, keep the leftover $r$, then slide $(a,b)\to (b,r)$. (Recall $q$ = quotient, $r$ = remainder; each slide is valid by Euclid's invariant $\gcd (a,b)=\gcd (b,r)$ from the formula box above.)

• Step 1: $1155=405\cdot 2+345$ → new pair $(405,345)$.
• Step 2: $405=345\cdot 1+60$ → new pair $(345,60)$.
• Step 3: $345=60\cdot 5+45$ → new pair $(60,45)$.
• Step 4: $60=45\cdot 1+15$ → new pair $(45,15)$.
• Step 5: $45=15\cdot 3+0$ → remainder is $0$, stop.

Remainder hit $0$ at Step 5; the last non-zero remainder is $15$, so $\gcd (1155,405)=15$.

$\gcd (0,17)=17$: order doesn't matter, and $\gcd (a,0)=a$ gives $17$. $\gcd (17,17)=17$: the biggest number dividing $17$ is $17$ itself, and it also divides the other $17$.

From L2.1, $\gcd (180,168)=12$. Rearrange the identity (justified in the formula box at the top of this page): $\mathrm{lcm}(a,b)=\frac{a\times b}{\gcd (a,b)}=\frac{180\times 168}{12}=\frac{30240}{12}=2520.$ Sanity check by max exponents (LCM — Least Common Multiple): $180=2^2\cdot 3^2\cdot 5$, $168=2^3\cdot 3\cdot 7$, so $\mathrm{lcm}=2^3\cdot 3^2\cdot 5\cdot 7=8\cdot 9\cdot 35=2520$. ✅

Let $d$ be any common divisor of $n+1$ and $n$. Then $d$ divides their difference: $d\mid ((n+1)-n)=1.$ The only positive integer dividing $1$ is $1$ itself, so the greatest common divisor is $1$. Meaning: any two consecutive integers are coprime — they share no prime brick at all. This is the "divisors survive subtraction" idea from Euclid's lemma, used in a single stroke.

The answer $2^6$ is correct — but only if you handle every prime, not just prime $2$. Line up primes:

• $a=2^{10}=2^{10}\cdot 3^0$
• $b=2^6\cdot 3^1$

Min exponents: $2:\min (10,6)=6$; $3:\min (0,1)=0$. $\gcd =2^6\cdot 3^0=2^6=64.$ So the value $2^6=64$ is right. The reasoning is only complete if the student also noticed that prime $3$ contributes $3^{\min (0,1)}=3^0=1$ and therefore drops out. A student who wrote "$\gcd =2^6$ because $\min (10,6)=6$" got the correct number but skipped the check on prime $3$; a student who kept the $3$ (writing $2^6\cdot 3$) would be wrong. Verdict: correct answer, and the min rule confirms it — provided the $3$ is explicitly dropped.

Target from L2.2: $\gcd =15$. Take the Euclid steps and back-substitute, replacing each remainder by the equation that produced it.

From the steps: $15=60-45\cdot 1$, and $45=345-60\cdot 5$, and $60=405-345\cdot 1$, and $345=1155-405\cdot 2$.

Start at $15$ and climb: $15=60-45.$ Replace $45=345-5\cdot 60$: $15=60-(345-5\cdot 60)=6\cdot 60-345.$ Replace $60=405-345$: $15=6(405-345)-345=6\cdot 405-7\cdot 345.$ Replace $345=1155-2\cdot 405$: $15=6\cdot 405-7(1155-2\cdot 405)=20\cdot 405-7\cdot 1155.$ So $x=20,y=-7$: check $405\cdot 20-1155\cdot 7=8100-8085=15$. ✅ (See Diophantine Equations — solutions exist exactly when the target is a multiple of the gcd.)

Divide top and bottom by their HCF (from L2.2, $\gcd =15$): $\frac{1155}{405}=\frac{1155÷15}{405÷15}=\frac{77}{27}.$ $77=7\cdot 11$ and $27=3^3$ share no prime, so $\gcd (77,27)=1$ — the fraction is now in lowest terms. This is precisely what Reducing Fractions to Lowest Terms does: strip the common HCF.

"Longest length that divides all three exactly" is $\gcd (60,84,120)$. As warned in the L3 trap above (the $\gcd \cdot \mathrm{lcm}$ identity does not extend to three numbers), we do not use any product shortcut — we compute the gcd pairwise, step by step:

• $\gcd (60,84)$: $60=2^2\cdot 3\cdot 5$, $84=2^2\cdot 3\cdot 7$ → min gives $2^2\cdot 3=12$.
• $\gcd (12,120)$: $12\mid 120$, so $\gcd =12$.

Piece length $=12$ cm. Count of pieces: $60/12+84/12+120/12=5+7+10=22$ pieces.

Key theorem: for Mersenne-type numbers, $\gcd (2^m-1,2^n-1)=2^{\gcd (m,n)}-1$. The exponents obey Euclid! So first run Euclid on the exponents $100$ and $60$ (same "$a=bq+r$" machine, with $q$ the quotient and $r$ the remainder):

• $100=60\cdot 1+40$
• $60=40\cdot 1+20$
• $40=20\cdot 2+0$ → $\gcd (100,60)=20$.

Therefore $\gcd (2^{100}-1,2^{60}-1)=2^{20}-1=1048575.$ Why the shortcut works (sketch): subtracting $2^n-1$-type numbers mirrors subtracting exponents, so common divisors track $\gcd$ of exponents — Euclid's "survive subtraction" idea lifted one level up. This is the flavour behind fast gcd in Modular Arithmetic & RSA.

Since $\gcd (a,b)=1$, Bézout gives integers $x,y$ with $ax+by=1.$ Multiply both sides by $c$: $acx+bcy=c.$ Now inspect the two terms on the left:

• $a\mid acx$ (obviously, $a$ is a factor).
• $a\mid bcy$ because we are given $a\mid bc$, so $a$ divides $bc$ times anything.

A number dividing both summands divides their sum, so $a\mid (acx+bcy)=c$. $■$ This is exactly why a prime dividing a product must divide one of the factors — the backbone of the Fundamental Theorem of Arithmetic.

Fewest tiles $\Rightarrow$ largest square side. A square of side $s$ tiles both directions exactly iff $s\mid c$ and $s\mid d$; the largest such $s$ is $s=\gcd (c,d)$. Number of tiles $=\frac{\text{area}}{s^2}=\frac{cd}{\gcd (c,d{)}^2}$. Notice this equals $\frac{c}{s}\cdot \frac{d}{s}$ = "tiles across" $\times$ "tiles down". For $c=1155,d=405$: $\gcd =15$ (from L2.2), so $\text{tiles}=\frac{1155\cdot 405}{15^2}=\frac{467775}{225}=2079.$ Check as a grid: $1155/15=77$ tiles across, $405/15=27$ tiles down, and $77\times 27=2079$. ✅