# Testing for prime

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.

## Probable primes

Decide which of these numbers is prime:

• 12
• 101
• 4249599619
• 5175703781
• 35563611982942194303
• 82793885002522383103
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;
}

## Prime Billion

Find the first prime bigger than 1 billion

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

## Prime Googol

• A googol is 1 followed by 100 zeros.
• Find the first prime bigger than 1 googol
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
}

## Primes per Thousand

• For the 1000 numbers from 1000000 to 1000999 how many are prime?

let b = pow(10n,6n);
let pc = 0;
for(let i=0n;i<1000n;i++){
let p = b+i;
if (pow(2n,p,p)===2n)
pc++;
}
document.body.innerHTML = `\${pc}`

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

## Primes per Thousand Again

• How primes are there in the thousand number starting:
• 1000000 (106),10000000,100000000, ... 1000000000000 (1012)
let ls = [];
for(let j=6n;j<=12n;j++){
let b = pow(10n,j);
let pc = 0;
for(let i=0n;i<1000n;i++){
let p = b+i;
if (p%2n!==0n)
pc++;
}
ls.push(`<tr><td>\${b}</td><td>\${pc}</td></tr>`);
}
document.body.innerHTML = `<table>\${ls.join('')}</table>`

//raise n to the power e, modulo m
//m is optional
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
}
let ls = [];
for(let j=6n;j<=12n;j++){
let b = pow(10n,j);
let pc = 0;
for(let i=0n;i<1000n;i++){
let p = b+i;
if (pow(2n,p,p)===2n)
pc++;
}
ls.push(`<tr><td>\${b}</td><td>\${pc}</td></tr>`);
}
document.body.innerHTML = `<table>\${ls.join('')}</table>`

//raise n to the power e, modulo m
//m is optional
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
}