Regex for divisibility by 123 in binary strings
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$.