Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Simple problem 3x = 1 (mod 16), find all possible values of x mod 16

  1. Feb 29, 2008 #1
    simple problem... 3x = 1 (mod 16), find all possible values of x mod 16

    so this is what i've come to:
    3x = 1 + 16k, where k is any integer

    i'm stuck though, any help?

  2. jcsd
  3. Feb 29, 2008 #2
    Well, there are only 16 possible values for x; which ones work?
  4. Feb 29, 2008 #3
    Well is there a systematic way to solve a problem like this?

    what if it were mod 2008
  5. Feb 29, 2008 #4
    The systematic way is to use http://www.cut-the-knot.org/blue/chinese.shtml" [Broken]
    Last edited by a moderator: May 3, 2017
  6. Feb 29, 2008 #5
    well, you put 3x-16k=1

    by simple inspection i get the solution x=-5 and k=-1 , since the congruence is purely linear the solution can be written as

    x= -5+16t and k= -1+3t where 't' is just any integer

    the smallest positive solution is x=11 and k=2

    To solve the general congruence ax+by=c

    a) using trial and error find a paritcular solution , let's say x=m and y=n

    b) we are supposing that gcd (a,b)=1 , the solution then may be written as

    x= m+bt y=n-at for any integer 't'
    Last edited: Feb 29, 2008
  7. Feb 29, 2008 #6
    This problem has showed up by the same author in General Math, under "Simple Problem 3X==1 (16)

    I answered it there: 3 is relatively prime to 16, thus the elements 3x1, 3x2, 3x3....3x15 are all distinct, and simply form a permutation of the original multiplicative group. That is to say.....there is only a single answer to your problem.

    You can see that also by:

    Then all you have to do is find that one number. Hint(1): It can't be a multiple of 2. Hint(2): Look for a solution of and then subtract that number from 16.
  8. Feb 29, 2008 #7
    bobthebanana: what if it were mod 2008? (3x==1 Mod 2008)

    They are certain more or less systematic ideas. 2008 =8x251, so you could try working out solutions for 251 and for 8 and use the Chinese Remainder Theorem.

    However with a simple modulus like 3, we can use inspection.

    We have the equation 2008K +1 = 3j. It happens to be that 2007 is divisible by 3, in fact, by 9. Thus 2008 is one more than a multiple of 3, and so is 1. Thus we need k=2. This gives us:

    [tex]\frac{2x2008+1}{3} = 1339 [/tex] So X=1339 is the answer.
    Last edited: Feb 29, 2008
  9. Mar 1, 2008 #8
    As Robert pointed out with respect to 2008, 16 = 1 mod 3 so k must equal 2 mod 3 since
    1 + 16k = 3x
    1 + k = 3 mod 3
    k = 2 mod 3

    so the smallest positive value of x is (2*16 + 1)/3 or 11.
    3*16/3 = 16 so x = 11 +16t
    Last edited: Mar 1, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook