SK Tuitions

Does the written addition algorithm cover every case?

Step 1 — Choose a test that exposes a missing case. Take 2468 + 1532. Align thousands with thousands, hundreds with hundreds, and so on.

Step 2 — Follow the printed units rule.

The chapter tells us what to do when the sum is less than 10 or more than 10. It gives no instruction for a sum equal to 10. Therefore, if we follow only the written instructions, we cannot continue this example. We must not silently invent the missing branch.

Step 3 — Correct the rule. In both the units step and the later-column step, replace “more than 10” with “10 or more”. Then write the units digit and carry 1.

Adding numbers with unequal lengths

Step 1 — Try 12,345 + 678. Right alignment leaves the thousands and ten-thousands positions of the shorter number blank.

Step 2 — Identify the missing instruction. The printed algorithm says to add the two digits in each column, but does not explicitly say how to handle a blank. Ordinary arithmetic treats the blank as 0; a fully precise algorithm must state that rule.

Why align from the right?

Step 1 — Recall the meaning of position. The rightmost digit counts ones, the next tens, the next hundreds, and so on. Addition must combine like units.

Step 2 — Match the place values. Write 56 below 234 with 6 under 4 and 5 under 3. Then ones combine with ones and tens with tens.

If 56 is wrongly aligned on the left and the blank on its right is treated as 0, it effectively becomes 560. That would give 234 + 560 = 794, which answers a different question.

Why can the carry not exceed 1?

Step 1 — Bound the units-column sum. Each digit is at most 9, so the first sum is at most 18. Its carry is therefore either 0 or 1.

Step 2 — Include an incoming carry. In any later column, there are two digits, each at most 9, and an incoming carry at most 1.

Thus the carry into the next column again cannot exceed 1. Starting at the first column and applying this reasoning repeatedly proves the claim for every column.

Why must we write the final carry?

When it still works: If there is no carry after the leftmost column, omitting Step 5 changes nothing.

When it fails: Choose 6789 + 5678. This example avoids the separate missing-sum-10 issue, so it isolates the importance of Step 5.

After processing the four columns, the written digits are 2467 and the carry is 1. That 1 represents one ten-thousand.

A complete, corrected addition algorithm

ADD(a, b)
Input: two non-negative whole numbers.
1. Align digits by place value.
2. Treat each missing digit as 0.
3. Set carry ← 0.
4. Process every column, from right to left:
   a. s ← digit of a + digit of b + carry
   b. Write s mod 10 in this answer column.
   c. carry ← whole-number quotient of s ÷ 10
5. If carry is 1, write it to the left.
6. Report the completed answer.

The remainder s mod 10 is the digit to write; the quotient is the number of tens transferred left. This single rule handles sums below 10, exactly 10, and above 10 without a gap.

Finding elements present in only one list

Plan: Scan the source list. For each value, test whether it appears in the other list. Keep it only if it does not. This is a list-difference operation; the order of the two lists matters.

(i) List 1 minus List 2

DIFFERENCE(List1, List2)
1. Start with an empty answer list.
2. For each value x in List1, in order:
   If x is not present in List2:
      Append x to answer.
3. Return answer.

(ii) List 2 minus List 1

1. Start with an empty answer list.
2. For each value y in List2, in order:
   If y is not present in List1:
      Append y to answer.
3. Return answer.

Worked trace: Take List 1 = [1, 2, 3, 6] and List 2 = [1, 3, 4, 6, 12].

Why correct? Every source-list entry is examined, and an entry is kept exactly when it is absent from the other list. Since retained entries stay in their original order, the answer is also increasing. Both loops end because the input lists are finite.

Optional improvement: use the sorted order

Keep one position in each list. If the values match, move both positions. If the List 1 value is smaller, keep it for part (i) and move only its position. If the List 2 value is smaller, move only its position. Once List 2 is exhausted, keep all remaining List 1 values. For part (ii), swap the lists. Each position moves only forwards.

An algorithm for the least common multiple

Start from the definition. A common multiple must be a multiple of m and of n. Examine positive multiples of the larger input in increasing order. The first that is also divisible by the smaller input is the least common multiple.

LCM(m, n)
Input: positive integers m and n.
1. a ← max(m, n)
2. b ← min(m, n)
3. candidate ← a
4. While candidate mod b is not 0:
   candidate ← candidate + a
5. Return candidate.

Worked example: lcm(12, 18). Here a = 18 and b = 12.

Why correct? Every candidate is a multiple of a. The stopping test confirms it is also a multiple of b. We test candidates in increasing order, so none of the earlier multiples of a is common.

