Question

Number Theory problem

Answer 1

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.

Answer 2

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?

Answer 3

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.

Answer 4

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

Answer 5

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?

Answer 6

Ahh. Thank you :) I understand now

Answer 7

yw