Euclidean division
The theorem a = bq + r with 0 ≤ r < b, for a positive or negative dividend, divisibility, and the gap between the mathematical remainder and the % operator of programming languages.
- 26 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
A few cards from the deck
Euclidean division of a by b: what is it?
Show the answer
For an integer a and a positive integer b, the unique pair of integers (q, r) such that a = b × q + r with 0 ≤ r < b.
The pair exists and is unique thanks to the condition 0 ≤ r < b. Without it, 17 = 5 × 2 + 7 = 5 × 3 + 2 would give several pairs.
What does this program print?
```python
print(-17 // 5, -17 % 5)`-4 3-3 -2-3 2-4 -3
Show the answer
-4 3Python rounds down: -17 // 5 is -4, and -17 % 5 is 3 since 5 × (-4) + 3 = -17. The remainder stays in [0, 5[.
In a = b × q + r, a is called the …, b the …, q the … and r the ….
Show the answer
In a = b × q + r, a is called the dividend, b the divisor, q the quotient and r the remainder.
The remainder satisfies 0 ≤ r < b: it is strictly smaller than the divisor and never negative, even when the dividend is.
b | a (b divides a): what is it?
Show the answer
There is an integer k such that a = b × k; in other words, the remainder of the Euclidean division of a by b is zero.
5 | 0 is true (0 = 5 × 0), whereas 0 | 5 is false. A multiple of b is therefore an integer of the form b × k, and 0 is a multiple of every integer.