Why does it stop? The product ab is a common multiple: it occurs among a, 2a, 3a, …, ba. Therefore a successful candidate appears after at most b tests.

Faster alternative once gcd is available

To justify the formula, compare prime powers: gcd takes the smaller exponent of each prime and lcm takes the larger. Their exponents add to those in the product mn.

Finding divisors in pairs

(i) Use the smaller member of each pair. If a × b = n and both a and b were greater than √n, their product would exceed n. Therefore at least one factor in every pair is at most √n.

The symbol ⌊√n⌋ means the greatest whole number not exceeding √n. For every successful j, the paired divisor is n ÷ j.

Since 4² ≤ 18 < 5², only 4 candidate numbers are tested instead of all 18. At j = 4 no divisor is found; this test is still part of the scan.

Perfect-square case: For n = 36, the pair at j = 6 is (6, 6). Add 6 only once to avoid duplicating a divisor.

(ii) The rightmost-element rule may fail. Appending both factors of each pair immediately gives divisors(18) as [1, 18, 2, 9, 3, 6]. This is not in increasing order.

For gcd(18, 36), every value in that first list appears in the second divisor list. The common-divisor list therefore ends with 6 even though the gcd is 18. Selecting its rightmost item would be wrong.

A paired-divisor algorithm that preserves increasing order

PAIRED_DIVISORS(n)
Input: a positive integer n.
1. small ← [ ]; large ← [ ]
2. For j from 1 through floor(√n):
   If n mod j = 0:
      Append j to small.
      paired ← n ÷ j
      If paired is not equal to j:
         Append paired to large.
3. Reverse large.
4. Return small followed by large.

For 18, small = [1, 2, 3] and large is initially [18, 9, 6]. Reversing large gives [6, 9, 18]. Joining the lists gives [1, 2, 3, 6, 9, 18], so the original rightmost-common-divisor rule is safe again.

Reverse the order of divisor scanning

Step 1 — Understand the new list order. Divisors now appear in decreasing order. For example:

Step 2 — Scan the first list for common entries. The values 12 and 4 are not divisors of 18; 6, 3, 2 and 1 are. Thus the common list is [6, 3, 2, 1].

Step 3 — Change the final selection. The greatest common divisor is now the leftmost common entry, not the rightmost.

GCD_BY_DESCENDING_LISTS(m, n)
1. Obtain the divisors of m in decreasing order.
2. Obtain the divisors of n in decreasing order.
3. Start common ← [ ].
4. Scan the first list in its stored order:
   If the current value is in the second list:
      Append it to common.
5. Return the leftmost element of common.

Scan common-divisor candidates backwards

Important distinction: Reversing the loop without changing its stopping rule is not enough. If we continue replacing the stored answer at every common divisor, the last stored answer will be 1.

Correct improvement: Scan downwards and stop at the first common divisor. Every larger candidate has already failed.

GCD_DESCENDING(m, n)
Input: positive integers m and n.
1. For j from min(m, n) down to 1:
   If m mod j = 0 and n mod j = 0:
      Return j and STOP.

Trace for gcd(12, 18).

Correctness: No common divisor is larger than the smaller input. We test every possible larger candidate before reaching the answer, so the first success is the greatest.

Termination: The scan is finite and 1 always divides both positive inputs. The method may stop early, but if the inputs are coprime, it still scans all the way to 1.

Four gcd calculations with full working

Use the improved, remainder-based algorithm. Divide the larger number by the smaller, then replace the pair by (divisor, remainder). Repeat until the remainder is 0. The last non-zero divisor/remainder is the gcd.

GCD_REMAINDER(m, n)
Input: non-negative integers, not both 0.
1. If m < n, swap m and n.
2. While n is not 0:
   r ← m mod n
   m ← n
   n ← r
3. Return m.

(i) gcd(375, 825)

Start with the larger number as the dividend. In each next row, the old divisor becomes the dividend and the old remainder becomes the divisor.

The last non-zero remainder is 75. Equivalently, the final division has divisor 75 and remainder 0. Stop here; do not divide by 0.

(ii) gcd(51,000, 81,000)

Start with the larger number as the dividend. In each next row, the old divisor becomes the dividend and the old remainder becomes the divisor.

The last non-zero remainder is 3,000. Equivalently, the final division has divisor 3,000 and remainder 0. Stop here; do not divide by 0.

Check: 51,000 = 3000 × 17 and 81,000 = 3000 × 27. Since 17 and 27 have no common factor greater than 1, the gcd is 3000. Note that this question uses 51,000, not the 54,000 from an earlier worked example in the chapter.

