# Solving Kordemsky's Prime Cryptarithm and proving uniqueness

This is a cryptarithm from Kordemsky's The Moscow Puzzles, problem 273 to be precise. Each digit is a single-digit prime ($$2,3,5,$$ or $$7$$). Find a solution and prove that it is unique.

$$\begin{array}{ccccc} & & * & * & * \\ & & \times & * & * \\ \hline & * & * & * & * \\ * & * & * & * & \\ \hline * & * & * & * & * \end{array}$$

The following is an answer that is easy to verify but I do not know how to come up with it or how to prove uniqueness. Help would be appreciated.

$$\begin{array}{ccccc} & & 7 & 7 & 5 \\ & & \times & 3 & 3 \\ \hline & 2 & 3 & 2 & 5 \\ 2 & 3 & 2 & 5 & \\ \hline 2 & 5 & 5 & 7 & 5 \end{array}$$

The book does not provide a full solution, but here is some work that I have done based on the hint:

We will look at the units digits of products of single-digit primes. By trying out the $$\binom{4}{2}+4=10$$ possible pairs, we find that the units digit is prime again if and only if we are working with $$3\times 5,5\times 5,$$ or $$5\times 7.$$ In each case, the units digit is $$5.$$ So the bottom three rightmost numbers in the table are all $$5.$$ And at least one of the rightmost digits of the first two lines is $$5,$$ the other being $$3,5,$$ or $$7.$$

• This seems to be more a thing for mathematics than puzzling. You've given us the answer, and the problem gives us the assertion that it's unique, so the only thing that's left is derivation and proving that uniqueness. That doesn't seem like so much of a puzzling thing. – Ben Barden Jan 15 at 20:43
• @BenBarden I was hoping that the process of coming up with the solution would provide insight into uniqueness. If moderators feel that this puzzle is inappropriate for this forum, please move it to math.se. – Favst Jan 15 at 21:07

Case-bashing here is not so bad (and perhaps somewhat necessary since some of the examples come very close to working).

For ease, I will use the following notation $$\begin{array}{ccccc} & & A1 & A2 & A3 \\ & & \times & B1 & B2 \\ \hline & C1 & C2 & C3 & C4 \\D1 & D2 & D3 & D4 & \\ \hline E1 & E2 & E3 & E4 & E5 \end{array}$$

So far, you have discovered that

$$C4 = E5 = 5$$ and either $$A3$$ or $$B2$$ is $$5$$ with the other being $$3,5$$ or $$7$$. For now, Let us consider these as three separate cases.

Case 1

One of $$A3, B2$$ is $$7$$ and the other is $$5$$.
Since $$7 \times 5$$ is $$35$$, we see that this multiplication carries over $$3$$ to the next decimal place. This makes $$C3$$ equal to the last digit of $$A2 \times B2 + 3$$. The only possibilities therefore are
(i) $$A2 = B2 = 7$$ and $$C3 = 2$$.
(ii) $$A2 = 2$$, $$B2 = 5$$ and $$C3 = 3$$.
(iii) $$A2 = 2$$, $$B2 = 7$$ and $$C3 = 7$$.

In case (i), we carry over a $$5$$ to the next multiplication, $$A1 \times B2$$ where, this time, both digits from the result must be prime. Checking through the four cases for $$A1 = 2,3,5,7$$, we quickly see that in none of the results do we achieve that so this is a dead end.
In case (ii), we carry over a $$1$$ to the next multiplication. Again, checking through the four cases, $$A1 = 2,3,5,7$$ we see that $$A1 \times B2 + 1$$ cannot have both its digits prime and so this is another dead end.
In case (iii), we also carry over a $$1$$ to the next multiplication. This time there is exactly one instance where the product gives us a number, both of whose digits is prime, $$A1 = 3$$ and thus $$C1 = C2 = 2$$.
Following on from here, we can check through the four cases of $$B1$$ multiplied by $$325$$ ($$A1-A2-A3$$) to check whether the digits $$D1, D2, D3, D4$$ are prime. We already know it will work for $$B1=7$$ and $$B1=2$$ is an obvious dead end as $$D4$$ would be $$0$$.
$$3\times 325$$ will only have three digits and $$5 \times 325$$ will begin with a $$1$$ so they are also out. Hence $$B1 = 7$$ is the only possibility. Thus, so far we have $$\begin{array}{ccccc} & & 3 & 2 & 5 \\ & & \times & 7 & 7 \\ \hline & 2 & 2 & 7 & 5 \\2 & 2 & 7 & 5 & \\ \hline E1 & E2 & E3 & E4 & E5 \end{array}$$ and evaluating the final sum gives $$25025$$ so, in this case, only $$E3=0$$ is non-prime.

