How do I use Fermat's Little Theorem to solve for x in F19?

[PolyFX]

Homework Statement

Solve 3x + 50 = 11 in F₅₃

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 - 2Now 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

 

[micromass]

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

 

[PolyFX]

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

 

[Dick]

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?

 

[PolyFX]

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 F₁₉"

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?

 

[micromass]

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

 

[PolyFX]

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 2¹⁸ mod 19 = 1.

So,

2^-100 mod 19:

= 2^{18 * -5 + (-10)} mod 19
=(2¹⁸)^-5 * 5¹⁰ mod 19
= 1^-5 * 5¹⁰ mod 19
= 5¹⁰ mod 19

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

 

[micromass]

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 2¹⁸ mod 19 = 1.

So,

2^-100 mod 19:

= 2^{18 * -5 + (-10)} mod 19
=(2¹⁸)^-5 * 5¹⁰ mod 19
= 1^-5 * 5¹⁰ mod 19
= 5¹⁰ 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 5¹⁰ gets there. The answer should be [tex]2^{-100}=2^{-10}[/tex].

Now, 2¹⁰ is easily calculatable, so finding its inverse should also pose no problem...