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

[bobthebanana]

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

 

[Dragonfall]

Well, there are only 16 possible values for x; which ones work?

 

[bobthebanana]

Well is there a systematic way to solve a problem like this?

what if it were mod 2008

 

[ramsey2879]

Well is there a systematic way to solve a problem like this?

what if it were mod 2008

The systematic way is to use http://www.cut-the-knot.org/blue/chinese.shtml"

 

[mhill]

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'

 

[robert Ihnot]

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.

 

[robert Ihnot]

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:

$$\frac{2x2008+1}{3} = 1339$$ So X=1339 is the answer.

 

[ramsey2879]

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

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