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

  • Thread starter bobthebanana
  • Start date
In summary, the problem is asking to find all possible values of x mod 16 for the equation 3x = 1 (mod 16). The solution is that there is only one possible value, which can be found by looking for a solution of 3x ≡ -1 ≡ 15 (mod 16) and subtracting it from 16. Alternatively, you can brute force by trying 3x mod 16 for x = 0 to 17 and looking for a repeating pattern. Another method is to add 1 to the multiples of 16 up to 32 and divide by 3 until an integer is obtained.
  • #1
bobthebanana
23
0
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
 
Mathematics news on Phys.org
  • #2
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: [tex]3x \equiv 3y Mod {16} \rightarrow {x} \equiv {y} Mod {16.} [/tex]

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 [tex] 3x \equiv {-1}\equiv{15} Mod 16 [/tex] and then subtract that number from 16.
 
Last edited:
  • #3
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:
  • #4
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.
 

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

What is the problem asking for?

The problem is asking for all possible values of x mod 16 that satisfy the equation 3x = 1 (mod 16).

What is the meaning of "mod" in this context?

In this context, "mod" stands for the modulus operation, which calculates the remainder after dividing the first number by the second number.

What is the first step in solving this problem?

The first step is to add 16 to both sides of the equation, resulting in 3x + 16 = 1 (mod 16).

How many solutions does this problem have?

This problem has infinitely many solutions, as every integer value of x satisfies the equation when taken mod 16.

What are the possible values of x mod 16?

The possible values of x mod 16 are all integers from 0 to 15, as any value within this range can be expressed as x = 3x + 16 (mod 16).

Similar threads

Replies
5
Views
2K
  • General Math
Replies
1
Views
1K
  • Quantum Physics
Replies
3
Views
969
  • General Math
Replies
12
Views
4K
  • Calculus and Beyond Homework Help
Replies
25
Views
500
  • Calculus and Beyond Homework Help
Replies
1
Views
5K
Replies
2
Views
996
  • General Math
Replies
1
Views
1K
Back
Top