HCF & LCM — Applications and Remainder Recipes

Use the HCF when the question asks for the largest quantity that divides several given quantities exactly:

• the largest square tile that paves a floor with no cutting;
• the greatest length that measures several lengths exactly;
• the greatest speed making each journey take a whole number of hours.

Convert to a common unit first — centimetres, paise, tenths of a kilometre — so the HCF is taken over integers. For a tiling count, divide each side by the HCF and multiply.

Use the LCM when the question asks for the first time several repeating events coincide:

• bells ringing at different intervals, next ringing together;
• runners with different lap times, next meeting at the start;
• the least amount that is a whole number of two different units.

Then convert the LCM into the requested units, and if the question asks how many times within a window, divide the window by the LCM and take the floor.

Let $L$ be the LCM of the given divisors.

• Largest $k$-digit multiple: $L\times\left\lfloor \frac{\text{largest }k\text{-digit}}{L}\right\rfloor$.
• Smallest $k$-digit multiple: $L\times\left\lceil \frac{\text{smallest }k\text{-digit}}{L}\right\rceil$.
• Count of multiples up to $N$: $\left\lfloor N/L \right\rfloor$.

For a least perfect square divisible by the given numbers, take the LCM and then raise each prime exponent to the next even number.

If $N$ leaves the same remainder on dividing $a$, $b$, $c$, then $N$ divides each of $b-a$, $c-b$ and $c-a$. The greatest such $N$ is

• The two independent differences suffice; the third is their sum and adds nothing.
• If instead the remainder is stated — "leaves remainder 5 in each case" — subtract it from every number first and take the HCF of the results.

If $N \equiv r$ modulo each of $d_1,\ldots,d_k$ (with $r$ less than every $d_i$), then

• For the smallest such $N$ with a digit condition, find the least $k$ making $N$ large enough.
• For the largest $k$-digit such $N$, take $\lfloor(\text{max} - r)/L\rfloor$ then multiply back and add $r$.
• For divisors that are successive powers of one prime, the LCM is just the highest power.

If $N$ leaves remainder $d_i - d$ on dividing by $d_i$, for every $i$ and a fixed $d$, then $N+d$ is divisible by every $d_i$, so

• The classic signature is remainders one less than the divisors: remainders $1,2,3,4,5$ for divisors $2,3,4,5,6$ means $d=1$.
• Always compute divisor minus remainder for each pair and check the value is the same before using this. If the shortfalls differ, no single recipe applies.

Procedure:

• Apply the appropriate recipe to get the family $N = Lk + r$.
• Substitute into the extra condition. If $N$ must be divisible by $m$, reduce $L$ and $r$ modulo $m$ and solve $Lk + r \equiv 0 \pmod m$ for $k$.
• Take the least non-negative $k$ that works, then compute $N$.

For two different remainders with no common pattern, listing one family and testing it against the other condition is faster than any formula.