Practice question · Put in order
Order the steps of the proof that if a divides b and a divides c, then a divides b + c.
- Write b = a m and c = a n for some integers m and n
- Note that m + n is an integer
- Add them: b + c = a m + a n = a(m + n)
- Conclude that a divides b + c
- Assume a divides b and a divides c
Hints
- A direct proof unpacks the definition into algebra, computes, then repacks it.
- The definition of 'divides' must be re-applied at the very end, and that needs the factor to be an integer.
Show the answer
- Assume a divides b and a divides c
- Write b = a m and c = a n for some integers m and n
- Add them: b + c = a m + a n = a(m + n)
- Note that m + n is an integer
- Conclude that a divides b + c
Why
The pattern is: assume, unpack the definition, compute, check the result still fits the definition, conclude. The fourth step is not decoration, a(m + n) only witnesses divisibility because m + n is itself an integer.
Practise Divisibility and the Division Algorithm
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Divisibility and the Division Algorithm
- Select every integer below that divides 84.
- Since 47 = 6 x 6 + 11 is a true equation, it gives the quotient and remainder of 47 divided by 6.
- The division algorithm insists the remainder satisfies 0 ≤ r < a. Both 17 = 5·3 + 2 and 17 = 5·2 + 7 are…
- A hash function reduces a key modulo the table size. Why do implementations favour a prime table size?