Primality proof for n = 27678676889:

Take b = 2.

b^(n-1) mod n = 1.

119087 is prime.
b^((n-1)/119087)-1 mod n = 11069242734, which is a unit, inverse 20394477560.

1709 is prime.
b^((n-1)/1709)-1 mod n = 14370813982, which is a unit, inverse 12694812043.

(1709 * 119087) divides n-1.

(1709 * 119087)^2 > n.

n is prime by Pocklington's theorem.