Solve for X in Finite Fields

  • Thread starter PolyFX
  • Start date
  • #1
31
0

Homework Statement


Solve 3x + 50 = 11 in F53

Homework Equations


Extended Euclidean Algorithm


The Attempt at a Solution



To find 3-1 mod 53 using the euclidean algorithm:

gcd(53,3)

1)53/3 = 17 + 2R

53 = 17 * 3 + 2
2 = 53 - 17 * 3

3/2 = 1 + 1R

3 = 1 * 2 + 1
1 = 3 - 1 * 2 = 3 - 2


Now going from reverse;

1 = 3 - (53 - 17 * 3)
= 3 - 53 + 17 * 3
= 18*3 - 53

3-1 = 18 mod 53

3x + 50 = 11
3x = 11 - 50 mod53 ==> 3x = -39 mod 53
3x = 14 mod 53

I'm stuck after this step. How do I solve for x?

-Thanks
 

Answers and Replies

  • #2
22,129
3,297
When your at 3x=14, just multply both sides by [tex]18=3^{-1}[/tex]. You should get there then...
 
  • #3
31
0
When your at 3x=14, just multply both sides by [tex]18=3^{-1}[/tex]. You should get there then...

Hi micromass,

So

3x = 14 mod 53
18 * 3x = 18 * 14 mod 53

Is it safe to assume that 18 * 3x = x since 3*3-1 = 1?

therefore

x = 18 * 14 mod 53
= 252 mod 53
= 40 mod 53

Is this the correct approach?

-Thanks
 
  • #4
Dick
Science Advisor
Homework Helper
26,263
619
Hi micromass,

So

3x = 14 mod 53
18 * 3x = 18 * 14 mod 53

Is it safe to assume that 18 * 3x = x since 3*3-1 = 1?

therefore

x = 18 * 14 mod 53
= 252 mod 53
= 40 mod 53

Is this the correct approach?

-Thanks

It looks fine. Check it. Put x=40 in your original equation. Does it work?
 
  • #5
31
0
It looks fine. Check it. Put x=40 in your original equation. Does it work?

Haha of course. Yep, I plugged in 40 back into the original equation and I got

3x + 50 = 11 mod 53
3(40) + 50 = 11 mod 53
120 => 11 mod 53


However, I have another question

Say you're given something like this

"Solve 7x + 2 = 2-100 in F19"

I tried doing this the same way as the previous problem but once again I am stuck. Here is what I have so far.


Find 7-1 mod 19

gcd(19,7)

19/7 = 2 + 5R

19 = 2 * 7 + 5
5 = 19 - 2 * 7


7/5 = 1 + 2 R

7 = 1 * 5 + 2
2 = 7 - 1*5

5/2 = 2 + 1
5 = 2 * 2 + 1
1 = 5 - 2 * 2

Going from reverse:

1 = 5 - 2 * 2
= 5 - 2 * (7 - 5)
= 5 - 2*7 + 2*5
= 3*5 - 2*7
3*(19-2*7) - 2*7
=3*19 - 6*7 -2*7
=3*19 -8*7

Therefore 7-1 = -8 = 11 mod 19

7x = 2-100 - 2 mod 19

This is where I'm having problems. What do I do next?
 
  • #6
22,129
3,297
Just multiply both sides by [tex]7^{-1}[/tex].
Also, [tex]2^{100}[/tex] can be simplified by using Fermat's little theorem.
 
  • #7
31
0
Just multiply both sides by [tex]7^{-1}[/tex].
Also, [tex]2^{100}[/tex] can be simplified by using Fermat's little theorem.


Hi, I'm a little lost as to how to use Fermats Little Theorem to simplify.

2-100 mod 19

Since 19 is prime then that should mean that 218 mod 19 = 1.

So,

2-100 mod 19:

= 218 * -5 + (-10) mod 19
=(218)-5 * 510 mod 19
= 1-5 * 510 mod 19
= 510 mod 19

I need some assistance after this part however, I don't believe it is correct either.


-Thanks
 
  • #8
22,129
3,297
Hi, I'm a little lost as to how to use Fermats Little Theorem to simplify.

2-100 mod 19

Since 19 is prime then that should mean that 218 mod 19 = 1.

So,

2-100 mod 19:

= 218 * -5 + (-10) mod 19
=(218)-5 * 510 mod 19
= 1-5 * 510 mod 19
= 510 mod 19

I need some assistance after this part however, I don't believe it is correct either.


-Thanks

I don't see how that 510 gets there. The answer should be [tex]2^{-100}=2^{-10}[/tex].

Now, 210 is easily calculatable, so finding its inverse should also pose no problem...
 

Related Threads on Solve for X in Finite Fields

  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
513
  • Last Post
Replies
6
Views
8K
  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
1
Views
1K
Top