Using Fermat's Little Theorem find the value for x.

x ≡ 9^(794) mod 73

I don't even know where to begin, I need step by step help majorly : )

Printable View

- Jun 1st 2008, 06:40 PMduggaboyCongruence Fermat's little theorem help
Using Fermat's Little Theorem find the value for x.

x ≡ 9^(794) mod 73

I don't even know where to begin, I need step by step help majorly : ) - Jun 1st 2008, 06:44 PMThePerfectHacker
Begin with 9^72 = 1 (mod 73)

Now keep on rasing exponents to get 794 - Jun 2nd 2008, 01:08 PMduggaboyfeeling dumb
This is totally stupid I know, but what is the base for using Mods? I've never used them by hand, only TI89 which now I have to show by hand, I'm totally lost..

- Jun 2nd 2008, 01:12 PMMoo
Hello,

Basis :

means that is a multiple of n.

In some cases, b represents the remainder of a in the Euclidian division by n.

a and b can be negative or positive.

Basic operations :

Also, , for any k in

<< for this one, always look for congruences to 1, because any power of 1 always yields 1.

Be careful :

There are several properties you should know...

Fermat's little theorem states :

(with a, not multiple of p) - Jun 2nd 2008, 01:15 PMMathstud28
- Jun 2nd 2008, 01:24 PMduggaboycongruence mods
Okay that makes a lot of sense thank you so much!!!

In solving x ≡ 9^(794) mod 73

I see where 9^72 *9^72 (until I get 794) but here I'm a little stuck cause 9^72 (11 times) gives me 9^792 so then at that point would I also include 9^2?? - Jun 2nd 2008, 01:27 PMMoo
- Jun 2nd 2008, 01:32 PMduggaboygetting so close
BTW your the BEST!!

now that I have the 1^11*9^2 (mod 794)

Would I use the equation a^p = 9 + 794k to find a? - Jun 2nd 2008, 01:38 PMMoo
- Jun 2nd 2008, 01:43 PMduggaboyahha
not sure where i came across that formula ??(Thinking)

mods kill me!!

THANK YOU AGAIN! - Jun 2nd 2008, 01:44 PMThePerfectHacker
- Jun 2nd 2008, 01:49 PMduggaboychecking point
when solving for x here using the approach from the previous problem

x^86 = = 6 (mod 29)

I am getting

x = 36 (mod 29)

36^86 = = 6 (mod 29) or just

36 = = 6 (mod 29)