BigMod(farmetts little theorem)

Fermat's little theorem states that if p is a prime number, then for any integer a, the number a p − a is an integer multiple of p. In the notation of modular arithmetic, this is expressed as

    a^p ≡ a ( mod p )

For example, if a = 2 and p = 7, 2^7 = 128, and 128 − 2 = 7 × 18 is an integer multiple of 7.

If a is not divisible by p, Fermat's little theorem is equivalent to the statement that a^(p − 1) − 1 is an integer multiple of p, or in symbols

    a^(p − 1) ≡ 1 ( mod p )

For example, if a = 2 and p = 7 then 26 = 64 and 64 − 1 = 63 is thus a multiple of 7.