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 : )
Hello,
Basis :
$\displaystyle a=b\mod n$ means that $\displaystyle 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 :
$\displaystyle a=b \mod n \Longleftrightarrow a+c=b+c \mod n$
Also, $\displaystyle a=b \mod n \Longleftrightarrow a=b+kn \mod n$, for any k in $\displaystyle \mathbb{Z}$
$\displaystyle 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.
$\displaystyle a=b \mod n \implies a*c=b*c \mod n$
Be careful :
$\displaystyle a=b \mod n \not \implies \frac ac=\frac bc \mod n$
There are several properties you should know...
Fermat's little theorem states :
$\displaystyle \text{If p is a prime number, then } a^{p-1}=1 \mod p$ (with a, not multiple of p)
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 :
$\displaystyle 794=72*11+2$
Therefore $\displaystyle 9^{794}=(9^{72})^{11}*9^2$ (these are powers rules)
-------> $\displaystyle 9^{794}=1^{11}*9^2 \mod 794$
Conclude ?
Hmmmm strange oO
what is this formula ?
All you need is to "simplify" $\displaystyle 9^{794} \mod 73$, in order to get x.
$\displaystyle 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