Here’s that proof I promised at the end of class on Monday. Read through it line by and line and see if you can follow it. Let me know if you have any questions.

Theorem: If a decimation cipher multiplier is NOT relatively prime to the alphabet length (that is, if it has a prime factor in common), then it produces an unusable cipher alphabet.

Proof: (in the case where the alphabet has length 26)

  • Suppose d has a prime factor p in common with 26 (either 2 or 13).
  • Let x be a number between 0 and 25, representing a letter in the plain text alphabet.
  • Then xd must be divisible by p, since d is divisible by p.
  • Dividing 26 into xd yields xd =26q + r for some quotient q and remainder r, where r is between 0 and 25.
  • Then r = 26q – xd, which is divisible by p since p is a factor of 26 (and thus of 26q) and of xd.
  • Thus xd MOD 26 is a number between 0 and 25 that is divisible by p. There aren’t 26 such numbers, so we’re guaranteed to get repeats in the cipher alphabet.

Note that we could make the same argument for other alphabet lengths.

This theorem allows us to rule out 2, 4, 6, 8, 10, 12, 13, 14, 16, 18, 20, 22, and 24 as usable decimation cipher multipliers. That leaves 11 possible multipliers: 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25. We can verify experimentally that all of these work, or we could prove the following conjecture.

Conjecture: If a decimation cipher factor is relatively prime to the alphabet length (that is, if it has no prime factors in common), then it produces a usable cipher alphabet.

I can’t call this a theorem until we’ve proved it! I haven’t proved it yet, but I suspect that it’s true.