# Congruence Fermat's little theorem help

• Jun 1st 2008, 06:40 PM
duggaboy
Congruence 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 PM
ThePerfectHacker
Begin with 9^72 = 1 (mod 73)
Now keep on rasing exponents to get 794
• Jun 2nd 2008, 01:08 PM
duggaboy
feeling 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 PM
Moo
Hello,

Quote:

Originally Posted by duggaboy
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..

Basis :

$a=b\mod n$ means that $a-b$ 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 :

$a=b \mod n \Longleftrightarrow a+c=b+c \mod n$

Also, $a=b \mod n \Longleftrightarrow a=b+kn \mod n$, for any k in $\mathbb{Z}$

$a=b \mod n \implies a^c=b^c \mod n$ << for this one, always look for congruences to 1, because any power of 1 always yields 1.

$a=b \mod n \implies a*c=b*c \mod n$

Be careful :

$a=b \mod n \not \implies \frac ac=\frac bc \mod n$

There are several properties you should know...

Fermat's little theorem states :

$\text{If p is a prime number, then } a^{p-1}=1 \mod p$ (with a, not multiple of p)
• Jun 2nd 2008, 01:15 PM
Mathstud28
Quote:

Originally Posted by Moo
Hello,

Basis :

$a=b\mod n$ means that $a-b$ is a multiple of n.

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

Basic operations :

$a=b \mod n \Longleftrightarrow a+c=b+c \mod n$

$a=b \mod n \implies a^c=b^c \mod n$ << for this one, always look for congruences to 1, because any power of 1 always yields 1.

Be careful :

$a=b \mod n \not \implies \frac ac=\frac bc \mod n$

There are several properties you should know...

Fermat's little theorem states :

$\text{If p is a prime number, then } a^{p-1}=1 \mod p$

Just to add to Moo's wonderful response, it also might be helpful to know Wilson's Theorem

Iff $p$ is a prime then $(p-1)!+1\equiv{0} \mod\text{ p}$
• Jun 2nd 2008, 01:24 PM
duggaboy
congruence mods
Okay that makes a lot of sense thank you so much!!!

In solving x9^(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 PM
Moo
Quote:

Originally Posted by duggaboy
Okay that makes a lot of sense thank you so much!!!

In solving x9^(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??

Yep, nearly ^^

Actually, when dealing with such questions, always find the power to which the number (here, 9) will be congruent to 1 modulo n (794).

Then, do the Euclidian division :

$794=72*11+2$

Therefore $9^{794}=(9^{72})^{11}*9^2$ (these are powers rules)

-------> $9^{794}=1^{11}*9^2 \mod 794$

Conclude ?
• Jun 2nd 2008, 01:32 PM
duggaboy
getting 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 PM
Moo
Quote:

Originally Posted by duggaboy
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?

Hmmmm strange oO
what is this formula ?

All you need is to "simplify" $9^{794} \mod 73$, in order to get x.

$x=1^{11}*9^2 \mod 73$, not 794 :) Don't confuse with the numbers, it's quite common to see that kind of mistakes ^^

Now, just simplify 1^11 and calculate 9². It will give you x :p
• Jun 2nd 2008, 01:43 PM
duggaboy
ahha
not sure where i came across that formula ??(Thinking)
mods kill me!!

THANK YOU AGAIN!
• Jun 2nd 2008, 01:44 PM
ThePerfectHacker
Quote:

Originally Posted by duggaboy
mods kill me!!

Okay. How would you like to die?
• Jun 2nd 2008, 01:49 PM
duggaboy
checking 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)