Fermats theorem

#1

pls explain me the fermats theorem code.

#2

it is basically used for calculating multiplicative modulo inverse

We know x^(p-1) mod p => 1 if p is prime number…fermant little theorem

now to calculate (a^b) mod p .
we can write b = (p-1) + (p-1) + (p-1) … + k

where k is remainder we are left with. i.e k=b%(p-1)

substituting value of b
(a^b)mod p = a^(p-1 + p-1 + p-1 + p-1 … + k) mod p

now using property a^(x+y) => a^x * a^y

=> ( a^(p-1) * a^(p-1) * a^(p-1) … a^k )mod p

now we know a^(p-1) mod p =1

=> 1 * 1 * 1 …a^k mod p
=> a^k mod p
substituting value of k
=> a^(b%(p-1) ) mod p

here refer this
(https://www.google.com/amp/s/www.geeksforgeeks.org/fermats-little-theorem/amp/)
dont forget to hit like and mark resolved if cleared :smiley: