Product of Vigenère ciphers is not a Vigenère cipher with length of LCM I have always thought that using two Vigenère ciphers leads to another Vigenère cipher with key length of LCM (least common multiple) of the two previous Vigenère ciphers. But I have stumbled upon this problem:


  Let $\mathcal{V}_1,\mathcal{V}_2, \mathcal{V}_3$ be Vigenère ciphers with key length $l_1, l_2\in\mathbb{N}$ and LCM$(l_1,l_2)$. Prove that for some $l_1, l_2\in\mathbb{N}$ is not $\mathcal{V}_1\times\mathcal{V}_2\approx\mathcal{V}_3$.


I have tried with some lengths but it worked so that the product was Vigenère with length of LCM. Would you give me example of lengths for which it doesn't work?
I have tried with some lengths but it worked so that the product was Vigenère with length of LCM.


Actually, the statement really isn't "is encrypting with cipher $\mathcal{V}_1$ and the cipher $\mathcal{V}_2$ always equivalent to some cipher $\mathcal{V}_3$.

Instead, it's "are the set of transforms that you can express by first encrypting by some transform (I'll say key, even those the members in the set are technically transforms and not keys) in $\mathcal{V}_1$ and then by some key in $\mathcal{V}_2$ precisely the same as the set of transforms you can reach by encrypting by some key in $\mathcal{V}_3$."

Expressed that way, it should be obvious that, for some lengths $l_1, l_2, LCM(l_1, l_2)$ there are keys in $\mathcal{V}_3$ that cannot be reached by $\mathcal{V}_1$ followed by $\mathcal{V}_2$

To take a simple example, if $l_1 = 2$, $l_2 = 3$ and we're doing Vigenère in base 26.  In this case, the total number of transforms that can be expressed by $\mathcal{V}_1$ and $\mathcal{V}_2$ is at most $26^2 \times 26^3 = 26^5$ (and it's actually less than that).  However $\mathcal{V}_3$ contains $26^6$ transforms, hence there must be quite a number that are not reachable via $\mathcal{V}_1$ and $\mathcal{V}_2$