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: Discrete Math Question Involving Congruence Modulus

  1. Apr 25, 2013 #1
    Solve for x: 4x=6(mod 5)

    Here is my solution:

    From the definition of modulus, we can write the above as [itex]\frac{4x−6}{5}=k[/itex], where [itex]k[/itex] is the remainder resulting from [itex]4x~mod~5=6~mod~5=k.[/itex]

    Solving for [itex]x[/itex], [itex]x=\frac{5k+6}{4}⟹x(k)=\frac{5k+6}{4}[/itex]

    Now, my teacher said that is incorrect, and that [itex]k=...−2,−1,0,1,2,...[/itex]

    I honestly don't understand what is wrong about my answer; and shouldn't k only take on nonnegative values, following from the definition of modulus?
  2. jcsd
  3. Apr 25, 2013 #2


    User Avatar
    2017 Award

    Staff: Mentor

    k can be any integer number. 4=6 mod 2, and 6=4 mod 2.
    "mod 2" refers to the "=", not to one side of the equation. This is different in computer science.

    Your x(k) will give answers only if the fraction there (evaluated in the real numbers) gives integers.
  4. Apr 26, 2013 #3
    So, I presume there is a different way of solving this, of which I am unaware of? Could you possibly give me a hint?
  5. Apr 26, 2013 #4
    I think I might have discovered why I am unable to do this problem: my teacher furnished this as a test question, despite the fact that my teacher did not even assign the chapter which deals with solving congruences, nor did my teacher assign probems. Frustrating but not out of the ordinary.
    Last edited: Apr 26, 2013
  6. Apr 26, 2013 #5


    User Avatar
    Science Advisor

    It would be better to write 4x- 6= 5k or 4x= 6+ 5k since all numbers here must be integers. And writing it as a fraction obscures that.

    Now: if k= 0, this is 4x= 6 which does not have an integer solution.
    If k= 1, this is 4x= 11 which does not have an integer solution.
    If k= 2, this is 4x= 16 which has x= 4 as a solution.

    And since this is "modulo 5", any x= 4+ 5k, for k any integer, is a solution.

    No, there is no requirement that "k" be non-negative. I don't know which of several equivalent defnitions of "modulus" you are using. One is "a= b (mod n) if and only if a- b is divisibe by n". Another is "a= b (mod n) if and only if a= b+ kn for some integer n".

    4- 5= -1 is also a value of "x= 4 (mod 5)" and satisfies 4(-1)= -4= 6 (mod 5) because 6- (-4)= 10 is a multiple of 5.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted