Number theory path · N02

Before this lesson: Divisibility of integers

Your goal: Represent an integer with a valid bounded remainder.

Start with the idea and one example. Take a break before the written task if you need it. The questions are original teaching exercises, not official past-paper questions.

Euclidean division and remainders: the key idea

For every integer a and positive integer d, there are unique integers q,r such that a=dq+r and 0≤r<d. This is Euclidean division. The remainder is always chosen nonnegative, including when a is negative. The quotient is q=⌊a/d⌋, so truncating a negative decimal towards zero can give the wrong quotient. The restriction on r both chooses a standard representative and makes it unique.

A worked example

Divide −17 by 5 in Euclidean form.

Since −20≤−17<−15, the quotient is −4 and the remainder is 3: −17=5(−4)+3, with 0≤3<5.

Your turn: change one thing

Find the quotient and remainder when 83 is divided by 7.

Try this on paper before opening the explanation.

Compare your reasoning

83=7·11+6. The quotient is 11 and remainder 6, which lies between 0 and 6.

Pause and check

A trap to avoid: Allowing a negative remainder under the chosen standard convention.

Practise and adjust the level

Foundation checks the language; Core applies the method; Stretch asks you to choose or justify an idea. These are levels within this lesson. A session selects six of the nine questions; unused questions allow the level to change. Advanced theory still needs written practice.

Interactive practice loads here. You can also use the complete question set below.

Write a complete argument

Prove uniqueness of the Euclidean remainder.

Planning hint

List the assumptions and the exact conclusion. Identify the definition or theorem in this lesson that connects them. Explain why its conditions hold before using it.

Read the full solution after your attempt

Suppose a=dq+r=dq′+r′ with 0≤r,r′<d. Then d(q−q′)=r′−r. The right side has absolute value less than d; the only multiple of positive d in that range is 0. Thus r=r′ and then q=q′.

My proof notebook

Write on paper, or keep a draft here. Compare your reasoning with the solution only after a real attempt. The checklist is your own review, not an automatic mark.

All nine practice questions

Prefer paper or have JavaScript switched off? The complete question set, hints and solutions are here. Interactive practice uses these same questions in an order chosen from your answers.

1. For divisor d>0, the Euclidean remainder satisfies what?

Foundation

  1. 0<r≤d
  2. −d<r≤0
  3. r can be arbitrary
  4. 0≤r<d
Hint

Use the defining range.

Answer and reasoning

0≤r<d. The remainder is one of 0,1,…,d−1.

2. In a=dq+r, which symbol is the quotient?

Foundation

  1. a
  2. d
  3. r
  4. q
Hint

Identify each part of the division identity.

Answer and reasoning

q. q counts the integer multiple of the divisor.

3. The Euclidean remainder of −17 divided by 5 is what?

Core

  1. −2
  2. 2
  3. −3
  4. 3
Hint

Use −17=−20+3.

Answer and reasoning

3. The required nonnegative remainder is 3.

4. The quotient when 83 is divided by 7 is what?

Core

  1. 12
  2. 10
  3. 6
  4. 11
Hint

Find the largest multiple at most 83.

Answer and reasoning

11. 7·11=77 and 83−77=6.

5. Why must two valid remainders be equal?

Stretch

  1. The quotients are prime
  2. Their difference is a multiple of d with absolute value below d
  3. They are both positive
  4. All differences vanish
Hint

Combine the two division identities.

Answer and reasoning

Their difference is a multiple of d with absolute value below d. Only the zero multiple of d lies strictly between −d and d.

6. For a negative a, which expression gives the Euclidean quotient?

Stretch

  1. ⌊a/d⌋
  2. Truncation towards zero in every case
  3. ⌈a/d⌉ always
  4. |a|/d
Hint

The quotient must leave a nonnegative remainder.

Answer and reasoning

⌊a/d⌋. The floor inequality q≤a/d<q+1 is equivalent to 0≤a−dq<d.

7. For division by 7, what is the largest allowed remainder?

Foundation

  1. 5
  2. 6
  3. 7
  4. 8
Hint

The remainder is smaller than the divisor.

Answer and reasoning

6. The range is 0 through 6.

8. Write −23=6q+r with 0≤r<6.

Core

  1. q=−3,r=−5
  2. q=−4,r=−1
  3. q=4,r=1
  4. q=−4,r=1
Hint

Choose the multiple −24 below −23.

Answer and reasoning

q=−4,r=1. −23=6(−4)+1.

9. Why is q=−3,r=−5 not Euclidean division of −23 by 6?

Stretch

  1. The equality fails
  2. The quotient is negative
  3. 6 is not prime
  4. The remainder is negative
Hint

The equality alone is not enough.

Answer and reasoning

The remainder is negative. Although −23=−18−5, the remainder condition 0≤r<6 fails.

Choose your next step

Continue to Greatest common divisor and Bézout. If this felt difficult, return to a prerequisite above. Every lesson stays open.

Open my revision list →

Original teaching material · IMOolympiad.com. Send a specific correction through our contact page. Learning progress is optional and stays in this browser.