Maths Olympiad Prep

Library / /25 of 34

Number theory Difficulty 6.3 National olympiad Prove it Romania

Find all prime numbers with n3n \ge 3 digits, having the property: for every k{1,2,,n2}k \in \{1, 2, \dots, n-2\}, deleting any kk of its digits leaves a prime number.

Solution

Answer: 113, 131, 137, 173, 179, 197, 311, 317, 431, 617 and 719.
Denote N=anan1a1a0N = \overline{a_n a_{n-1} \dots a_1 a_0}, such a number. We can make the following observations.

O1. NN has at most one digit multiple of 3, because otherwise we delete the other digits and we get a two digit multiple of 3. In the same way, NN cannot have three digits congruent mod 3, because the elimination of the other digits would leave a three digit multiple of 3.

O2. NN has exactly three digits. Indeed, if NN has at least 4 digits, then three of its digits must leave the remainder 1 or 2 mod 3 and, in view of (O1), we must get both remainders, so the number made by this two digits is divisible by 3.

O3: NN has at most one even digit, and this can be only the first one, because otherwise when we delete all the digits placed at right side of the (last) even digit we get an even two digit number.

O4: NN cannot have a 5. Otherwise, NN could have at most one 5 and this should be in the first position. Now (O3) shows that NN cannot have even digits. Since NN has at most one of the digits 3 and 9, NN has at least one of the digits 1 and 7. Deleting the proper digits we would get 51 or 57, numbers which are not primes.

If NN has three odd digits, then NN has a 3 or a 9 and the other two digits are 1 and/or 7. Checking all the combinations, we get the solutions 113, 131, 137, 173, 179, 197, 311, 317, 719.

If the first digit of NN is even, then (O1) and (O4) show that this digit cannot be 2 or 8, because if otherwise NN should have a 1 or a 7 and, deleting the appropriate digits, we get a two digit multiple of 3. If the first digit is 6, then the other two are from {1,7}\{1, 7\}, and if the first digit is 4, another one is 1 or 7 and the third is 3 or 9. This way we get the solutions 617 and 431.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.