title: Check number divisibility with regular expressions
body: <p>Given a decimal number <code>N</code> as a string of digits, how do I check if it's divisible by <code>M</code> <strong>using regular expressions only</strong>, without converting to int?</p>
  
  <p>M=2, 4, 5, 10 are obvious. For M=3 some interesting insights here: <a href="https://stackoverflow.com/questions/10992279/python-regex-filter-numbers-divisible-by-3">Regex filter numbers divisible by 3</a></p>
  
  <p>Can anyone provide a solution for M=7, 9, 11, 13 etc? A generic one? </p>
  
  <p>Testing code (in python, but feel free to use any language):</p>
  
  <pre><code>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
  </code></pre>
  
  <p>For those curious, here's an example for <code>M=3</code> (assumes an engine with recursion support):</p>
  
  <pre><code>^
  (
      | [0369]+ (?1)
      | [147] (?1) [258] (?1)
      | [258] (?1) [147] (?1)
      | ( [258] (?1) ) {3}
      | ( [147] (?1) ) {3}
  )
  $
  </code></pre>
  
  <p>Upd: for more discussion and examples see this <a href="https://codegolf.stackexchange.com/q/3503">thread</a>. The expression posted there turned out to be buggy (fails on 70*N), but "how to get there" part is very educative.</p>