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

1. Feb 29, 2008

### 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

2. Feb 29, 2008

### Dragonfall

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

3. Feb 29, 2008

### bobthebanana

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

what if it were mod 2008

4. Feb 29, 2008

### ramsey2879

The systematic way is to use The Chinese Remainder Theorem

5. Feb 29, 2008

### 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'

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

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

7. Feb 29, 2008

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

Last edited: Feb 29, 2008
8. Mar 1, 2008

### ramsey2879

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

Last edited: Mar 1, 2008