# 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:

• the middle digit is $$0$$,

• the ten thousands digit and the tens digit are equal,

• the thousands digit and the ones (units) digit are equal, and

• the number has exactly $$5$$ prime factors. All of these prime factors are odd and none are repeated.

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$$.