# Cryptogram

A *cryptogram* is a mathematical puzzle, where various symbols are used to represent digits, and a given system has to be true. The most common form is a mathematical equation (as shown below), but sometimes there can be multiple equations or statements. Solving a cryptogram by hand usually involves a mix of logical deduction and exhaustive tests of remaining possibilities. Furthermore, keep in mind that a cryptogram could have no solutions, one unique solution, or even numerous solutions.

We will explore various techniques for tackling cryptograms, which provides you with a complete arsenal to solve cryptograms such as

\[ \large{\begin{array}{ccccccc} && & & S& E & N&D\\ +&& & & M& O & R&E\\ \hline & & & M & O& N & E&Y\\ \hline \end{array}} \]

For simplicity and consistency, we will assume the following:

- Each symbol represents a distinct single non-negative digit.
- All leading digits are non-zero unless stated otherwise.
- We read columns from the rightmost, so the units column is the first.

## Algebraic Techniques

### 1) Converting cryptogram to equation

We will be applying some properties of simple equations for cryptogram. If you are not familiar with that concept, please see the main article first, Simple Equations.

\[ \begin{array}{ccccc} & & & 1 & 1&1\\ + & & & 1 & \bigtriangleup &\square \\ \hline & & & 2 & \square &4\\ \hline \end{array} \]

To solve the above cryptogram for \( \bigtriangleup \) and \(\square,\) we can interpret it as the sum of two integers. That is, \(111 + \overline{1 \bigtriangleup \square} = \overline{2\square4} \) or \(111 + 100 + (10 \bigtriangleup ) +\square = 200 + 10 \square+ 4 \). This gives \(7 + 10 \bigtriangleup = 9 \square\). We can check individually and find that \(\square = 3, \bigtriangleup = 2\) gives a solution.

\[ \begin{array}{ccccc} & & & 1 &\lozenge &1\\ + & & & \lozenge & 0 &\lozenge \\ \hline & & & 8 & \lozenge &8\\ \hline \end{array} \]

## Find the value that represents the symbol \(\lozenge \).

Converting the cryptogram to an equation gives \( \overline{1 \lozenge 1} + \overline{\lozenge 0 \lozenge } = \overline{8 \lozenge 8} \).

We then convert each of these 3-digit integers to an algebraic expression:

\[\begin{eqnarray} \overline{1 \lozenge 1} &=& 100 + 10 \lozenge + 1 \\ \overline{\lozenge 0 \lozenge} &= &100\lozenge + 10(0) +\lozenge \\ \overline{8 \lozenge 8} &=& 800 + 10\lozenge + 8. \end{eqnarray} \]

Thus we have

\[ \begin{eqnarray} (100 + 10 \lozenge + 1) + (100\lozenge + 10(0) +\lozenge) &=& (800 + 10\lozenge + 8 ) \\ \require{cancel} (100 + \xcancel{10 \lozenge} + 1) + (100\lozenge + \cancel{10(0)} +\lozenge) &=& (800 + \xcancel{10\lozenge} + 8 ) \\ 100(\lozenge+1) + (\lozenge+1) &=& 800 + 8 \\ \lozenge+ 1 &=& 8 \\ \lozenge &=& 7. \ _\square \end{eqnarray} \]

### 2) Rearrangement of columns

\[ \begin{array}{ccccc} & & & 1 & 1&A\\ & & & 1 & A&1\\ + & & & A & 1&1\\ \hline & & & 5 & 5&5\\ \hline \end{array} \qquad \qquad \begin{array}{ccccc} & & & A & A&A\\ & & & 1 & 1&1\\ +& & & 1 & 1&1\\ \hline & & & 5 & 5&5\\ \hline \end{array} \]

The above shows two cryptograms. For the left one, if we rearrange the digits/letters in their respective columns, we will obtain the cryptogram on the right. Be warned that we can only do this when it is a simple addition. This works because we have converted the cryptogram to an equation and then back to a revised cryptogram. Thus, solving for the unknown in the left one is equivalent to solving the right one. In this case, a simple algebra can solve it:

\[\overline{AAA} + 111 + 111 = 555 \Rightarrow \overline{AAA} = 333 \Rightarrow A = 3. \]

\[ \begin{array}{ccccc} & & & A & B&C\\ & & & B& C&A\\ + & & & C &A&B\\ \hline & & & 6 & 6&6\\ \hline \end{array} \]

## For the above cryptogram, find the value of \(A,B\) and \(C\) such that \(A<B<C\).

Rearranging the digits in their respective columns, we can obtain the following cryptogram,

\[ \begin{array}{ccccc} & & & A & A&A\\ & & & B& B&B\\ + & & & C &C&C\\ \hline & & & 6 & 6&6\\ \hline \end{array} \]

