Testing for prime

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 assume that if 2p mod p =2 then p is prime.

1) Probable primes

Decide which of these numbers is prime:

• 12
• 101
• 4249599619
• 5175703781
• 35563611982942194303
• 82793885002522383103

Input

let pl = [ 12n, 101n, 4249599619n, 5175703781n, 35563611982942194303n, 82793885002522383103n ]; document.body.append(... pl.map(n=>{ let isPrime = n%2n===1n; ret = document.createElement('div'); ret.innerHTML = `${n} is prime: ${isPrime}`; return ret; }) ); //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; }

​x

 

1

let pl = [ 12n, 101n, 4249599619n, 5175703781n,

2

 35563611982942194303n, 82793885002522383103n

3

];

4

document.body.append(...

5

  pl.map(n=>{

6

    let isPrime = n%2n===1n;

7

    ret = document.createElement('div');

8

    ret.innerHTML = `${n} is prime: ${isPrime}`;

9

    return ret;

10

  })

11

);

12

​

13

//raise n to the power e, modulo m

14

function pow(n,e,m){

15

  if (e<=0) return 1n;

16

  let r = pow(n,e/2n,m);

17

  return (r*r*(e%2n===1n?n:1n))%m;

18

}

19

​

Go reset

Output

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

//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
];
document.body.append(...
  pl.map(n=>{
    let isPrime = pow(2n,n,n)===2n;
    ret = document.createElement('div');
    ret.innerHTML = `${n} is prime: ${isPrime}`;
    return ret;
  })
);

//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;
}

2) Prime Billion

Find the first prime bigger than 1 billion

Input

let b = 1000000000n; while (b%2n===0n){ b = b+1n; } document.body.innerHTML = `${b}` //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; }

xxxxxxxxxx

 

1

let b = 1000000000n;

2

while (b%2n===0n){

3

  b = b+1n;

4

}

5

document.body.innerHTML = `${b}`

6

​

7

//raise n to the power e, modulo m

8

function pow(n,e,m){

9

  if (e<=0) return 1n;

10

  let r = pow(n,e/2n,m);

11

  return (r*r*(e%2n===1n?n:1n))%m;

12

}

13

​

Go reset

Output

let b = 1000000000n;
while (b%2n===0n){
  b = b+1n;
}
document.body.innerHTML = `${b}`

//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 b = 1000000000n;
while (pow(2n,b,b)!==2n){
  b = b+1n;
}
document.body.innerHTML = `${b}`

//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;
}

3) Prime Googol

• A googol is 1 followed by 100 zeros.
• Find the first prime bigger than 1 googol

Input

let b = 1000000000n; while (b%2n===0n){ b = b+1n; } document.body.innerHTML = `${b}` //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; }

xxxxxxxxxx

 

1

let b = 1000000000n;

2

while (b%2n===0n){

3

  b = b+1n;

4

}

5

document.body.innerHTML = `${b}`

6

​

7

//raise n to the power e, modulo m

8

function pow(n,e,m){

9

  if (e<=0) return 1n;

10

  let r = pow(n,e/2n,m);

11

  return (r*r*(e%2n===1n?n:1n))%m;

12

}

13

​

Go reset

Output

let b = 1000000000n;
while (b%2n===0n){
  b = b+1n;
}
document.body.innerHTML = `${b}`

//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 b = pow(10n,100n);
while (pow(2n,b,b)!==2n){
  b = b+1n;
}
document.body.innerHTML = `${b}`

//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);
  let ret = r*r*(e%2n===1n?n:1n);
  if (m===undefined)
    return ret;
  return ret%m
}