(iii) gcd(1,789,287, 237,656)

Start with the larger number as the dividend. In each next row, the old divisor becomes the dividend and the old remainder becomes the divisor.

The last non-zero remainder is 1. Equivalently, the final division has divisor 1 and remainder 0. Stop here; do not divide by 0.

Interpretation: The numbers are coprime because their gcd is 1. This does not mean that both individual numbers are prime.

(iv) gcd(2,587,392, 157,656)

Start with the larger number as the dividend. In each next row, the old divisor becomes the dividend and the old remainder becomes the divisor.

The last non-zero remainder is 24. Equivalently, the final division has divisor 24 and remainder 0. Stop here; do not divide by 0.

These divisions confirm that 24 divides both inputs; the remainder chain establishes that it is the greatest common divisor.

Why replacing a number by the remainder preserves gcd

Set up the division equation. We need n > 0 so that m mod n is defined. Let d be a positive integer and let r be the remainder.

Direction 1: common divisor of m and n ⇒ common divisor of n and r

Suppose d divides m and n. Then there are whole numbers a and b such that:

Thus r is an integer multiple of d, so d divides r. We already know d divides n. Therefore d is a common divisor of n and r.

Direction 2: common divisor of n and r ⇒ common divisor of m and n

Suppose d divides n and r. Write:

Therefore d divides m as well as n. This proves the reverse direction. The multiplier c can be 0 when the remainder is 0.

Example: 60 = 3 × 16 + 12. Common divisors of 60 and 16 are [1, 2, 4]; common divisors of 16 and 12 are also [1, 2, 4]. Both gcds equal 4.

Source clarification: On printed page 48, one sentence says “m and m mod n”. The correct preserved pair is n and m mod n, as in the exercise and the algorithm. For example, gcd(60, 12) = 12, whereas gcd(60, 16) = 4; so keeping m instead of n is not generally valid.

Write prime(n): is a number prime?

Plan: First exclude integers less than 2. For a positive integer n ≥ 2, form the complete divisor list and count its entries.

PRIME(n)
Input: an integer n.
1. If n < 2:
   Return FALSE and STOP.
2. D ← DIVISORS(n)
3. If the number of entries in D is 2:
   Return TRUE.
4. Otherwise:
   Return FALSE.

DIVISORS(n)
Input: a positive integer n.
1. D ← [ ]
2. For j from 1 through n:
   If n mod j = 0:
      Append j to D.
3. Return D.

Why correct? The divisor algorithm checks every possible positive divisor. For n ≥ 2, both 1 and n occur. Exactly two entries therefore means there are no other positive divisors, which is precisely the definition of prime.

Why it stops: The divisor loop checks a finite sequence of n candidates. The output TRUE means “prime”; FALSE means “not prime”.

Optional faster version

PRIME_FAST(n)
1. If n < 2, return FALSE.
2. For j from 2 through floor(√n):
   If n mod j = 0:
      Return FALSE and STOP.
3. Return TRUE.

If n were composite, a factor pair would have at least one member between 2 and √n. Hence finding no divisor in that range proves primality. For n = 2 or 3, the loop is empty and TRUE is correctly returned.

Write primedivisors(n)

Plan: Use two tools already built: DIVISORS(n) supplies candidates and PRIME(d) filters them. A filter keeps entries that satisfy a condition and rejects the others.

PRIMEDIVISORS(n)
Input: a positive integer n.
1. D ← DIVISORS(n)
2. P ← [ ]
3. For each d in D:
   If PRIME(d) is TRUE:
      Append d to P.
4. Return P.

Trace for n = 60.

Why correct? Every returned entry divides n and passes the prime test. Conversely, every prime divisor of n appears in D and will be kept. Nothing is missed and no composite number is included.

Special cases: primedivisors(1) = [ ]; primedivisors(13) = [13]; primedivisors(16) = [2]. The prime divisor 2 is listed only once for 16.

Prime factorisation and comparison

Plan: Start with the smallest possible prime divisor, 2. Divide it out repeatedly, counting how many times it occurs. Then try the next candidate. Continue until the remaining number becomes 1.

PRIME_FACTORIZATION(n)
Input: a positive integer n.
1. remaining ← n
2. p ← 2
3. factors ← [ ]
4. While remaining > 1:
   exponent ← 0
   While remaining mod p = 0:
      remaining ← remaining ÷ p
      exponent ← exponent + 1
   If exponent > 0:
      Append the pair (p, exponent) to factors.
   p ← p + 1
5. Return factors.

