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

  • Thread starter bobthebanana
  • Start date
In summary, the possible values of x mod 16 for the equation 3x = 1 (mod 16) are 11, 27, 43, 59, 75, 91, 107, 123, 139, 155, 171, 187, 203, 219, 235, 251.
  • #1
bobthebanana
23
0
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
 
Physics news on Phys.org
  • #2
Well, there are only 16 possible values for x; which ones work?
 
  • #3
Well is there a systematic way to solve a problem like this?

what if it were mod 2008
 
  • #4
bobthebanana said:
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"
 
Last edited by a moderator:
  • #5
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:
  • #6
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
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:

[tex]\frac{2x2008+1}{3} = 1339 [/tex] So X=1339 is the answer.
 
Last edited:
  • #8
bobthebanana said:
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
 
Last edited:

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

1. What is the meaning of "mod" in the equation 3x = 1 (mod 16)?

The term "mod" stands for "modulo" and is used to indicate the remainder after dividing a number by another number. In this case, we are looking for all possible values of x that leave a remainder of 1 when divided by 16.

2. How do I solve the equation 3x = 1 (mod 16)?

To solve this equation, we can use modular arithmetic. We can rewrite the equation as x ≡ 3-1 (mod 16), where 3-1 is the modular inverse of 3. The modular inverse of a number is the number that, when multiplied by the original number, gives a remainder of 1 when divided by the modulo. In this case, the modular inverse of 3 is 11, so x ≡ 11 (mod 16).

3. Are there any other possible values of x that satisfy the equation 3x = 1 (mod 16)?

Yes, since 11 is the modular inverse of 3, we can also write x ≡ -5 (mod 16). This is because -5 is equivalent to 11 (mod 16), as both have a remainder of 11 when divided by 16.

4. Can the value of x be a decimal or fraction?

No, the value of x must be an integer when working with modular arithmetic. This is because we are dealing with remainders, which are always whole numbers.

5. Is there a limit to the number of possible values of x mod 16?

Yes, there are a finite number of possible values of x mod 16. In this case, there are 16 possible values, as we are working with a modulo of 16. These values range from 0 to 15, as 16 is the smallest number that is greater than 1 and leaves a remainder of 1 when divided by 3.

Similar threads

  • Quantum Physics
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
25
Views
600
  • Linear and Abstract Algebra
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
  • Precalculus Mathematics Homework Help
Replies
15
Views
901
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
8
Views
839
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
8
Views
1K
Back
Top