CEMC Banner

Problem of the Week
Problem E and Solution
A Small Subset

Problem

There are \(90\,000\) five-digit positive integers. However, only some of these five-digit integers satisfy the following conditions:

Determine all five-digit positive integers that satisfy the given conditions.

Solution

Solution 1

Let \(st0st\) represent a five-digit positive integer satisfying the conditions. Notice that \[st0st=st(1000)+st=st(1000+1)=st(1001)\] This means that the number \(st0st\) is divisible by \(1001\), which is the product of the three odd prime factors \(7\), \(11\), and \(13\). So \(st\) is a two-digit number which is the product of two different odd prime factors none of which can be \(7\), \(11\) or \(13\). We will now generate all possible two-digit products, using odd prime factors other than \(7\), \(11\) and \(13\).

Prime
Factor \(a\)
Prime
Factor \(b\)
\(st = a\times b\)Five Different
Odd Primes
Product
\(st0st\)
\(3\)\(5\)\(15\)\(3,5,7,11,13\)\(15015\)
\(3\)\(17\)\(51\)\(3,7,11,13,17\)\(51051\)
\(3\)\(19\)\(57\)\(3,7,11,13,19\)\(57057\)
\(3\)\(23\)\(69\)\(3,7,11,13,23\)\(69069\)
\(3\)\(29\)\(87\)\(3,7,11,13,29\)\(87087\)
\(3\)\(31\)\(93\)\(3,7,11,13,31\)\(93093\)
\(5\)\(17\)\(85\)\(5,7,11,13,17\)\(85085\)
\(5\)\(19\)\(95\)\(5,7,11,13,19\)\(95095\)

No other two-digit product of two different odd prime factors other than \(7\), \(11\) and \(13\) exists.

Therefore, there are \(8\) five-digit positive integers that satisfy the given conditions. The numbers are \(15015\), \(51051\), \(57057\), \(69069\), \(87087\), \(93093\), \(85085\) and \(95095\).

Solution 2

Let \(st0st\) represent a five-digit positive integer satisfying the conditions.

A number is divisible by \(11\) if the difference between the sum of the digits in the even positions and the sum of the digits in the odd positions is a multiple of \(11\). (This problem can still be done without knowing this divisibility fact but the task is made simpler with it.) The sum of the digits in the even positions is \(st0st\) is \(t+s\). The sum of the digits in the odd positions is \(s+0+t\) which simplifies to \(s+t\). The difference of the two sums is \((t+s)-(s+t)=0\) which is a multiple of \(11\). Therefore, \(st0st\) is divisible by \(11\).

Only odd factors are used, so the product will be odd. This means that the product looks like \(s10s1\), \(s30s3\), \(s50s5\), \(s70s7\), or \(s90s9\) where \(s\) is a digit from \(1\) to \(9\). So we begin to systematically look at the possibilities.

First, we will examine numbers that have \(3\) (and \(11\)) as a factor. To be divisible by \(3\), the sum of the digits will be divisible by \(3\). To be divisible by \(9\), the sum of the digits will be divisible by \(9\). But if the number is divisible by \(9\), it is divisible by \(3^2\) and would have a repeated prime factor which is not allowed. So we want numbers divisible by \(3\) but not \(9\). The possibilities are as follows: \(21021\), \(51051\), \(33033\), \(93093\), \(15015\), \(75075\), \(57057\), \(87087\), \(39039\), and \(69069\). The sum of the digits of each of these numbers is divisible by \(3\) so each of the numbers are divisible by \(3\). The numbers \(81081\), \(63063\), \(45045\), \(27027\) and \(99099\) are divisible by \(9\) and have therefore been eliminated.

