페르마의 소정리로 소수를 구해보자

p는 소수이고, a는 p의 배수가 아니할 떄
a^(p-1) = 1 (mod p) 는 성립한다.

예를 들어 p는 7, a는 3일 경우,

3^(7-1) = 1 (mod 7) 
-> 729 = 1 (mod 7) 
-> 729 mod 7 = 1

729 / 7의 몫은 104이고 나머지는 1이므로 해당 공식은 성립한다.

여기서 a를 p의 1/2배보다 작은 수로 설정한 다음 부터 점점 1/2배 씩 감소하며 a가 1일 때까지 해당 공식이 성립한다면 p는 소수인 것이다.
만약 중간에 여기서 공식이 성립하지 않는 다면 p는 소수가 아닌 것이다.

Q.E.D.

예제 코드

function Fermat(p) {
  let a = p;
  while (true) {
    a = (a - a % 2) / 2;
    if (a === 1) {
      break;
    }
    let powed = (BigInt(a) ** BigInt(p - 1)) % BigInt(p)
    if (powed !== 1n) {
      return false;
    }
  }
  return true
}

무난하게 5자리대 수까지도 연산이 된다.