Testing for prime

Probable primes

Fermat's little theorem tells us that

xp mod p = x

if p is prime for x<p

The converse is that if

xp mod p ≠ x

then p is not prime. If the equality holds for some value of x then p is probably a prime. If the equality holds for two values of x then it is even more probable that p is prime. For these questions you can ignore that probability.

Decide which of these numbers is prime:

• 12
• 101
• 4249599619
• 5175703781
• 35563611982942194303
• 82793885002522383103
• 629817083229352620706184583313
• 984141389525199908877737938759

let pl = [ 12n, 101n, 4249599619n, 5175703781n,
 35563611982942194303n, 82793885002522383103n,
 629817083229352620706184583313n,
 984141389525199908877737938759n
];
document.body.append(...
  pl.map(n=>{
    let isPrime = n%2===1;
    ret = document.createElement('div');
    ret.innerHTML = `${n} is prime: ${isPrime}`;
  });
);

//raise n to the power e, modulo m
function pow(n,e,m){
  if (e<=0) return 1n;
  let r = pow(n,e/2n,m);
  return (r*r*(e%2n===1n?n:1n))%m;
}

let pl = [ 12n, 101n, 4249599619n, 5175703781n,
 35563611982942194303n, 82793885002522383103n,
 629817083229352620706184583313n,
 984141389525199908877737938759n
];
document.body.append(...
  pl.map(n=>{
    let isPrime = pow(2,n,n)===2;
    ret = document.createElement('div');
    ret.innerHTML = `${n} is prime: ${isPrime}`;
  });
);

//raise n to the power e, modulo m
function pow(n,e,m){
  if (e<=0) return 1n;
  let r = pow(n,e/2n,m);
  return (r*r*(e%2n===1n?n:1n))%m;
}