Question

Find a formula for the integer with smallest absolute value that is congruent to an integer a modulo m, where m is a positive integer.

Short answer

a-m(a/m) if a-m(a/m) \( \le \)(m/2)

a-m(a/m) – m if a-m(a/m) > (m/2)

Step-by-step solution

DEFINITIONS

Division algorithm let a be an integer and d a positive integer. Then there are unique integers q and r with \(0 \le r < d\)such that a = dq+r

q is called the quotient and r is called the remainder

q = a div d

r = a mod d

a is congruent to b modulo m is m divides a-b

notation: \(a \equiv b(\bmod m)\)

Step 2:

Solution

By the previous exersice, we know that is we divided a by m, then the quotient is (a/m) and the remainder is a-m(a/m).

However, this then implies

a mod m = a-m(a/m)

since, the remainder is at least 0 and less than m (\(0 \le a - m(a/m) < m\)):

a mod m = (a-m(a/m))mod m

however, we have shown (in a previous exercise) that if a mod m = b mod m, then\(a \equiv b(\bmod m)\)

\(a \equiv (a - m(a/m))(\bmod m)\)

Thus a-m(a/m) is an integer that is congruent to integer a modulo m.

Step 3:

Moreover, the integers closest to 0 that are congruent to a modulo m are then: the nonnegative integer a-m(a/m) and the nonpositive integer a-m(a/m))-m.

The nonnegative integer is the smallest absolute value when it is at most (m/2), while the nonpositive integer is the smallest absolute value when it exceeds (m/2).

The integer with thw smallest absolute value congruent to a modulo m is then: a-m(a/m) if a-m(a/m) \( \le \)(m/2) or a-m(a/m)-m if a-m(a/m)>(m/2).