Using E.F. Theorem to reduce exponent

45 Views Asked by At

Apllying what a sequence of rules helps to get (2) from (1)?

How does (2) result from (1)

(1) $a^{\varphi(n)}\equiv1\ mod\ n$

(2) $a^e\equiv a^{e+k*\varphi(n)}mod\ n$

$=a^e*a^{k*\varphi(n)}mod\ n$ #this reshape from one above is clear

I am aware of following conditions the above relation was valid under. Further might exist, that's not clear for me.

$gcd(k,\varphi(n))=1$

$k\in Z$

1

There are 1 best solutions below

0
On BEST ANSWER

$1 \equiv a^{\phi(n)} (\bmod n)$ then we can take both sides to the power k. $1^k = 1 \equiv a^{k\phi(n)} (\bmod n)$ finally we multiply both sides by $a^e$. $a^e \equiv a^e \cdot a^{k\phi(n)} (\bmod n)$