Congruence Fermat's little theorem help

**duggaboy** · June 1st 2008, 06:40 PM

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 : )

**ThePerfectHacker** · June 1st 2008, 06:44 PM

Begin with 9^72 = 1 (mod 73)
Now keep on rasing exponents to get 794

**duggaboy** · June 2nd 2008, 01:08 PM

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

**Moo** · June 2nd 2008, 01:12 PM

Hello,

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)

**Mathstud28** · June 2nd 2008, 01:15 PM

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}$

**duggaboy** · June 2nd 2008, 01:24 PM

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

**Moo** · June 2nd 2008, 01:27 PM

Originally Posted by duggaboy

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

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 ?

**duggaboy** · June 2nd 2008, 01:32 PM

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?

**Moo** · June 2nd 2008, 01:38 PM

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

**duggaboy** · June 2nd 2008, 01:43 PM

not sure where i came across that formula ??

mods kill me!!

THANK YOU AGAIN!

**ThePerfectHacker** · June 2nd 2008, 01:44 PM

Originally Posted by duggaboy

mods kill me!!

Okay. How would you like to die?

**duggaboy** · June 2nd 2008, 01:49 PM

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)

Thread: Congruence Fermat's little theorem help

LinkBack

Thread Tools

Display

Congruence Fermat's little theorem help

feeling dumb

congruence mods

getting so close

ahha

checking point

Similar Math Help Forum Discussions

abstract algebra [primitive root mod n, euler theorem, fermat theorem]

Fermat's Little Theorem

Fermat's Little Theorem

Find x in the congruence using Fermat's Little Theorem

Congruence Proof (Application of Fermat's Theorem I believe)

Search Tags