Primality proof for n = 35677501:

Take b = 2.

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

71 is prime.
b^((n-1)/71)-1 mod n = 34211506, which is a unit, inverse 18887383.

67 is prime.
b^((n-1)/67)-1 mod n = 4147432, which is a unit, inverse 1281082.

3 is prime.
b^((n-1)/3)-1 mod n = 30453007, which is a unit, inverse 1741497.

(3 * 67 * 71) divides n-1.

(3 * 67 * 71)^2 > n.

n is prime by Pocklington's theorem.