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
    URGENT: simple problem... 3x = 1 (mod 16), find all possible values of x mod 16

    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
    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: [tex]3x \equiv 3y Mod {16} \rightarrow {x} \equiv {y} Mod {16.} [/tex]

    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 [tex] 3x \equiv {-1}\equiv{15} Mod 16 [/tex] and then subtract that number from 16.
     
    Last edited: Feb 29, 2008
  4. Feb 29, 2008 #3

    rcgldr

    User Avatar
    Homework Helper

    You can just brute force this one by trying 3x mod 16, with x = 0 to 17 and look for a repeating pattern. All modulo sequences like this will repeat, but may not include all the numbers from 0 to M-1 (where M is the modulus), for example an even number times X modulo an even number will never produce an odd result, cutting out half the numbers in the range, and the cycle repeats at a faster "rate" (2X mod 8 for X = 0->n = 0 2 4 6 0 2 4 6 ...).
     
    Last edited: Feb 29, 2008
  5. Mar 3, 2008 #4
    Adding 1 to the multiples of 16 up to 32 and dividing by 3 until obtention of an integer is an easier solution, I believe.
     
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. Prove that -4 x -4 = 16 (Replies: 24)

Loading...