Primality proof for n = 26889041:

Take b = 2.

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

336113 is prime.
b^((n-1)/336113)-1 mod n = 15328821, which is a unit, inverse 13939937.

(336113) divides n-1.

(336113)^2 > n.

n is prime by Pocklington's theorem.