# : simple problem 3x = 1 (mod 16), find all possible values of x mod 16

1. Feb 29, 2008

### bobthebanana

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. Feb 29, 2008

### robert Ihnot

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

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 $$3x \equiv {-1}\equiv{15} Mod 16$$ and then subtract that number from 16.

Last edited: Feb 29, 2008
3. Feb 29, 2008

### rcgldr

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
4. Mar 3, 2008

### Werg22

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.