M = 2,4,5,10是明显的。对于M = 3，这里有一些有趣的见解：Regex filter numbers divisible by 3
任何人都可以为M = 7,9,11,13等提供解决方案？一般的？
测试代码(在python，但随意使用任何语言)：
M = your number,e.g. 2
R = your regexp,e.g.,'^[0-9]*[02468]$'
import re
for i in range(1,2000):
m = re.match(R,str(i))
if i % M:
assert not m,'%d should not match' % i
else:
assert m,'%d must match' % i
对于那些好奇的人来说，这里是一个M = 3的例子(假设引擎有递归支持)：
^
(
| [0369]+ (?1)
| [147] (?1) [258] (?1)
| [258] (?1) [147] (?1)
| ( [258] (?1) ) {3}
| ( [147] (?1) ) {3}
)
$
更新：有关更多的讨论和示例，请参阅这个thread.发布的表达式是错误的(在70 * N失败)，但“如何到达”部分是非常有教育意义的。
存在结果来自deterministic finite automata(DFA)和正则表达式之间的对应关系。所以我们来做一个DFA。将模数表示为N(不需要为素数)，用B表示数字，对于普通十进制数表示10。 N个状态的DFA标记为0到N-1。初始状态为0. DFA的符号为数字0到B-1。状态表示输入字符串的左前缀的剩余部分，当被除以N时被解释为整数。边缘表示当向右添加数位时状态的变化。算术地，这是状态图S(状态，数字)= B *状态位(模N)。接受状态为0，因为零余数表示可分割性。所以我们有一个DFA。 DFA识别的语言与正则表达式识别的语言相同，因此存在。所以虽然这很有趣，但没有帮助，因为它并没有告诉你如何确定表达式。
如果你想要一个通用的算法，在运行时很容易构建这样一个DFA，并通过直接的计算来填充它的状态表。初始化只是一对具有运行时间O(M * N)的嵌套循环。机器识别是每个输入字符的恒定时间。这是非常快的，但不使用正则表达式库，如果这是你真正需要的。
在实际的正则表达式中，我们需要看看Fermat’s Little Theorem.从定理我们知道B ^(N-1)== 1(模N)。例如，当N = 7和B = 10时，这意味着6位数的每个块相当于0 .. 6范围内的一个数字，用于可分割性。指数可以小于N-1;一般来说，它是07的Euler totient function的因素。调用块D的大小。对于D数组的块，有N个正则表达式，每个表示一个特定的等价类，余数为模N。最多，这些表达式具有长度为O (B ^ D)，这是很大的。对于N = 7，这是一组百万个字符的正则表达式;我可以想象会破坏大部分的regexp库。
这涉及到示例代码中的表达式如何工作;表达式(？1)是等于0(mod 3)的匹配字符串。这与N = 3一起工作，因为10 ^ 1 == 1(mod 3)，这意味着A0B == AB(mod 3)。当指数大于1时，这更复杂，但原理是相同的。 (注意，示例代码严格地使用不仅仅是正则表达式的识别器。)表达式[0173]，[147]和[258]是数字0,1和2中的正则表达式，其中模3表达。概括来说，您将以类似的方式使用上述的正则表达式数字。
我没有提供代码，因为(1)比这个答案需要更长的时间，(2)我真的怀疑它会在任何已知的实现中执行。
