Doubt about taking mod at the current video stamp. Why mod of y taken with “mod-1” and not “mod” https://youtu.be/K_UOxtlAIms?t=679
Why mod of y taken with "mod-1" and not "mod"
According to Fermat’s little theorem,
a^(p-1) mod p = 1, When p is prime.
From this, as of the problem, M is prime, express A^B mod M as follows:
A^B mod M = ( A^(M-1) * A^(M-1) *.......* A^(M-1) * A^(x) ) mod M
Where x is B mod M-1 and A ^ (M-1) continues B/(M-1) times
Now, from Fermat’s Little Theorem,
A ^ (M-1) mod M = 1.
Hence,
A^B mod M = ( 1 * 1 * ....... * 1 * A^(x) ) mod M
Hence mod B with M-1 to reduce the number to a smaller one and then use power() method to compute (a^b)%m.
could not understand the expression A^B mod M = ( A^(M-1) * A^(M-1) … A^(M-1) * A^(x) ) mod M
Thank you very much for writing solution and explaining in detail. But I will be very grateful to you if you kindly explain the last line of your first reply. “Hence mod B with M-1 to reduce the number to a smaller one and then use power() method to compute (a^b)%m.”
as you saw when we use m-1 to divide B how our (A^B)%M reduced to (A^X)%M where X is remainder when we divide B from M-1 that is B%(M-1) hence we need to calculate B%(M-1) which will work as X and then simply proceed towards solution.
Thank you for clearing my doubt with so much detail.