HCF & LCM — Laws and Fractions

For $a$ and $b$ written as prime powers:

• $\mathrm{HCF}$ takes $\min$ of each exponent (only primes in both);
• $\mathrm{LCM}$ takes $\max$ of each exponent (primes in either).

Consequences used constantly:

• $\mathrm{HCF} \mid a$, $\mathrm{HCF}\mid b$, and $\mathrm{HCF} \mid \mathrm{LCM}$;
• $a \mid \mathrm{LCM}$ and $b \mid \mathrm{LCM}$;
• the Euclidean algorithm computes the HCF by repeatedly replacing $(a,b)$ with $(b,\ a \bmod b)$ until the remainder is 0.

For any two positive integers,

• This gives the fourth quantity whenever three are known.
• It fails for three or more numbers: $\mathrm{HCF}\times\mathrm{LCM} \ne abc$ in general.
• Paired with $\mathrm{LCM} = k\cdot\mathrm{HCF}$ and a sum or difference of the two, it reduces most CDS puzzles to one linear equation.

Put $x = Ha$ and $y = Hb$ with $\gcd(a,b)=1$. Then:

• $xy = H^{2}ab$;
• $\mathrm{LCM}(x,y) = Hab$, so $\dfrac{\mathrm{LCM}}{\mathrm{HCF}} = ab$;
• $x+y = H(a+b)$ and $x-y = H(a-b)$.

Having reduced to $ab = m$, list the coprime factor pairs of $m$ only, then apply any size condition the question adds.

If $d \mid x$ and $d \mid y$ then $d \mid (x\pm y)$. Hence:

• $\mathrm{HCF}(p,\,p+q) = \mathrm{HCF}(p,\,q)$ and $\mathrm{HCF}(p,\,p-q) = \mathrm{HCF}(p,\,q)$;
• $\mathrm{HCF}(n,\,n+k) = \mathrm{HCF}(n,\,k)$, so it always divides $k$;
• you may subtract any multiple of one argument from the other, which is how $\gcd(12n+2,\,8n+1)$ reduces in two lines.

Related structural law: if $a=bc$ with $\gcd(b,c)=1$ then $\mathrm{HCF}(c,\,bd)=\mathrm{HCF}(c,\,d)$ — the coprime part $b$ contributes nothing.

With all fractions in lowest terms:

For an integer $a>1$,

• Take out any common constant factor first: $3^{29}-9 = 9\!\left(3^{27}-1\right)$, so the identity applies to the bracket and the 9 multiplies back at the end.
• The same shape works for a common factor of the whole expression, not for a constant added inside the power.

Necessary conditions for a stated HCF $H$ and LCM $L$ of two numbers:

• $H \mid L$, and $L/H = ab$ must be a positive integer;
• $H$ must divide each number given;
• each given number must divide $L$;
• $H \le$ each number $\le L$.

If any fails, no such pair exists. When that happens the honest answer is that the data is inconsistent — though the paper may still expect the value the intended arithmetic produces, so compute it and note the conflict.