## Hunus 2 years ago Number Theory problem

1. Hunus

The division algorithm states 'For any positive integers a and b there exists a unique pair (q, r) of non-negative integers such that b = aq + r, r < a.' For the uniqueness, assume that b = aq′ + r′, where q′ and r′ are also nonnegative integers satisfying 0 ≤ r′ < a. Then aq+r = aq′+r′, implying a(q−q′) = r′−r, and so a|r′ −r. Hence |r′−r| ≥ a or |r′ −r| = 0. Because 0 ≤ r, r′ < a yields |r′ − r| < a, we are left with |r′ − r| = 0, implying r′ = r and, consequently, q′ = q.

2. Hunus

My question lies with the statement 'Hence |r′−r| ≥ a or |r′ −r| = 0' Why does |r′−r| ≥ a imply that |r′ −r| = 0? Is it because r must be less than a and r' - r being greater than a is invalid so it must be zero?

3. experimentX

a(q−q′) = r′−r consider both q's and r's to be integer, if \( q' \neq q \), you would get \( k = |q - q'| \ge 0 \)| but \( k a = |r-r'|\) means |r-r'| is some integer multiple of a .. so it follows.

4. Hunus

I don't quite understand how that implies that |r - r'| = 0

5. experimentX

since both r and r' are assumed to be positive integers which is less than 'a' .. their difference can't be greater than 'a' .. can they?

6. Hunus

Ahh. Thank you :) I understand now

7. experimentX

yw