# Solve for X in Finite Fields

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

When your at 3x=14, just multply both sides by $$18=3^{-1}$$. You should get there then...

When your at 3x=14, just multply both sides by $$18=3^{-1}$$. 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

Dick
Homework Helper
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?

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?

Just multiply both sides by $$7^{-1}$$.
Also, $$2^{100}$$ can be simplified by using Fermat's little theorem.

Just multiply both sides by $$7^{-1}$$.
Also, $$2^{100}$$ 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

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 $$2^{-100}=2^{-10}$$.

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