All divisions performed inside the inner loop are exact. Although p tries composite candidates too, a composite candidate cannot divide the remaining number after all smaller prime factors have already been removed. Therefore every stored p is prime.

Full trace for 180

Why correct? At every step, the original number equals the product of all factors removed so far multiplied by the remaining number. A successful division transfers one factor from the remaining number to the stored factorisation, preserving that product. When the remaining number is 1, all factors have been recorded.

Why does it stop? A successful division makes the remaining positive integer smaller. If candidates fail, p increases until it reaches a divisor, at latest the remaining number itself. The process therefore reaches 1. For input 1, return [ ]: 1 has no prime factors; its empty product is 1.

(i) Representing the result

Store each distinct prime together with its exponent:

The pair (3, 2) means “the prime 3 occurs twice”, not “multiply 3 by 2”. A repeated-factor list [2, 2, 3, 3, 5] is also valid, but prime–exponent pairs make comparison simpler.

(ii) Comparing two factorisations

Match the same prime bases. For the gcd, keep each common prime with the smaller exponent. A missing prime has exponent 0. For example, compare 180 and 252:

GCD_FROM_FACTORS(m, n)
1. F ← PRIME_FACTORIZATION(m)
2. G ← PRIME_FACTORIZATION(n)
3. answer ← 1
4. For each prime p appearing in F:
   a ← exponent of p in F
   b ← exponent of p in G, or 0 if absent
   e ← min(a, b)
   Multiply answer by p exactly e times.
5. Return answer.

Why the minimum? A common divisor cannot contain more copies of a prime than either number contains. Taking every prime to its largest allowed common exponent makes the greatest possible common divisor.

If the task is to check whether the two original numbers are equal, their sorted prime–exponent lists must match exactly. If the task is lcm, use the maximum exponent over all primes appearing in either list.

Why digit-by-digit addition gives the correct sum

Step 1 — Break each number into place values. For example:

Step 2 — Add equal-sized units. Ones combine with ones; tens combine with tens; hundreds combine with hundreds.

General reasoning: At a place worth 10ᵏ, let the column sum be s. Write s = 10c + u, where u is its units digit and c is its carry.

Writing u in the current column and carrying c to the next column preserves the total value exactly. This is done at every place, so the completed result equals the original sum.

Modify addition for decimal fractions

The key change is alignment. Match decimal points so that tenths line up with tenths, hundredths with hundredths, and ones with ones. Add trailing zeros when necessary; this does not change a decimal’s value.

ADD_DECIMALS(a, b)
1. Align the decimal points.
2. Add trailing zeros so both fractional parts
   have the same number of digits.
3. Treat missing whole-number places as 0.
4. Set carry ← 0.
5. Add from the rightmost digit to the left,
   using the corrected whole-number rules.
6. Put the decimal point in the answer directly
   below the aligned decimal points.
7. Write any final carry to the left.

Example: 12.75 + 3.8. First write 3.8 as 3.80.

Execute the divisor algorithm

Use the chapter’s basic algorithm: start with [ ], test every j from 1 through n, and append j only if n mod j = 0. The following tables display successful updates; all other tested candidates leave the list unchanged.

Divisors of 15

Divisors of 135

Divisors of 775

How does the work grow? The basic procedure performs one divisibility test for each j from 1 to n, so it performs n tests. The number of divisors found is not the number of tests performed.

Thus the original algorithm takes 15, 135 and 775 tests for these inputs. From 15 to 135, the input is multiplied by 9 and so is the test count. In general, if the input value is multiplied by 10, this algorithm performs 10 times as many divisibility tests.

Why subtraction works, and why remainders are faster

1. The subtraction rule

For m ≥ n, any common divisor d of m and n divides m − n. Conversely, if d divides n and m − n, it also divides their sum m. Thus the common-divisor sets are identical.

2. Why the process stops

After arranging m ≥ n > 0, replacing (m, n) by (n, m − n) reduces the sum of the two entries from m + n to m. A strictly decreasing positive-integer sum cannot decrease forever. Eventually one entry is 0.

Every positive integer divides 0, but a common divisor must also divide a. Hence the greatest common divisor is a, not 0.

3. A short subtraction trace

The pairs above are reordered when necessary so the larger number is shown first. Reordering does not change common divisors.

4. The same input with remainder division

A single remainder step performs the effect of several repeated subtractions.

5. Odd-number example

For an odd number 2k + 1 ≥ 3, dividing by 2 always leaves remainder 1.

Thus two remainder reductions are sufficient for every odd input at least 3. For the boundary case k = 0, the input is gcd(1, 2); after swapping, only one division 2 = 2 × 1 + 0 is needed.