Interpreting this cryptogram shows that the sum of digits in any of the columns yields 6. Since \(A<B<C\) and they are all single digit positive integers such that \(A+B+C=6\), we have \(A=1,B=2,C=3\) only. \(_\square\)

**Bonus**: Try to solve the above example with 666 replaced by 777.

### 3) Carry Over

A **carry** is a digit that is transferred from one column of digits to another column of more significant digits.

\[ \large{\begin{array}{ccccccc} && & & S& E & N&D\\ +&& & & M& O & R&E\\ \hline & & & M & O& N & E&Y\\ \hline \end{array}} \]

For the cryptogram above, we can immediately show that \(M=1\) without knowing the values of the other unknown letters! Here's how:

We can show that the sum of two 4-digit integers does not exceed \(9999 + 9999 = 19998\). Also, since we know that \(M\) is non-zero, \(M \) is forced to be \(1.\)

The benefit of this technique is to restrict the possible values of unknown variables and thus make the puzzle easier to solve. More generally, we have the following theorem:

If we have \(n\) positive integers such that they all have the same number of digits, the maximum value of the carry over of the sum of these numbers is \(n-1. \ _\square\)

\[ \begin{array}{ccccc} & & 8& 7 & 6&4\\ + & & 9 & B& 3&2\\ \hline & A & 8 & C & 9&B\\ \hline \end{array} \]

## In the above cryptogram with some unknowns \(A, B\) and \(C,\) find the value of \(A.\)

Using the concept of carry over that we've learned above, we can see that \(A=1\) only. \(_\square\)

Note:We can obviously solve for the other unknowns first. For example, from the first column \(B= 4+2\) and from the third column \(7+6=13\), which implies \(C=3\) because we only take the last digit of \(13\) for \(C.\) So the carry is \(c_3 = 1 \). Then \(8 + 9 + 1 = 18 \) with carry over \(c_4 = 1\). Thus \(A = 1 \). But this method is much longer.

## When the sum of four distinct 4-digit integers is equal to a five digit number \(W\), find the possible value(s) of the leading digit of \(W\).

Using the concept of carry over, we figure that the maximum possible value of \(W\) is

\[9999 + 9998 + 9997 + 9996 = 39990 .\]

So, all the the possible values of the leading digit of \(W\) are \(1, 2\) and \(3. \ _\square\)

\[ \large{\begin{array}{ccccccc} && & & S& E & N&D\\ +&& & & M& O & R&E\\ \hline & & & M & O& N & E&Y\\ \hline \end{array}} \]

## From the above explanations, we know that \(M = 1\). Using the concept of carry over, show that

\(\begin{array}{r r l} \\ & \text{i)} &S \text{ must equal } 9. \\ & \text{ii)} & N=E+1. \end{array}\)

Since there is a carry in the \(4^{\text{th}}\) column, for the \(4^{\text{th}}\) column \(O \) must be less than or equal to \(M = 1\). But all these distinct letters are of distinct values, so by reading the \(4^{\text{th}} \), we have \(S+ M + c_3 = 10M + O \), where \(c_3 \) is the carry over of the \(3^\text{rd} \) with \(c_3 = 0\) or \(c_3 = 1\). Keep in mind that the only possible value of \(S \) and \(O \) are \(0,2,3,4,\ldots,9\).

If \(c_3 = 0\), we have \(S+1 + 0 = 10 + O \), or simply \(S =9 + O \), which forces \(S\) to take the value of 9 only and \(O\) to take the value of \(0\).

If \(c_3 = 1\), we have \(S+1 + 1 = 10 + O \), or simply \(S =8 + O \), which forces \(S\) to take the value of 8 only and \(O\) to take the value of \(0\).

Either way, \(O = 0\) is the only possible solution.

This is a sum of \(2\) positive integers with the same number of digits, so the carry over is either 0 or 1 only. So \(S= 8\) or \(S=9\) only. If \(S=8\), then there will be a carry in column 3, implying \(N\) would be less than or equals to \(O = 0 ,\) which is impossible. So there's no carry over for the third column. Thus \(S = 9 \) only.

Lastly, we refer to the third column. Since \(O = 0\), there is a non-zero value of carry over, which implies \(c_2 = 1 .\) Therefore, \(N=E+1. \ _\square\)

## Number Theory Techniques

### 4) Divisibility Rules

Like Modular Arithmetic, we will be applying some properties of divisibility rules for cryptogram. If you are not familiar with that concept, please see the main article first, Divisibility Rules.

\[ \large{\begin{array}{ccccccc} && & 1 & 2& 3 & 4&A\\ \times && & & & & &9\\ \hline & & 1 & B & 1& 1 & 0&5\\ \hline \end{array}} \]

By divisibility rule of \(5,\) since the last digit of the \(6\)-digit number is \(5,\) at least one of the last digits of the two other numbers must end with \(5.\) Thus \(A=5\). Now, because the \(6\)-digit number is divisible by \(9,\) its sum of digits must be divisible by \(9\) as well. So \(1 + B+ 1 + 1 + 0 + 5 = B + 8 \) is divisible by \(9\) with \(B \) a single digit integer, which implies \(B= 1\) only.

\[ \large{\begin{array}{ccccccc} && & & & 1 & 2&3\\ \times && & & & 4&5 &6\\ \hline & & & A & 6& 0 & 8&8\\ \hline \end{array}} \]

## The above shows an incomplete cryptogram. Find the values of \(A\) using the properties of divisibility rules alone.

Because \(123 \) is divisible by \(3\) and \(456\) is divisible by \(3,\) \(123\times456\) is divisible by \(9.\) This means that \(\overline{A6088} \) is divisible by \(9,\) implying the sum of its digits must be divisible by \(9\) as well: \(A + 6 + 0 + 8 + 8 \equiv 0 \pmod 9 \Rightarrow A = 5. \ _\square\)

\[ \large{\begin{array}{ccccccc} && & 1 & 2& 3 & 4&5\\ \times && & & & &3 &6\\ \hline & & 4 & 4 & 4& 4 & A&B\\ \hline \end{array}} \]

## The above shows an incomplete cryptogram. Find the values of \(A\) and \(B\) using the properties of divisibility rules alone.

Because \(12345\) ends with a \(5,\) the \(6\)-digit number is divisible by \(5,\) so the last digit of this number is either \(0\) or \(5\) only. Because it is a multiplication of an even number, the last digit must be \(0,\) so \(B = 0 \) only.

Since \(36 = 4\times 9 \), the \(6\)-digit number is divisible by \(9.\) Thus, the sum of digits is divisible by \(9\) as well. That is, \(4 + 4 + 4 + 4 + A +B \equiv 0 \pmod 9\Rightarrow A = 2 \) only. \(_\square\)

\[ \Large \begin{array} {c c c c }
& & \color{purple}{X}& \color{purple}{X} \\
& & \color{red}{Y} & \color{red}{Y} \\

+ & & \color{blue}{Z} & \color{blue}{Z} \\

\hline
& \color{purple}{X} & \color{red}{Y} & \color{blue}{Z} \\
\end{array} \]

If each letter represents a distinct digit, what is the value of the three-digit number \( \overline{XYZ}? \)

### 5) Factoring of terms

In this section, we will take advantage of the factorization of integers to solve cryptograms.

\[ \large{\begin{array}{ccccccc} && & & & A & B&B\\ \times && & & & &C &D\\ \hline & & & 1 & 8& 3 & 5&7\\ \hline \end{array}} \]

For the above example, we have one \(2\)-digit number and one \(3\)-digit number such that their product equals to \(18357.\) By prime factorization, we have \(18357 = 3 \times29\times211\) (the number 211 can be easily verified to be a prime). Converting to the form as above, we either have \(18357 = 87 \times211 \) or \(18357 = 633 \times 29 \). So there exist two solutions, namely \((A,B,C,D) = (2,1,8,7), (6,3,2,9) \).

### 6) Modular Arithmetic

We will be applying some properties of modular arithmetic for cryptogram. If you are not familiar with that concept, please see the main article first, Modular Arithmetic.

\[ \large{\begin{array}{ccccccc} && & & 3& 1 & 2&5\\ \times && & & & 2 &0 &8\\ \hline & & 6 & 5 & \diamondsuit& \clubsuit & \heartsuit&\spadesuit\\ \hline \end{array}} \]

The above shows an incomplete multiplication between two numbers, where we have not necessarily distinct single digit integers \(\diamondsuit, \clubsuit , \heartsuit \) and \(\spadesuit \). Because \(3125 \) is divisible by \(5^4\) and \(208 \) is divisible by \(2^4\), their product is divisible by \((5\times2)^4 = 10^4\). So \( \overline{65 \diamondsuit \clubsuit \heartsuit\spadesuit} \) must be divisible by \(10^4\). Thus by modular arithmetic, \( \diamondsuit= \clubsuit =\heartsuit=\spadesuit = 0 \).

## In our earlier example, we obtained \(M = 1, O = 0,S = 9 \) and \( N=E+1\). Using this additional information, show that \(R=8 \).

Suppose there were no carry in the \(2^{\text{nd}}\) column, then \(N +R \equiv E \pmod {10} \) with \(N =E+1 .\) Then we can simplify the congruence to \(R+1 \equiv 0 \pmod {10} \), which implies \(R = 9\). But this is a contradiction since \(S = 9 \) already and all the letters must be distinct. So there is no carry in the \(2^{\text{nd}}\) column, which implies \(R = 8\) only. \(_\square\)

