Primality proof for n = 12695774573265607:

Take b = 2.

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

705320809625867 is prime.
b^((n-1)/705320809625867)-1 mod n = 262143, which is a unit, inverse 9177331101675013.

(705320809625867) divides n-1.

(705320809625867)^2 > n.

n is prime by Pocklington's theorem.