Case 2

$$A3 = B2 = 5$$.
Since $$5 \times 5$$ is $$25$$, we see that this multiplication carries over $$2$$ to the next decimal place. This makes $$C3$$ equal to the last digit of $$A2 \times 5 + 2$$. We see that, in this case $$A2$$ can be any of the four possibilities and $$C3$$ will be prime. However, if we carry over a $$1$$ to the next product ($$A1 \times 5$$) then $$C2$$ cannot be prime, hence there are only two cases which we need to investigate, namely

(i) $$A2 = 5$$ and $$C3 = 7$$.
(ii) $$A2 = 7$$ and $$C3 = 7$$.
In case (i), we carry over a $$2$$ to the next multiplication and to get $$C1$$ and $$C2$$ both prime, we must have $$A1 = 5$$ or $$7$$.
In case (iii), we carry over a $$3$$ in which case, no choice for $$A1$$ will make both $$C1$$ and $$C2$$ prime.

Therefore, we only have two remaining cases to consider for $$A1-A2-A3$$ which are $$555$$ and $$755$$. In the $$555$$ case, we can easily see that $$B1$$ cannot be $$2$$ and if $$B1=3$$ then $$D1$$ would be $$1$$. If $$B1$$ is $$7$$ then $$D3=8$$ and so this would also not work.
Hence, we must have $$B1=5$$ and the product looks like this $$\begin{array}{ccccc} & & 5 & 5 & 5 \\ & & \times & 5 & 5 \\ \hline & 2 & 7 & 7 & 5 \\2 & 7 & 7 & 5 & \\ \hline E1 & E2 & E3 & E4 & E5 \end{array}$$ and evaluating the final sum gives $$30525$$ so, in this case, only $$E2=0$$ is non-prime.

When $$A1-A2-A3$$ is $$755$$ we can see that $$B1$$ is not $$2$$. $$B1=3$$ makes $$D3=6$$ and $$B1=7$$ makes $$D3=8$$ so the only thing that will work here is $$B1=5$$.
Overall, we have $$\begin{array}{ccccc} & & 7 & 5 & 5 \\ & & \times & 5 & 5 \\ \hline & 3 & 7 & 7 & 5 \\3 & 7 & 7 & 5 & \\ \hline E1 & E2 & E3 & E4 & E5 \end{array}$$ and evaluating the final sum gives $$41525$$ so, in this case, both $$E1$$ and $$E2$$ are non-prime.

Case 3

One of $$A3, B2$$ is $$3$$ and the other is $$5$$.
Since $$3 \times 5$$ is $$15$$, we see that this multiplication carries over $$1$$ to the next decimal place. This makes $$C3$$ equal to the last digit of $$A2 \times B2 + 1$$. The only possibilities therefore are

(i) $$A2=2$$, $$B2=3$$ and $$C3=7$$.
(ii) $$A2=7$$, $$B2=3$$ and $$C3=2$$.

In case (i), we carry over nothing to the next multiplication which means we need both digits of the product $$A1 \times 3$$ to be prime which doesn't happen for any of the possible values of $$A1$$.
In case (ii), we carry over a $$2$$ to the next product, which means that both digits of $$A3 \times 3 + 2$$ must be prime and this only happens for $$A1 = 7$$, so that $$A1-A2-A3$$ is $$775$$.
Now checking through the cases for $$B1$$ we see that it cannot be $$2$$ (otherwise $$D4=0$$), $$B1$$ cannot be $$5$$, otherwise, $$D2=8$$ and $$B1$$ cannot be $$7$$, otherwise $$D2=4$$. These latter cases can also be ruled out as, otherwise, they would have appeared as candidate solutions in one of the first two main cases. Hence, $$B1 = 3$$ is the only possibility.
Plugging into the equation we have $$\begin{array}{ccccc} & & 7 & 7 & 5 \\ & & \times & 3 & 3 \\ \hline & 2 & 3 & 2 & 5 \\2 & 3 & 2 & 5 & \\ \hline E1 & E2 & E3 & E4 & E5 \end{array}$$ and evaluating the final sum gives $$25575$$ all of whose digits are prime so this is the only solution.