why do we have to use totient theorem in this problem?
y = k*phi(m) + y%(p-1)
In above exp, if m = (p-1)
then k = ?
Totient theorem usage
@hari_2425 We use totient function to reduce the problem, into a more simple problem.
We now that if m is prime phi(m)=m-1.
Now for some number y, we can write it as, y=k(m-1) + y%(m-1) (we can always break down a number like thi, let m=11, we can write 33= 3*(11-1) + (33%(11-1)));
Now if y<(m-1) k will become zero. else it will be greater than 1, But its does not affect us as
a^(k*(m-1)+rem)=(a^(m-1)K )a^rem.
Now focus on (a^(m-1)K) = a^(m-1) * a^(m-1) * a^(m-1) … k times (simple exponentiation rule)
now we know. a^(m-1)%m=1 , so our term (a^(m-1)K)= 11*1…=1
Se we never needed the value of K
If this resolves your doubt mark it resolved.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.