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!

: 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?

  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


    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook