Charcoal, 35 bytes

Ｎθ≔Ｘ²⁻Ｘθ³θηＷ∨﹪Π…¹θθ﹪÷Ｘηθ⊖η⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code. Uses @xnor's formulas (see @Sisyphus's answer), so slow for large inputs (seems to be OK up to \$ b = 27 \$ at least). Explanation:

Ｎθ

Input \$ n \$, which is initially equal to \$ b \$.

≔Ｘ²⁻Ｘθ³θη

Calculate \$ 2 ^ { b (b - 1) (b + 1) } \$ which is used in @xnor's GCD calculation.

Ｗ∨

While either...

﹪Π…¹θθ

... \$ n \$ does not divide \$ (n - 1)! \$, meaning that \$ n \$ is 4 or prime, or...

﹪÷Ｘηθ⊖η⊖Ｘ²θ

... \$ 2 ^ n - 1 \$ does not divide \$ \left \lfloor \frac { 2 ^ { n b (b - 1) (b + 1) } } { 2 ^ { b (b - 1) (b + 1) } - 1 } \right \rfloor \$, meaning that \$ n \$ is not coprime to all of \$ b - 1 \$, \$ b \$ and \$ b + 1 \$, ...

≦⊕θ

... increment \$ n \$.

Ｉθ

Output the final value of \$ n \$.

Much faster 38-byte version which performs separate coprimaility testing on \$ b - 1 \$, \$ b \$ and \$ b + 1 \$:

Ｎθ≔Ｅ³Ｘ²⊖⁺θιηＷ∨﹪Π…¹θθ⊙η﹪÷Ｘκθ⊖κ⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code.

Charcoal, 35 bytes

Ｎθ≔Ｘ²⁻Ｘθ³θηＷ∨﹪Π…¹θθ﹪÷Ｘηθ⊖η⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code. Uses @xnor's formulas (see @Sisyphus's answer), so slow for large inputs (seems to be OK up to \$ b = 27 \$ at least). Explanation:

Ｎθ

Input \$ n \$, which is initially equal to \$ b \$.

≔Ｘ²⁻Ｘθ³θη

Calculate \$ 2 ^ { b (b - 1) (b + 1) } \$ which is used in @xnor's GCD calculation.

Ｗ∨

While either...

﹪Π…¹θθ

... \$ n \$ does not divide \$ (n - 1)! \$, meaning that \$ n \$ is 4 or prime, or...

﹪÷Ｘηθ⊖η⊖Ｘ²θ

... \$ 2 ^ n - 1 \$ does not divide \$ \left \lfloor \frac { 2 ^ { n b (b - 1) (b + 1) } } { 2 ^ { b (b - 1) (b + 1) } - 1 } \right \rfloor \$, meaning that \$ n \$ is not coprime to all of \$ b - 1 \$, \$ b \$ and \$ b + 1 \$, ...

≦⊕θ

... increment \$ n \$.

Ｉθ

Output the final value of \$ n \$.

Much faster 38-byte version which performs separate coprimaility testing on \$ b - 1 \$, \$ b \$ and \$ b + 1 \$:

Ｎθ≔Ｅ³Ｘ²⊖⁺θιηＷ∨﹪Π…¹θθ⊙η﹪÷Ｘκθ⊖κ⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code.

Charcoal, 35 bytes

Ｎθ≔Ｘ²⁻Ｘθ³θηＷ∨﹪Π…¹θθ﹪÷Ｘηθ⊖η⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code. Uses @xnor's formulas (see @Bubbler's answer), so slow for large inputs (seems to be OK up to \$ b = 27 \$ at least). Explanation:

Ｎθ

Input \$ n \$, which is initially equal to \$ b \$.

≔Ｘ²⁻Ｘθ³θη

Calculate \$ 2 ^ { b (b - 1) (b + 1) } \$ which is used in @xnor's GCD calculation.

Ｗ∨

While either...

﹪Π…¹θθ

... \$ n \$ does not divide \$ (n - 1)! \$, meaning that \$ n \$ is 4 or prime, or...

﹪÷Ｘηθ⊖η⊖Ｘ²θ

... \$ 2 ^ n - 1 \$ does not divide \$ \left \lfloor \frac { 2 ^ { n b (b - 1) (b + 1) } } { 2 ^ { b (b - 1) (b + 1) } - 1 } \right \rfloor \$, meaning that \$ n \$ is not coprime to all of \$ b - 1 \$, \$ b \$ and \$ b + 1 \$, ...

≦⊕θ

... increment \$ n \$.

Ｉθ

Output the final value of \$ n \$.

Much faster 38-byte version which performs separate coprimaility testing on \$ b - 1 \$, \$ b \$ and \$ b + 1 \$:

