1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Congruence modulo m

  1. Jul 24, 2011 #1
    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:
    [tex]x \equiv a \pmod m[/tex]

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

    Thank you in advance.
  2. jcsd
  3. Jul 24, 2011 #2


    User Avatar
    Science Advisor

    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook