Concepts on remainder theorem

Fermet’s theorem

If ‘a’ and ‘p’ are two numbers such that p is prime number then

( a) ^p-1 divided by p will always leave remainder 1

For example 16^38 when divided by 7 then by ferments 16^6n divided by 7 will give remainder 1

further 16^2 divided by 7 will give remainder 4.

Euler’s theorem

When ‘a’ and ‘p’ are coprime and p is not prime number than a ^E divided by ‘p’ will leave remainder 1 , given

E = p( 1- 1/x) (1- 1/y)

Where x and y are prime factors of number, note we are not concerned with powers of x and y.

For example E for hundred will be
100 = 2^2 * 5^2

E = 100(1-1/2) ( 1- 1/5) = 40

So 3^ 80 / 100 will give remainder 1 by Euler’s theorem