Return to Answer

This was inspired by the algorithm used by Bubbler's APL answer. The full prime power version of that would be:
^(?!((x+)(?=2円+$)x+)(?!1円*2円+$)1円+$) - ECMAScript, 36 bytes
^(?!((x+)x+)\B(?>1円*?(?<=^2円+))$) - .NET, 33 bytes
^(?!((x+)+)\B(?>1円*?(?<=^2円+))$) - .NET, 32 bytes, 🐌 exponential slowdown

This is interesting because if I'd set out to implement that function intentionally, I would have come up with something like ^(?=(x?x+?)1円*$)((?=(x+)(3円+$))4円)?1円$ (38 bytes), which is 10 bytes longer.

It was inspired by the algorithm used by Bubbler's APL answer. The full prime power version of that would be:
^(?!((x+)(?=2円+$)x+)(?!1円*2円+$)1円+$) - ECMAScript, 36 bytes
^(?!((x+)x+)\B(?>1円*?(?<=^2円+))$) - .NET, 33 bytes
^(?!((x+)+)\B(?>1円*?(?<=^2円+))$) - .NET, 32 bytes, 🐌 exponential slowdown

-2 bytes thanks to H.PWiz; the explanation for why this worked was more complicated
-1 bytes by returning to the original algorithm (with its simple explanation), by a different angle (slower than its 35 byte version, but not exponentially so)

-2 bytes thanks to H.PWiz; the explanation for why this worked was more complicated
-1 bytes by returning to the original algorithm (with its simple explanation), by actually constructing values of \$a\$ not divisible by \$b\$ (32 bytes) instead of asserting \$a\$ is not divisible by \$b\$ (35 bytes); this is slower, but not exponentially so

-2 bytes thanks to H.PWiz
-1 bytes by returning to the original algorithm, by a different angle (slower, but not exponentially so)

-2 bytes thanks to H.PWiz; the explanation for why this worked was more complicated
-1 bytes by returning to the original algorithm (with its simple explanation), by a different angle (slower than its 35 byte version, but not exponentially so)