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

[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

 

[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.

 

[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 ...).

 

[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.