[Question]
  [
Figuring out whether a given number is prime, while not very complicated, is kind of hard. But making a guess doesn't need to be.
Seeing whether a number is a multiple of 2 or 5 is easy - you can just look at the last digit. Multiples of 3 isn't much harder, just add up the digits and see if you end up with a multiple of 3. Multiples of 11 are also easy enough, at least as long as they're fairly small. Any other number might not *be* prime, but at least they look like they *might* be prime. Or at least, that's how it works in base ten. As a person who frequently uses base ten, you can probably also identify the single-digit primes, and know that 11 is a prime as well.
We can generalize this to other bases. In some base \$b \ge 2\$, you can find fairly simple divisibility rules for any factor of \$b, b-1 \text{ or }b+1\$. You also presumably know all the prime numbers up to and including \$b+1\$.
But in any base, you eventually start running into numbers that *look* prime, but *aren't*. And I want to know when that happens. I know that in base 10, the first such number is 49 (not divisible by 2, 3, 5 or 11, but also not prime), in base 12 it's 25 (not divisible by 2, 3, 11 or 13), and in base 27, it's 55 (not divisible by 2, 3, 7 or 13, and unlike 25 it's also big enough to require two digits!). But for other bases? That's where you come in!
## Rules
Your task is to write a program or function which takes as input some integer \$b\ge2\$ and outputs the first integer which, when written in base \$b\$ *looks* like it might be prime, but *isn't*. That is to say, the smallest integer that
* Is a composite number and
* Is greater than \$b\$ and
* Is coprime with (does not share any prime factors with) \$b-1\$, \$b\$ and \$b+1\$
This is related to [OEIS A090092](https://oeis.org/A090092), but starts to diverge at \$b=27\$
This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so save those bytes!
## Test cases
```
Base -> Smallest pseudo-prime
2 -> 25
5 -> 49
6 -> 121
10 -> 49
12 -> 25
27 -> 55
32 -> 35
34 -> 169
37 -> 49
87 -> 91
88 -> 91
89 -> 91
121 -> 133
123 -> 125
209 -> 289
```
  
[Answer]
# [Haskell](https://www.haskell.org/), 53 bytes
```
f b=[x|x<-[b..],k<-[2..x-1],mod x k+gcd(b^3-b)x<2]!!0
```
[Try it online!](https://tio.run/##DYxLDoIwFEW38phBvG3aVxVIwB24gloTKqKEj0QddODea5N7kpMzuM/uM93nOcaBfGvDLzTCeikdpiQsZRDaYXn1FGjaPW597q9G@CI07LJMxaUbV2pp6bYz5RcvTtt7XL@5R7orCrKMA47QCprBJQzD7GFKVGkVqjp1nTBgVbv4Bw "Haskell – Try It Online")
[Answer]
# JavaScript (ES6), ~~91 83 79~~ 76 bytes
```
f=(b,n=b,k=n)=>(g=d=>k<2?d<n:k%d?g(d+1):b*~-b*~b%d&&g(d,k/=d))(2)?n:f(b,n+1)
```
[Try it online!](https://tio.run/##ddBLDoMgEAbgfU/hRgOtVgEfYETPIqKm1UBTmy57dWsj3UhYsOFjZv7h3r7bpXveHq9Iadmv68CBCBUX4cQV5DUYueT1VOFGVqqcfNmMQF4QLMX5E21H@DIItqtwirmEEGDYqHL4tdgerZ1Wi57766xHMADPwxB6cezh7HSUbJeUWZLvgjA6EkpcRcg5CBe7ZJYQU0NsSU2E3BpEClcEaoRZsSl1CnPItryJQIhF5P9Bx@A4Mf0wZesX "JavaScript (Node.js) – Try It Online")
### How?
Given the base \$b\$, we look for the smallest integer \$n\ge b\$ with a prime divisor \$d\$ which is neither \$n\$ itself nor a divisor of \$b-1\$, \$b\$ or \$b+1\$.
### Commented
```
f = (                  // f is a recursive function taking:
  b,                   //   b = input base
  n = b,               //   n = candidate number, starting at b
  k = n                //   k = copy of n
) => (                 //
  g = d =>             // g is a recursive function taking a divisor d
    k < 2 ?            // if k = 1:
      d < n            //   successful if d is smaller than n
    :                  // else:
      k % d ?          //   if d is not a divisor of k:
        g(d + 1)       //     do recursive calls with d + 1 until it is
      :                //   else:
        b * ~-b * ~b   //     if b(b - 1)(b + 1) ...
        % d &&         //     ... is not divisible by d:
          g(d, k /= d) //       do a recursive call with k divided by d
  )(2)                 // initial call to g with d = 2
  ?                    // if successful:
    n                  //   return n
  :                    // else:
    f(b, n + 1)        //   try again with n + 1
```
[Answer]
# [Gaia](https://github.com/splcurran/Gaia), ~~21~~ ~~20~~ 18 bytes
```
1⟨+:ṗ!¤@3*@⁻S&⟩#e+
```
[Try it online!](https://tio.run/##ASYA2f9nYWlh//8x4p@oKzrhuZchwqRAMypA4oG7Uybin6kjZSv//zIwOQ "Gaia – Try It Online")
-2 thanks to Arnauld!
```
1⟨	      ⟩#	% Find the first 1 positive integers n where:
  +:			% b + n
    ṗ!			% is not prime
	    S&		% and is coprime with
      ¤@3*@⁻		% b^3 - b, the product of b-1,b,b+1
		e+	% and return b + n
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), 13 bytes
```
ḟȯ≥3Λ`%-¹^3¹p
```
[Try it online!](https://tio.run/##AR8A4P9odXNr///huJ/Ir@KJpTPOm2AlLcK5XjPCuXD///82 "Husk – Try It Online")
## Explanation
```
ḟȯ≥3Λ`%-¹^3¹p   Input is a number b.
ḟ               Find first number ≥b that satisfies:
 ȯ              Composition of 3 functions:
                 Argument is a number n.
            p    1) Prime factors of n (with repetitions).
    Λ            2) All of them satisfy this:
           ¹      b
         ^3       cubed
       -¹         minus b
     `%           modulo the prime (is nonzero).
                  Λ returns either 0 or length+1.
  ≥3             3) Is at least 3.
                  This means n has at least 2 prime factors and none of them divide b^3-b = b*(b+1)*(b-1).
```
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 15 bytes
```
’r‘Ɗg’;Ẓ}E
ç@1#
```
[Try it online!](https://tio.run/##y0rNyan8//9Rw8yiRw0zjnWlA1nWD3dNqnXlOrzcwVD5////RgaWAA "Jelly – Try It Online")
## How it works
```
’r‘Ɗg’;Ẓ}E - Helper link. Takes b on the left and n on the right
   Ɗ       - Run the previous 3 commands over b:
’          -   Yield b-1
  ‘        -   Yield b+1
 r         -   Yield [b-1, b, b+1]
    g      - Take the GCD between each of these and n
     ’     - Decrement, yielding 0 for co-primes
       Ẓ}  - Is n prime?
      ;    - Concatenate to the list of decremented GCDs
         E - Are they all equal i.e. do they all equal 0?
ç@1# - Main link. Takes b on the left
  1# - Count up from b and return the first integer, n, which is true when: 
ç@   -   run through the helper link with b on the left and n on the right
```
[Answer]
# [Scala](http://www.scala-lang.org/), ~~97~~ ~~96~~ 91 bytes
```
b=>{def g(i:Int):Int=if(BigInt(b*b*b-b).gcd(i)>1|2.to(i-1).forall(i%_>0))g(i+1)else i
g(b)}
```
[Try it online!](https://tio.run/##Xc7NCsIwDADg@56iFyFRNtbNf9hAbx58Bmm3dkRKN1wRQX32OfEgGYUmX5M27Svl1NDqq6mCOCvywjyC8XUvDl33jO7KCbsXJx9EUf7CoIvyWRsrGqD9eILfrSALR2rGDPR8XLHGpKlqICzlK0tCCxRLTGx7U84BzS5lijg@sJBoXG8ERQ1ofA/djXxwHixkiNFfK6Y1k0w5@c1sw5jzar7k5M3bCbecu8lcOXHOP5J@@6P38AE "Scala – Try It Online")
* Thanks to [Sisyphus](https://codegolf.stackexchange.com/users/48931/sisyphus) for -1!
* Thanks to [user](https://codegolf.stackexchange.com/users/95792/user) for -5!
[Answer]
# [Husk](https://github.com/barbuz/Husk), ~~18~~ 17 bytes
```
ḟ(EM⌋m+¹ṡ1)fo¬ṗ↓N
```
[Try it online!](https://tio.run/##AScA2P9odXNr///huJ8oRU3ijIttK8K54bmhMSlmb8Ks4bmX4oaTTv///zI "Husk – Try It Online") or [Verify all test cases](https://tio.run/##yygtzv6f@6ip8f/DHfM1XH0f9XTnah/a@XDnQkPNtPxDax7unP6obbLf////o410THXMdAwNdAyNdIzMdYyNdIxNdIzNdSyAyELHwhIobgjExjpGBpaxAA "Husk – Try It Online")
-1 byte after rearranging stuff.
## Explanation
```
ḟ(EM⌋m+¹ṡ1)fo¬ṗ↓N
               ↓N drop first b elements from natural numbers.
           fo¬ṗ   filter out primes
ḟ                 get first element which satisfies the following:
 (        )       co-prime check
        ṡ1        range -1..1
     m+¹          add each to b
   M⌋             GCD of each and b
  E               are all equal?
```
[Answer]
# [Brachylog](https://github.com/JCumin/Brachylog), 22 16 bytes
*-6 thanks to Zgarb*
```
^₃;?-ḋF&<.ḋṀ;Fx×
```
[Try it online!](https://tio.run/##SypKTM6ozMlPN/pfXa6koGunoFSu9qhtw6Ompoe7Omsfbp3wP@5RU7O1ve7DHd1uajZ6QOrhzgZrt4rD0///jzbSMdUx0zE00DE00jEy1zE20jE20TE217EAIgsdC0uguCEQG@sYGVjGAgA "Brachylog – Try It Online")
* `^₃;?-ḋF`: all the prime factors of `B^3-B`
* `&<.`: the output `N` is greater than `B`
* `ḋṀ`: `N`'s prime factors are at least 2
* `;Fx×`: and the product of the prime factors without the ones in `F` unifies with the output `N`.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 13 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
’r‘²Pg€ƊỤẒÞḊḢ
```
A monadic Link accepting an integer, \$b\$, which yields the first integer that "looks prime but isn't".
**[Try it online!](https://tio.run/##ASoA1f9qZWxsef//4oCZcuKAmMKyUGfigqzGiuG7pOG6ksOe4biK4bii////MTA "Jelly – Try It Online")** (Too inefficient for even quite small inputs due to golfing.)
### How?
This is really just a golfed version of this 15 byter which is not so ridiculously inefficient: `’r‘ṀÆn²g€ƲỤẒÞḊḢ`.
```
’r‘²Pg€ƊỤẒÞḊḢ - Link: b
’             - decrement -> b-1
  ‘           - increment -> b+1
 r            - inclusive range -> [b-1, b, b+1]
       Ɗ      - last three links as a monad:
   ²          -   square -> [(b-1)², b², (b+1)²]
    P         -   product -> (b(b-1)(b+1))²
                  (this is always greater than ṀÆn²
                     - the square of the next prime above b+1
                   and saves us two precious bytes)
      €       -   for each (v in [1..(b(b-1)(b+1))²]:
     g        -     greatest-common-divisor (between v and each of [b-1, b, b+1])
        Ụ     - grade-up -> 1-based indices sorted by the values at those positions
          Þ   - sort by:
         Ẓ    -   is prime?
           Ḋ  - dequeue (since 1 gets GCDs [1,1,1] so it also looks prime and isn't prime)
            Ḣ - head -> the smallest number that looks prime and isn't prime
```
[Answer]
# [Python 3.8](https://docs.python.org/3.8/), ~~115~~ ~~98~~ 89 bytes
Saved a whopping 17 bytes thanks to the man himself [Arnauld](https://codegolf.stackexchange.com/users/58563/arnauld)!!!
```
f=lambda b,m=9:(m>b)*(perm(m-1)**2%m!=1)*m*(gcd(b**3-b,m)<2)or f(b,m+1)
from math import*
```
[Try it online!](https://tio.run/##NU7LboQwDLzzFe6hIkmNtElggVXZH2l74BF2kRqIQiq1RXw7NbS1bHnG9sjjvsJ9GnXh/Lb11Xttm66GBm1VXpi9NlwwZ7xlNpFcCPVoHyoCVrBb27FGCJ3QLX9WfPLQM8JPkke9nyzYOtxhsG7yQWzBzGGGCpjCDM8oTygVqhy1Qp2izrGgLLAoaS6pNKpTySPz6UwbTHcoM0x/19SIZBnqDOW53Hkp/1JqTTcZqoLkftfFrx8qT9sYDiB1TP7IbEADwwjfg2OHOfz/xS8RUOxuexb4QZwfxsD6eAkrJFdY5hUW/2Kqan5bY779AA "Python 3.8 (pre-release) – Try It Online")
### Explanation
```
f=lambda  b                       # recursive function taking b  
           ,m=9                   # init possible answer to largest single  
                                  # digit (of which none of them can be  
                                  # the solution because they're either  
                                  # prime or divisible by 2 or 3)  
               :                  # the start of a chain of logical  
                                  # tests, if any of them are False the  
                                  # chain will be 0 invoking recursion  
    (m>b)*                        # first one makes sure m is >= b + 1  
      (perm(m-1)**2%m!=1)*        # second tests that m isn't prime using  
                                  # one of xnor's tricks 
        *(math.gcd(b**3-b,m)<2)   # third tests that m is coprime with  
                                  # (b - 1)*b*(b + 1) == b**3 - b  
            *m                    # if all this is True return m  
               or f(b,m+1)        # otherwise try m + 1
```
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 16 [bytes](https://en.wikipedia.org/wiki/ISO/IEC_8859-1)
```
@Jõ+U ejX «Xj}aU
```
[Try it](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QEr1K1UgZWpYIKtYan1hVQ&input=MjA5) or [run all test cases](https://petershaggynoble.github.io/Japt-Interpreter/?v=1.4.6&code=QEr1K1UgZWpYIKtYan1hVQ&footer=V2dWIHMg%2bTMgKyIgPSAiK1VzIPkz&input=WzIgNSA2IDEwIDEyIDI3IDMyIDM0IDM3IDg3IDg4IDg5IDEyMSAxMjMgMjA5XS1tUg)
```
@Jõ+U ejX «Xj}aU     :Implicit input of integer U
@                    :Function taking an integer X as argument
 J                   :  -1
  õ                  :  Range [-1,1]
   +U                :  Add U to each
      e              :  All
       jX            :    Co-prime with X
          «          :  Logical AND with the boolean negation of
           Xj        :  Is X prime?
             }       :End function
              aU     :Starting from U, get the first X that returns true
```
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 58 bytes
```
.+
$*11¶$&$*
+`^(11+)\1*1?1?¶\1+$|¶(?!(11+)\2+$)
$&1
r`1\G
```
[Try it online!](https://tio.run/##JcixCcMwFEXR/m0R@DayBMbvK4nlSqWXEEEpUqRJYVJ6Lg2gxRRB4N7mHK/v@/Nsg9lzmx3EkrXIKBYuPwzppkTLyFhLopOzFhMvf1cnE2Qkjsy0t6a44Q4uoEJXeIW/wq8IvYCwdWffQ5ftBw "Retina 0.8.2 – Try It Online") Link includes test cases. Explanation:
```
.+
$*11¶$&$*
```
Convert `b` to unary, and make a copy as `b+1`, which will be used for GCD testing.
```
+`^(11+)\1*1?1?¶\1+$|¶(?!(11+)\2+$)
$&1
```
Keep incrementing the result while it's prime or shares a common factor with either `b+1`, `b` or `b-1`.
```
r`1\G
```
Convert the result back to decimal.
[Answer]
# [Stax](https://github.com/tomtheisen/stax), 12 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)
```
öα•○¼¿¼╓♫├û•
```
[Run and debug it](https://staxlang.xyz/#p=94e00709aca8acd60ec39607&i=2%0A5%0A6%0A10%0A12%0A27%0A32%0A34%0A37%0A87%0A88%0A89%0A121%0A123%0A209&a=1&m=2)
[Answer]
# [C (gcc)](https://gcc.gnu.org/), ~~87~~ ~~86~~ 84 bytes
Saved a byte thanks to the man himself [Arnauld](https://codegolf.stackexchange.com/users/58563/arnauld)!!!
```
i;q;p;m;f(b){for(p=m=b;p|!q;++m)for(q=p=i=1;++i<m;)q=m%i<1?p=0,q&&b*~-b*~b%i:q;--m;}
```
[Try it online!](https://tio.run/##bVFdb4IwFH33V3QkGKqXjFKrsNrtYdmvUB8EYWuyIl9ZyBz76@wiqFuypjfl3J5z2h5i9zWOu07LQubSyNSJ6Ck9lk6ujIpk/nVXyPnc0L5VqFxpxRDrtZG0UMbWa/aUKw@K6TSafbtYka0fCum6Rradzmpi9jpz6OQ0ITj6Rp1UdbXZEUVOPghYAvOA@eCvgPvAF8BXEOAMIAixz7A4@F7YyqtD0uRJXCeH0UTAYmDigkAI4ALYMuxxyMbJOEeOAD@4OMVv@3JGysHE2jYv/rYJn7GEBeQ35taowAyI019AZ4ekQZknx881qfRnckyd8@Po/YhmA5QEE@t5lAwxXB5CIjQZ8jjv7@R1Oy@RkDqWfSDuI8EbRVT@0ZZJ/bF/R33/x/7V2dU2Q@FAxHVzkahbgsOxu9GgnbTdDw "C (gcc) – Try It Online")
Port of my [Python answer](https://codegolf.stackexchange.com/a/213463/9481).
[Answer]
# [Python 3](https://docs.python.org/3/), 81 bytes
```
f=lambda b,k=1,p=1:(k<b)|p%k|math.gcd(b**3-b,k)-1and f(b,k+1,p*k)or k
import math
```
[Try it online!](https://tio.run/##FY3PDoMgDIfP8yl6WQKsLiL7o2Y@ybIDjDgJE4nhssR3Z@Xwtb@2X9L4S/MaVM7T@NWLsRoM@lFiHOXA/MPwPR79vug0nz9vy4wQqiaD11IHCxOjfCJbeL5u4Cu3xHVLUPw80caAC/BsEa4INwTZEDS1dwRFXV0Iyl2hI/pyl6Uospr@NVSHuLmQGL3iPP8B "Python 3 – Try It Online")
---
Uses [xnor's corollary to Wilson's theorem](https://codegolf.stackexchange.com/a/27022/48931). I still find it unbelievable that the shortest way to test for coprimality is `import math;math.gcd(x,y)<2`, but I couldn't find a shorter way.
-2 due to xnor, since we only need the regular factorial here (instead of factorial squared). The special case `k=4` is taken care of by the other conditions.
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~15~~ 14 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
∞+.ΔαD3mαy¿yp+
```
Inspired by [*@Giuseppe*'s Gaia answer](https://codegolf.stackexchange.com/a/213469/52210), so make sure to upvote him as well!
[Try it online](https://tio.run/##yy9OTMpM/f//Ucc8bb1zU85tdDHOPbex8tD@ygLt//@NAA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfeWhlf8fdczT1js35dC6cxtdjHPPbaw8tL@yQPt/rc7/aCMdUx0zHUMDHUMjHSNzHWMjHWMTHWNzHQsgstCxsASKGwKxsY6RgWUsAA).
**Explanation:**
```
∞            # Push an infinite positive list: [1,2,3,...]
 +           # Add the (implicit) input `n` to each: [n+1,n+2,n+3,...]
  .Δ         # Find the first `n+b` which is truthy for:
    α        #  Take the absolute difference with the (implicit) input: [1,2,3,...]
     D       #  Duplicate this `b`
      3m     #  Cube it: b³
        α    #  Take the absolute difference with the `b` we've duplicated: |b-b³|
         y¿  #  Get the greatest common divisor with the current `b+n`: gcd(|b-b³|,b+n)
    yp       #  Check whether `b+n` is a prime number (1 if prime; 0 if not)
    +        #  Add them together: gcd(|b-b³|,b+n)+isPrime(b+n)
             #  (NOTE: only 1 is truthy in 05AB1E)
             # (after which the result is output implicitly as result)
```
[Answer]
# [R](https://www.r-project.org/), ~~100~~ ~~81~~ ~~73~~ 72 bytes
*Edit1: -19 bytes by abandoning the nice all-in-one check-for-primality-and-shared-divisors, and instead using clunkier but shorter separate checks*
*Edit2: -8 bytes, and then -1 more byte thanks to Giuseppe*
```
f=function(b,n=b)`if`(sum(a<-!n%%2:n)>1&all(!a|(b^3-b)%%2:n),n,f(b,n+1))
```
[Try it online!](https://tio.run/##hdDLCoMwEAXQfb9CKZaEKpjER1Kqn1IfrQFBoxjd9d@tpaYrh2zDmTs3M626r7qu0XMx6mZ5DcU4tX2TrTKTi3rO7aBQ7ausxmUrS6SXHlX3wFWeR28K5@SyDSO3eqP6wYIa/5595cvv1JVgfJyPKHbOTpA7ND4dg3gHkQBAsgNCCSBIaMsg1ho03UUMCWYyGCgiUzWBirDUVpUbIaDvcm4Vwia2Y5qujIGG/U8Pni00qygX6wc "R – Try It Online")
Sadly, although checking for primality by counting divisors and checking for **co**-primality by counting **shared** divisors could be elegantly combined, the ugly code below is actually (quite a bit) shorter...
Thanks to Giuseppe for ruthlessly pruning all the unneccessary variables, parentheses, square-brackets and so on...
**How?** (code before golfing by Giuseppe)
```
f=function(b,               # f is recursive function taking argument b (=base)
  n=b,                      # n is number to test for pseudo-primeness; start at b
  a=!n%%2:n,                # a is zero-values of n MOD 2..n = divisors (excluding 1)
  c=!(b^3-b)%%2:n           # c is zero-values of (b-1).b.(b+1) MOD 2..n = divisors of b-1, b or b+1
)
`if`(                       # Now, check whether:
(sum(a)>1)                  #   a is not prime (if it has >1 divisor including itself)
  &!sum(c[a]),              #   and it has no shared divisors with b-1, b or b+1
  n,                        # If both are Ok, then n is a pseudo-prime: return it
  f(b,n+1)                  # otherwise, do recursive call with n+1
)                                   
```
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), 35 bytes
```
Ｎθ≔Ｘ²⁻Ｘθ³θηＷ∨﹪Π…¹θθ﹪÷Ｘηθ⊖η⊖Ｘ²θ≦⊕θＩθ
```
[Try it online!](https://tio.run/##XU@7DoMwDNz5ioyORIfSoQNTVRYGWtQ/SENEIgWHvODz01SNGGrJtnx3Op25ZI4bplPqcY3hEZe3cGBpW928VzPCaPYMNDUZFEZfTluTC62JpXnIrN2l0oLA08FgpqgNjC5vHuDFcBZwLlKbuwh6DJ3a1CSKo/yxneBOLAKDmEDSP@CIks1ykYGtJWSPh@rLttXoFAa4Mx/yL7RNqbmm06Y/ "Charcoal – 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!](https://tio.run/##XY/PCoMwDMbve4oeU@hgc6fhSebFg5vsDbpatFhb@0dlT9/VKTIWCCHJL3xfWEst01SGUKhh9Pexf3ELBqeHzDnRKCjpABeCKj3HeUJQzpnlPVee11DJ0YEhSOAYBLXxam6F5AgeFkpdj1JDZWNlHp5UNRzOBJkFNTEz9YaWoI0rlM/FJGoOq1S3Qr9y3V@/ezL4Gyh63VwXaseWdXqorFAebtT5@BxOQ0hO13Cc5Ac "Charcoal – Try It Online") Link is to verbose version of code.
[Answer]
# [Python 3](https://docs.python.org/3/), ~~145~~ ~~143~~ 137 bytes
```
from math import*
p=lambda b,h=2,c=inf:h>c and c or p(b,h+1,([h*i for i in range(2,h+1)if 2>gcd(h*i,b**3-b)and h*i<c and b<h*i]or[c])[0])
```
[Try it online!](https://tio.run/##XZDLbsMgEEXX9VeMvAKXVgbysKM4P@Kiyq8EpBgjh0iNony7O8RtWmVxYebM1UWDu3g9WDlNpnfD6KGvvI5ccaz6uq2gZroQrCnSjd41UNkWGhhGcAQHr5yRUicG9kgMGAtjZQ8dEWFEzR7ELoS9H5qWoI3VSSLfahpCsN2Se5JOEn1H9RahGsayUbRMFZ2MdWd/ggJKwWDJYMWApyjsxJqBxFsuUFhnQRkqD3MeDomuNFdR9@W6xnft53D2jzxMW/xaQxHAEiVRfJXPMOd/4lIGO45FhqGnS18Px3tW/HEWa57FDOZqEasoevqQY2fJvA2lm@jFjcZ6so@vMyuNum3g6sijpTe4/jxR/sdQFPC8D3J1i@n0DQ "Python 3 – Try It Online")
* -2 bytes by reformatting the condition in the list comprehension and removing an unnecessary space.
* -6 bytes from removing a special case when `c` is `0` by making it default to `math.inf` instead
Wanted to test how a solution that doesn't involve prime checking might fare, just out of curiosity. Worse than the competition, it seems. Oh well, at least I had fun.
Works by generating all composite numbers. On each pass, we generate some numbers that are definitely composite, then update our best guess (which we'll call \$x\$) to be the smallest number we find that's between \$b\$ and \$x\$ and also coprime with \$b^3 - b\$ - if we didn't end up generating a number like that, we keep our existing \$x\$. Eventually we reach a point where we know we'll no longer generate any numbers that are below our current \$x\$, which means \$x\$ must be the correct answer.
## Ungolfed
```
from math import gcd, inf
def pseudoprime(base, high=2, candidate=inf):
    if high > candidate:
        # We can no longer find anything that's small enough to care about
        return candidate
    else:
        valid_multiples = [high * i for i in range(2, high+1) if # Generate all multiples of "high", then filter them
            base < high * i and # Exclude single-digit numbers
            math.gcd(high * i, base ** 3 - base) < 2 and # Check for coprimality
            high * i < candidate # Make sure it's not bigger than our best guess, assuming we've found one
        ]
        if valid_multiples:
            return pseudoprime(base, high + 1, valid_multiples[0])
        else:
            return pseudoprime(base, high + 1, candidate)
```
[Answer]
# Java 8, ~~106~~ ~~105~~ ~~104~~ 100 bytes
```
n->{for(int b=0,p,g,i;;){for(g=p=++n;n%--p>0;);for(i=++b*b*b-b;i>0;)i=g%(g=i);if(p>1&g<2)return n;}}
```
-1 byte thanks to *@ceilingcat*.
[Try it online.](https://tio.run/##PZDNboMwEITveYpVpFS4LIiftiFx4dJzc8kxzcEQg5ySBYFJVSGenRqSVF6vtJ9GO2OfxVU459P3mJWibeFTKOoXAIq0bHKRSdhN4wwgs6ZOjBsyLExrtdAqgx0QxDCSk/R51cyiNPawxgIV52yGRVzHtk2cVo5TJx5nfJYalj6b46RcTVTFxcpoFeMqt@rEfyreA9ZI3TUExIdh5JNv3aWl8b3bXyt1gosJbu11o6g4HEGwW@pHHC1b/SFaCVsg@TM95nDsA3zFN/Q99AMM1hgGGL5guMbIVITRxnDf3BADbzOweR/A/rfV8uJWnXZrY6ZLsh7L7eX2Sy9tcrN/xO5/NYx/)
**Explanation:**
```
n->{                 // Method with integer as both parameter and return-type
  for(int b=0,       //  Start integer `b` at 0
          p,         //  Temp-integer to check for primes
          g,i;       //  Temp-integers to check for the gcd
      ;){            //  Loop indefinitely:
    for(g=p=++n;     //   Increase n by 1 first with `++n`
                     //   And then set both g and p to this new n
        n%--p>0;);   //   Decrease p by 1 before every iteration with `--p`
                     //   and continue looping as long as n is NOT divisible by p
    for(i=++b*b*b-b; //   Then increase b by 1 first with `++b`
                     //   And set i to b³-b
        i>0;)        //   Loop as long as i is still positive:
      i=g%(g=i);     //    First set g to i
                     //    And then set i to old_g modulo-new_g
    if(p>1           //   If `p` is larger than 1 (this means it's NOT a prime)
       &g<2)         //   and the greatest common divisor is 1:
      return n;}}    //    Return the modified n as result
```
]