🔢

Fermat's Little Theorem

★★★★☆Undergraduate

📖Definition

If p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p).

a^p-1 ≡ 1 ±odp

a^p ≡ a ±odp

Fermat's Little Theorem (variant)

예제 1

Find 2^10 mod 11 using Fermat's Little Theorem.

예제 2

Find 3^100 mod 7.

Discovered by: Pierre de Fermat (1640)

First mentioned in a letter to Mersenne; proved by Euler.

RSA, primality testing

Fast exponentiation

#페르마#소정리#Fermat#little theorem