A couple well known rules for divisibility exist, let us start with the smaller one:
Divisibility by 3: A number is divisible by 3 if and only if it's digit sum is divisible by 3.
Divisibility by 5: A number is divisible by 5 if and only if it's last digit is either 0 or 5.
It seems what we need so far is some framework (at least be) able to
- pick out single digits and
- to calculate sums
- iterate on all resulting numbers $\mathbb Z \backslash \{0,1,\cdots,9\}$
- compare to a base case (set of integers $\subset \{0,1,\cdots,9\}$)
Multiplying with a vector $\bf v$ can achieve this. Summing the elements of a vector corresponds to scalar product with vector full of ones. Picking out last element corresponds to scalar product with vector $[0,\cdots,0,1]^T$.
Now to the tricky part. Can we mathematically prove that such a scalar product vector $v$ and set of end-up numbers $\mathcal S$ must exist for any divisor $ d\in \mathbb Z$?
Own work
- Case $d=5, {\bf v}=[0,1]^T, \mathcal S = \{0,5\}$, for the subset $\{0,1,\cdots,99\}$
- Case $d=7, {\bf v}=[3,1]^T, \mathcal S = \{7\}$, for the subset $\{0,1,\cdots,99\}$
- Case $d=11, {\bf v}=[1,-1]^T, \mathcal S = \{0\}$, for the subset $\{0,1,\cdots,99\}$