1. Not finding help here? Sign up for a free 30min 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!

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?

    thanks
     
  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 The Chinese Remainder Theorem
     
  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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Simple problem 3x = 1 (mod 16), find all possible values of x mod 16
  1. X^2 + 1 = 0 (mod 5^3). (Replies: 2)

  2. X² + y² = 1 (mod p) (Replies: 7)

  3. Mod Problem (Replies: 3)

Loading...