ISO/IEC 7064:2003 defines so-called pure check digit systems. The term “pure” refers to only requiring one modulus as opposed to two moduli (p. 2).
A character string satisfies the check of a pure check digit system when:
$\sum\limits_{i=1}^n s_i \cdot r^{i-1}\equiv 1\pmod{M}$, where $s$ is the string of digits, $s_i$ is the digit at the $i$-th position, $n$ is the length of the string $s$, $r$ is the radix, and $M$ is the modulus (p. 3). The first digit of $s$ (that is, $s_1$) is the check digit.
In annex B (p. 12), the standard provides guidance on how to construct check digit systems for other alphabets. In particular, it examines a check digit system for the Danish 29 letter alphabet. It reads:
Since 29 is a prime number, and since 2 has the property that the smallest positive integer $a$ for which $2^a\equiv1\pmod{29}$ is $28~(=29-1)$, a pure system can be used with 29 as the modulus and 2 as the radix.
Since $M=29$ is prime, any integer raised to the $M-1$th power is congruent to 1 modulo $M$.
With this in mind, I would like to ask:
- For any integer $M$ that is not an odd prime, is it certain that the equation $2^a\equiv1\pmod{M}$ has a solution $a$ such that $0\le a<M$?
- Given a non-prime $M$, is the check digit system still meaningful? In particular, can single substitution errors still be reliably detected?