Regex for divisibility by 123 in binary strings Is there a regex that checks for divisibility by 123 in binary strings?
This question can be found in the Algorithms’ textbook by Sedgewick and Wayne official website (question 7b in the Creative Exercises section).
Creating a regex to check if a binary string is divisible by 3 is simple: (0|1(01*0)*1) *
A regex to check if a binary string is divisible by 2 is also simple: (0|1)*0
And there are many questions on the Internet asking for a regex for divisibility by 7.
However, I could not find any resources related to a regex for checking if a binary string is divisible by 123.
These are the representations of some multiples of 123 in binary:

0 = 0
123 = 1111011
246 = 11110110
369 = 101110001
492 = 111101100
615 = 1001100111
738 = 1011100010
861 = 1101011101
984 = 1111011000
1107 = 10001010011
1230 = 10011001110

There doesn’t seem to be a pattern that stands out (even though there is probably one, since the question to check 123-divisibility with a regex exists).
There are, however, some similarities in some strings:
123, 246, 492 and 984 in binary are basically the same, but 246 has an extra 0 in the end, 492 has two extra 0s in the end and 984 has three extra 0s in the end.
369 and 738 in binary are basically the same, but 738 has an extra 0 in the end.
615 and 1230 in binary are basically the same, but 1230 has an extra 0 in the end.
Any ideas for a regular expression for such strings? Thanks!
Here is a way that succeeds, albeit with a lot of work.

First, construct a DFA for the language. That is actually quite simple: It has states $0$ through $122$ (for the remainders), start state and only accepting state is $0$, the transitions from state $n$ go to $(2n \mod 123)$ for label $0$ and to $(2n+1 \mod 123)$ for label $1$.

Now, convert that DFA to a regular expression. The result is not likely to be simple, small or nice.

If you use an extension to regular expressions that allows intersection, you can also do the above with $41$ instead of $123$ and then intersect with the expression you have for divisibility by $3$.