Congruence modulo m

1. Jul 24, 2011

pc2-brazil

1. The problem statement, all variables and given/known data
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.

2. Relevant equations
An integer x is congruent to an integer a modulo m if and only if:
$$x \equiv a \pmod m$$

3. The attempt at a solution
From the definition:
$$x \mod m = a \mod m$$
or:
$$x - a = km$$
where k is an integer.
From the division "algorithm":
$$x = mq + a\mod m$$
where q is the quotient.
But I'm not sure on how to proceed from here. The textbook gives a strange answer: $x \mod m$ if $x \mod m \leq \left \lceil m/2 \right \rceil$ and $(x \mod m) - m$ if $x \mod m > \left \lceil m/2 \right \rceil$
I would say that the smallest absolute value of x is when the quotient (q above) is 0. Thus:
$$x=a\mod m$$
According to the answer, $x=a\mod m$ is only true if $x \mod m \leq \left \lceil m/2 \right \rceil$, but I can't figure out why.

2. Jul 24, 2011

HallsofIvy

Staff Emeritus
For example, If a= 5 and m= 7, then x= 5 (mod 7) if and only if x= 5+ 7k for integer k. k= 0 gives x= 5, of course, and k= -1 gives x= -2. The "smallest absolute value" is 2, not 5, because ⌈m/2⌉= 3 and 3< 5. If a= 3 then x= 3 (mod n7) if and only if x= 3+ 7k. k= 0 gives x= 3 while k= -1 gives 3- 7= -4. Now the "smallest absolute value" is 3.

In general x= a (mod m) (for [itex]0\le a< m) if and only if x= a+ mk for integer k. k= 0 gives x= a> 0 and k= -1 gives a- m< 0. Which of those has smaller absolute value depends on how close a is to m.