Now, can you finish off the very first cryptogram above?

### 7) Chinese Remainder Theorem

For some cryptarithm involving multiplication, Chinese Remainder Theorem (CRT) will come in handy. It uses some properties of modular arithmetic. If you are not familiar with that concept, please see the main article first, Chinese Remainder Theorem.

\[ \large{\begin{array}{ccccccc} && & & & A & B&C\\ \times&& & & & & B&C\\ \hline & & & & D& A & B&C\\ \hline \end{array}} \]

With the same rules applied, can you solve this cryptarithm?

Notice that the last two digits of all these three numbers are the same. Writing it down in linear congrunce gives \(x^2 \equiv x \pmod {100} \), or \( x(x-1) \equiv 0 \pmod {100} \). Because \(x\) and \(x-1\) are consecutive, they must be coprime. With \(100 = 4\times25 \), we have

\[\begin{array} &\text{either} &x \equiv 0 \pmod 4, &x - 1 \equiv 0 \pmod {25}, &&\text{or} &x \equiv 0 \pmod {25}, &x - 1 \equiv 0 \pmod 4. \end{array} \]

Solving via CRT gives \(x \equiv 25 \text{ or } 76 \) only, implying \(\overline{ABC} = A25 \text{ or } A76 \). Can you finish out the solution by yourself?

The above shows a cryptarithm such that each letter represents a distinct single non-negative integer with \(J, B\) being non-zero. Find the sum of all the possible values of the \(4\)-digit number \(\overline{JEEP} \).

## Computer Science Techniques

### 8) Trial and error

Sometimes, there could be no easy way to deal with a cryptogram, and the most we can do is to apply brute force approach and check each case to determine whether they yield a solution.

\[ \large{\begin{array}{ccccccc} && & &1 & 2 & \bigstar &4\\ \times && & & & &2 &7\\ \hline & & & \bigstar & \bigstar & \bigstar & 1&8\\ \hline \end{array}} \]

Take the above as an example, where \(\bigstar\) could be any integer between \(1\) and \(9\) inclusive: \( \bigstar =1,2,\ldots,9\). By trial and elimination, \( \bigstar =3\) only. This is the simplest approach to tackle this problem because there is only one unknown to consider and this unknown is set up in such a way that other solving techniques will take longer.

### 9) Programming approach

Sometimes, it would be more tedious to check for all possible cases like the trial and error approach. So it's not an ideal way to solve this and thus we need to apply other techniques. A viable approach is to use programming codes to solve it.

\[ \large{\begin{array}{ccccccc} &&E& U & R & O&P&A\\ + &J&U & P&I & T &E &R\\ \hline &N & E & P& T & U & N&E\\ \hline \end{array}} \]

## Find the values of the unknown letters represented in the cryptogram above.

Solution:

1 2 3 4 5 6 7`from itertools import permutations for i in permutations('0123456789'): str = ''.join(i) [E,U,R,O,P,A,J,I,T,N]=list(str) if int(E+U+R+O+P+A)+int(J+U+P+I+T+E+R)==int(N+E+P+T+U+N+E): print (int(E+U+R+O+P+A))`

The output is \(794853+1956074=2750927. \ _\square\)

### 10) Branch and Bound

There is a method called Branch and Bound that utilizes a technique from Operations Research. For the main article, refer to Branch and Bound.

## Problem Solving

The examples above in this wiki page show cryptograms that require only one technique. However, it will be trickier to solve a cryptogram that uses a mix of techniques, which is developed out in the follow-up page: Cryptogram - Problem Solving.

The techniques mentioned above in this page are sufficient enough to tackle all cryptogram problems. However, it is definitely beneficial to know which technique to use when solving a cryptogram. Here are a few good indicators on how to identify which techniques are useful when tackling a cryptogram:

Technique | Type of problem | Conditions to apply |

1) Converting cryptogram to equation | All | Few symbols, which occur 1-2 times each |

2) Rearrangement of columns | \(+, -\) | At most 1-2 symbols in each column |

3) Carry Over | \(+, -\) | (Most useful technique) to identify additional constraints |

4) Divisibility Rules | \(\times\) | A term has a factor with a simple rule of divisibility |

5) Factoring of terms | \(\times\) | If we know the entire term and can easily factorize it |

6) Modular Arithmetic | \(\times\) | If we have a lot of information modulo a value (like 2, 3, 4, 5, 8) |

7) Chinese Remainder Theorem | \(\times\) | Last few digits of 2 or more numbers are the same |

8) Trial and error | All | Few variables, but they occur many times |

9) Programming approach | All | Any cryptogram will do |