Now we examine the prime factorization of each of these numbers to see which numbers satisfy the conditions. \[21021=3\times 11\times 637=3\times 11 \times 7 \times 91= 3\times 11 \times 7 \times 7 \times 13\] Since the prime factor 7 is repeated, this is not a valid number. \[51051=3\times 11\times 1547=3\times 11 \times 7 \times 221= 3\times 11 \times 7 \times 13 \times 17\] Since there are 5 different odd prime factors, 51051 is a valid number. \[33033=3\times 11\times 1001=3\times 11 \times 7 \times 143= 3\times 11 \times 7 \times 11 \times 13\] Since the prime factor 11 is repeated, this is not a valid number. \[93093=3\times 11\times 2821=3\times 11 \times 7 \times 403= 3\times 11 \times 7 \times 13 \times 31\] Since there are 5 different odd prime factors, 93093 is a valid number. \[15015=3\times 11\times 455=3\times 11 \times 5 \times 91= 3\times 11 \times 5 \times 7 \times 13\] Since there are 5 different odd prime factors, 15015 is a valid number. \[75075=3\times 11\times 2275=3\times 11 \times 5 \times 455= 3\times 11 \times 5 \times 5 \times 91=3\times 11 \times 5 \times 5 \times 7 \times 13\] Since the prime factor 5 is repeated and there are six prime factors, this is not a valid number. \[57057=3\times 11\times 1729=3\times 11 \times 7 \times 247= 3\times 11 \times 7 \times 13 \times 19\] Since there are 5 different odd prime factors, 57057 is a valid number. \[87087=3\times 11\times 2639=3\times 11 \times 7 \times 377= 3\times 11 \times 7 \times 13 \times 29\] Since there are 5 different odd prime factors, 87087 is a valid number. \[39039=3\times 11\times 1183=3\times 11 \times 7 \times 169= 3\times 11 \times 7 \times 13 \times 13\] Since the prime factor 13 is repeated, this is not a valid number. \[69069=3\times 11\times 2093=3\times 11 \times 7 \times 299= 3\times 11 \times 7 \times 13 \times 23\] Since there are 5 different odd prime factors, 69069 is a valid number.

Second, we will examine numbers that are divisible by \(5\) but not \(3\), since divisibility by \(3\) has been examined. If a number is divisible by \(5\), then it ends in \(5\) or \(0\). Since the number is odd, we can exclude any number ending in \(0\), leaving \(25025\), \(35035\), \(55055\), \(65065\), \(85085\) and \(95095\) as possible numbers. (\(15015\), \(45045\), \(75075\) were examined above and have been excluded.)

Now we examine the prime factorization of each of these numbers to see which numbers satisfy the conditions. \[25025=5\times 11\times 455=5\times 11 \times 5 \times 91= 5\times 11 \times 5 \times 7 \times 13\] Since the prime factor 5 is repeated, this is not a valid number. \[35035=5\times 11\times 637=5\times 11 \times 7 \times 91= 5\times 11 \times 7 \times 7 \times 13\] Since the prime factor 7 is repeated, this is not a valid number. \[55055=5\times 11\times 1001=5\times 11 \times 7 \times 143= 5\times 11 \times 7 \times 11 \times 13\] Since the prime factor 11 is repeated, this is not a valid number. \[65065=5\times 11\times 1183=5\times 11 \times 7 \times 169= 5\times 11 \times 7 \times 13 \times 13\] Since the prime factor 13 is repeated, this is not a valid number. \[85085=5\times 11\times 1547=5\times 11 \times 7 \times 221= 5\times 11 \times 7 \times 13 \times 17\] Since there are 5 different odd prime factors, 85085 is a valid number. \[95095=5\times 11\times 1729=5\times 11 \times 7 \times 247= 5\times 11 \times 7 \times 13 \times 19\] Since there are 5 different odd prime factors, 95095 is a valid number.

Thirdly, we will look at numbers that are divisible by \(7\) but not divisible by \(3\) or \(5\). If we multiply \(7\) by the next four odd prime numbers we get \(7\times 11\times 13\times 17\times 19=323\,323\), a six-digit number, so we are beyond all possible solutions.

Therefore, there are \(8\) positive five-digit integers that satisfy the given conditions. The numbers are \(51051\), \(93093\), \(15015\), \(57057\), \(87087\), \(69069\), \(85085\) and \(95095\).