Ｎθ≔Ｅ³Ｘ²⊖⁺θιηＷ∨﹪Π…¹θθ⊙η﹪÷Ｘκθ⊖κ⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code.

Charcoal, 35 bytes

Ｎθ≔Ｘ²⁻Ｘθ³θηＷ∨﹪Π…¹θθ﹪÷Ｘηθ⊖η⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code. Uses @xnor's formulas (see @Sisyphus's answer), so slow for large inputs (seems to be OK up to \$ b = 27 \$ at least). Explanation:

Ｎθ

Input \$ n \$, which is initially equal to \$ b \$.

≔Ｘ²⁻Ｘθ³θη

Calculate \$ 2 ^ { b (b - 1) (b + 1) } \$ which is used in @xnor's GCD calculation.

Ｗ∨

While either...

﹪Π…¹θθ

... \$ n \$ does not divide \$ (n - 1)! \$, meaning that \$ n \$ is 4 or prime, or...

﹪÷Ｘηθ⊖η⊖Ｘ²θ

... \$ 2 ^ n - 1 \$ does not divide \$ \left \lfloor \frac { 2 ^ { n b (b - 1) (b + 1) } } { 2 ^ { b (b - 1) (b + 1) } - 1 } \right \rfloor \$, meaning that \$ n \$ is not coprime to all of \$ b - 1 \$, \$ b \$ and \$ b + 1 \$, ...

≦⊕θ

... increment \$ n \$.

Ｉθ

Output the final value of \$ n \$.

Much faster 38-byte version which performs separate coprimaility testing on \$ b - 1 \$, \$ b \$ and \$ b + 1 \$:

Ｎθ≔Ｅ³Ｘ²⊖⁺θιηＷ∨﹪Π…¹θθ⊙η﹪÷Ｘκθ⊖κ⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code.

Charcoal, 35 bytes

Ｎθ≔Ｘ²⁻Ｘθ³θηＷ∨﹪Π…¹θθ﹪÷Ｘηθ⊖η⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code. Uses @xnor's formulas (see @Bubbler's answer), so slow for large inputs (seems to be OK up to \$ b = 27 \$ at least). Explanation:

Ｎθ

Input \$ n \$, which is initially equal to \$ b \$.

≔Ｘ²⁻Ｘθ³θη

Calculate \$ 2 ^ { b (b - 1) (b + 1) } \$ which is used in @xnor's GCD calculation.

Ｗ∨

While either...

﹪Π…¹θθ

... \$ n \$ does not divide \$ (n - 1)! \$, meaning that \$ n \$ is 4 or prime, or...

﹪÷Ｘηθ⊖η⊖Ｘ²θ

... \$ 2 ^ n - 1 \$ does not divide \$ \left \lfloor \frac { 2 ^ { n b (b - 1) (b + 1) } } { 2 ^ { b (b - 1) (b + 1) } - 1 } \right \rfloor \$, meaning that \$ n \$ is not coprime to all of \$ b - 1 \$, \$ b \$ and \$ b + 1 \$, ...

≦⊕θ

... increment \$ n \$.

Ｉθ

Output the final value of \$ n \$.

Charcoal, 35 bytes

Ｎθ≔Ｘ²⁻Ｘθ³θηＷ∨﹪Π…¹θθ﹪÷Ｘηθ⊖η⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code. Uses @xnor's formulas (see @Bubbler's answer), so slow for large inputs (seems to be OK up to \$ b = 27 \$ at least). Explanation:

Ｎθ

Input \$ n \$, which is initially equal to \$ b \$.

≔Ｘ²⁻Ｘθ³θη

Calculate \$ 2 ^ { b (b - 1) (b + 1) } \$ which is used in @xnor's GCD calculation.

Ｗ∨

While either...

﹪Π…¹θθ

... \$ n \$ does not divide \$ (n - 1)! \$, meaning that \$ n \$ is 4 or prime, or...

﹪÷Ｘηθ⊖η⊖Ｘ²θ

... \$ 2 ^ n - 1 \$ does not divide \$ \left \lfloor \frac { 2 ^ { n b (b - 1) (b + 1) } } { 2 ^ { b (b - 1) (b + 1) } - 1 } \right \rfloor \$, meaning that \$ n \$ is not coprime to all of \$ b - 1 \$, \$ b \$ and \$ b + 1 \$, ...

≦⊕θ

... increment \$ n \$.

Ｉθ

Output the final value of \$ n \$.

Much faster 38-byte version which performs separate coprimaility testing on \$ b - 1 \$, \$ b \$ and \$ b + 1 \$:

Ｎθ≔Ｅ³Ｘ²⊖⁺θιηＷ∨﹪Π…¹θθ⊙η﹪÷Ｘκθ⊖κ⊖Ｘ²θ≦⊕θＩθ

Try it online! Link is to verbose version of code.