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: Help with a mod problem

  1. Sep 9, 2011 #1
    1. The problem statement, all variables and given/known data

    For what integers is x^2-2x-3 divisible by 8.

    give answer x = a list of natural numbers (mod 8)

    2. Relevant equations



    3. The attempt at a solution

    I thought x(x-2) = 3 (mod 8) and tried to find all values that satisfied this. But got really stuck.
    I also tried to find values that gave a reminder of zero when the quadratic was divided by 8, which i think was 7, 11, 15 but this was not correct.
    I thought this was quite difficult as i thought my solutions made sense, but i must have misunderstood it somewhere. Thanks! its much appreciated.
     
  2. jcsd
  3. Sep 9, 2011 #2

    ehild

    User Avatar
    Homework Helper

    Factorize the left hand side first: it is x(x-2). The product has to be 3(mod 8), so the factors have to be either {1(mod 8) * 3(mod 8)} or {(-1)(mod 8) * (-3)(mod 8)}. Which of x and x-2 can be 1 (mod 8) so the other is 3 (mod 8)? The same with -1 and -3.


    ehild
     
    Last edited: Sep 10, 2011
  4. Sep 9, 2011 #3

    HallsofIvy

    User Avatar
    Science Advisor

    Since this is "mod 8", it's not too difficult to "exhaust" the cases:
    if x= 0 then 0(0- 2)= 0 (mod 8), not 3
    if x= 1 then 1(1- 2)= -1= 7 (mod 8), not 3
    if x= 2 then 2(2- 2)= 0 (mod 8), not 3
    if x= 3 then 3(3- 2)= 3 (mod 8) !!!

    if x= 4 then 4(4- 2)= 8= 0 (mod 8), not 3
    if x= 5 then 5(5- 2)= 15= 7 (mod 8), not 3
    if x= 6 then 6(6- 2)= 24= 0 (mod 8), not 3
    if x= 7 then 7(7- 2)= 35= 3 (mod 8)!!!!

    So x= 3 (mod 8) or x= 7 (mod 8) so any x of the form x= 3+ 8n or x= 7+ 8n, where 8 is any integer, satisfies this equation.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook