Minimum Number of Divisors

Number Theory Level pending

What is the minimum number of divisors for the 8-digit number $\overline{abbaabba}$ , where $a$ and $b$ are integers from 1 to 9?

Details and assumptions

$\overline{abc}$ means $100a + 10b + 1c$ , as opposed to $a \times b \times c$ . As an explicit example, for $a=2, b=3, c=4$ , $\overline{abc} = 234$ and not $2 \times 3 \times 4 = 24$ .

The answer is 16.

7 solutions

Calvin Lin Staff
May 13, 2014

$11111111 = 11 \times 73 \times 101 \times 137$ has 16 divisors. We have $\overline{abbaabba} = 10001\times \overline{abba} \Rightarrow$ $\overline{abbaabba} = 10001 \times 11 \times (10b+91a) = 11 \times 73 \times 137 \times (10b+91a)$ . If $(10b+91a)$ has a prime factor other than $11, 73, 137$ , then we are guaranteed to have at least $(1+1) \times (1+1) \times (1+1) \times (1+1) = 16$ divisors.

To attempt to reduce the number of divisors, we must have $10b + 91a = 11^{x} 73^{y} 137 ^{z}$ for some non-negative integers $x, y$ and $z$ . Then, $\overline{abbaabba} = 11^{x+1} 73^{y+1} 137^{z+1}$ and it has $(x+2)(y+2)(z+2)$ factors. Since $3 \times 3 \times 2 = 18 > 16$ and $4 \times 2 \times 2 = 16$ , thus $(x,y,z) = (0,0,0)$ and any permutation of $(x,y,z) = (1,0,0)$ are the only possible cases where we can get less than 16 factors. Hence we need only consider the case where $10b+91a = 1, 11, 73$ or $137$ where $a$ and $b$ are integers from 1 to 9. Since $a,b \geq 1$ , thus $10b + 91a \geq 101$ , so the only possibility to check is $10b + 91a = 137$ . Since $91\times 2 > 137$ this implies that $a=1$ which gives $b = \frac{23}{5}$ . Thus there are no integer solutions within the given range and it is not possible to have less than 16 divisors. Hence, the minimum number of divisors is 16, which is achieved by 11111111.

Note: The minimum number of divisors is achieved when $10b+91a$ is a prime, or equal to 121 (this yields the number 13311331).

Rishav Roy
May 20, 2014

The given number can be written as abba (10^4 +1). it can be checked that 10^4 + 1 is a prime. So the problem now reduces to finding out the minimum number of divisors of abba. The sum of digits in odd places=a+b and the sum of digits in even places=a+b. Thus abba is divisible by 11. So if we can find an example where abba=11 (some prime) we will get the situation of minimum number of divisors. Observe that 3223=11*293 and 293 is a prime. Hence the minimum possible number of divisors of abbaabba is 6.

Comments and replies:

Calvin:

Can you explain how you checked that $10^4+1$ is prime?
Can you explain how you calculated 6 divisors? I don't see any explanation for 6, and it seemed pulled from nowhere.

Rishav Roy:

I'm sorry. 10^4+1=73 * 137. 73 and 137 are both primes. Thus the integer can be represented as 73 137 11 (prime) for the minimum case( for eg 3223=73 137 11 293). If the prime factorization of an integer is (p1^k1) (p2^k2) ..... (pn^kn) where p1,p2,...,pn are distinct primes and k1,k2,...,kn are positive integers then the number of divisors of the integer = (k1+1) (k2+1) ..... (kn+1). Applying the above concept, we find that the minimum number of divisors of abbaabba is (1+1)(1+1)(1+1)(1+1)=16.

[Calvin - Edited 10^4+1]

Calvin:

Rishav, your solution is not complete, as you're still missing out cases. Why must the minimum case be 73 137 11*(prime)? Look at how the divisors are calculated. Is there a way for us to get (possibly) less than 16?

Rishav Roy:

Let us denote number of divisors of abbaabba by d(n). 73,137,11 necessarily divide abbaabba. So if abbaabba/(73 137 11) is a composite number N = (q1^r1) (q2^r2)...(qn^rn) where q1,q2,...qn are distinct primes and distinct from 11,73,137 andr1,r2,....rn are positive integers then d(n) = (1+1)(1+1)(1+1)(1+r1)(1+r2)...(1+rn). Since N is composite n>= 2. so d(n)>=32(in case ri=rj=1 for some 1<=i,j=3 2 2 2=24. If N is composite and has 2 of 11,137,73 as its prime divisors then d(n)>=3 3 2=18. If N is composite and has all 3 of 11,137 and 73 as its prime divisors then d(n)>=3 3 3=27. Now consider N to be prime. If it is a prime distinct from 73,11and 137 then the number of divisors of abbaabba will be 2 2 2 2=16. But if it is = one of 11,73,137 then d(n)=2 2 3=12. Also note that N 11=abba. Case1 : N=11, N 11=121 is not in the form of abba. Case 2: N=73, N 11=803 is not in the form of abba. Case 3: N=137, N 11=1507 is not in the form of abba. Thus N has to be a prime distinct from 11,73 and 137. We have an example of 32233223=137 73 11 293 having d(n)=2 2 2*2=16. And hence the Minimum number of divisors of the number of the form abbaabba is 16.

Calvin:

I didn't understand what you meant by "Since N is composite n>= 2. so d(n)>=32(in case ri=rj=1 for some 1= 2". (aka that a composite number must have at least 2 distinct prime factors).

You still have (at least one) missing cases, in order to make your solution complete.

I agree with the rest of your analysis.

Rishav Roy:

In the above reply by mistake I have written 10^4=73 137. It should be 10^4+1=73 137. Apologies..

Calvin Lin Staff - 7 years ago

Sreejato Bhattacharya
May 20, 2014

The given number= 10^8a + 10^7b + 10^6b + 10^5a + 10^4a + 10^3b + 10^2b + a = 100110001 a + 11001100 b.

Now, g.c.d(100110001, 11001100) = 1

Take two co-prime numbers from the set {1,2,3,...9} [for example 3 and 7]. Let a and b be the two co-prime numbers.

Then, 100110001 a and 11001100 b have no common factors, which implies that the given number is a prime.

So, the minimum number of divisors of the given number is 2.

Comments and replies:

Calvin:

The first line should read $10011001a + 1100110b$ .

I don't see any reasoning why $\gcd (10011001, 1100110)=1$ . (Not saying that you are right or wrong, just that I don't see any explanation why this is obviously true.) Please explain.

I disagree with the (main) argument. For example, though $\gcd(3,5)=1$ , and the numbers 7, 11 are coprime, the number $3 \times 7 + 5 \times 11 = 21+55=76$ is not prime. I can create a multiple of $p$ by adding up two numbers which are not individually multiples of $p$ .

In particular, the number $\overline{abba}$ divides $\overline{abbaabba}$ (3773 divides 37733773), so the latter is never prime. The number $\overline{abbaabba}$ has more than 2 divisors.

Sreejato Bhattacharya:

Note:- The prime factorization of 11001100 is 2^2 5^2 11 73 137. So, a must be different from 2 and 5. Again, there are no prime factors of 100110001 in the set {1,2,...9}. So, b can be any number co-prime to a.

Sreejato Bhattacharya:

It has been shown that abbaabba = 73 * 137 * 11 * (91a + 10b).

Now, if 91a + 10b is a prime, it has 16 divisors.

Now it has to be proved that this is the minimum number of divisors.

On the contrary, assume that the minimum number of divisors occurs when 91a + 10b is composite.

Let 91a + 10b= (x1^y1) (x2^y2) ...*(xn^yn), where xi s are distinct primes and yi s are natural numbers.

Then, number of divisors of abbaabba= 8*(y1+1)(y2+1)(y3+1)...(yn+1)

Now, since 91a+10b is composite, the minimum value of n should be 2, and none of the yi s should be 0... Now, the minimum value of y1= 1, minimum value of y2= 1.

So, 8 (y1+1)(y2+1)...(yn+1) >= 8 2*2(y3+1)(y4+1)...(yn+1) > 16

Thus if 91a + 10b is composite, the number of divisors of abbaabba will be greater than 16.

So, the minimum occurs when this is prime.

Thus 16 is the answer.

Calvin:

I disagree that if (91a+10b) is a prime, then abbaabba has 16 divisors.

I disagree that if (91a+10b) is composite, then the minimum value of n should be 2.

I disagree that if (91a+10b) is composite, then it will have 8 2 2*... factors.

Please think why the above statements are true, and then see how to modify your solution.

Calvin Lin Staff - 7 years ago

Raoul Danniel Manuel
May 20, 2014

$\overline{abbaabba}=10001\times \overline{abba}$ $=(73\times 137)\times (1000a+100b+10b+a)$ $=(73\times 137)\times (1001a+110b)$ $=(73\times 137)\times [11\times (91a+10b)]$ $=11\times 73\times 137\times (91a+10b)$

If $91a+10b$ is prime, it can be $11,73,137$ , or some other prime. But $a \ge 1$ , so $91a+10b \ge 91$ and cannot be $11$ or $73$ . If $91a+10b=137$ , then $11\times (91a+10b)=\overline{abba}$ . But $137$ is not of this form. So $91a+10b$ must be some other prime, and $\overline{abbaabba}$ has $(1+1)(1+1)(1+1)(1+1)=16$ divisors.

If $91a+10b$ is composite, Case 1: $91a+10b=11^2,73^2,$ or $137^2$ (times a prime or product of primes). So $\overline{abbaabba}$ has at least $((1+\textbf{2})+1)(1+1)(1+1)=16$ divisors. Case 2: it can be some other prime squared (times a prime or product of primes). So $\overline{abbaabba}$ has at least $(1+1)(1+1)(1+1)(2+1)=24$ divisors. Case 3: $91a+10b=xy,x=11,73,$ or $137,y=$ a prime or product of primes. So $\overline{abbaabba}$ has at least $(2+1)(1+1)(1+1)(1+1)=24$ divisors. Case 4: $91a+10b=11\times 73,73\times 137,11\times 137,$ or $11\times 73\times 137$ (times a prime or product of primes). So $\overline{abbaabba}$ has at least $(2+1)(2+1)(1+1)=18$ divisors. Case 5: it is a product of at least 2 unequal primes (except $11,73,137$ ) raised to a positive integer. So $\overline{abbaabba}$ has $\emph{at least} (1+1)(1+1)(1+1)(1+1)(1+1)=32$ divisors.

In all cases, $\overline{abbaabba}$ has at least $16$ divisors.

Comments and replies:

Calvin:

You managed to find a case that everyone else missed - your Case 1. This actually yields the integer $13311331=11^3 \times 73 \times 137$ , which has 16 divisors. This was also the value that I was referencing to in Anoopam's reply. If he did the calculations, he would see that this integer 121 only has 11 as a factor, but is not prime.

However, your description of the cases need slight work. For example, you missed out the possibility that $91a+10b = 2 \times 11 \times 37$ . It doesn't qualify under case 4 (which only has 4 numbers) or case 5 (since it does not have 2 primes that are not 11, 73, 137). In this question, the checking of cases is extremely important. This can be simplified by a good choice of the description of cases.

Raoul Danniel Manuel:

$\overline{abbaabba}=10001\times \overline{abba}$ $10001=73\times 137$ $\overline{abba}=1000a+100b+10b+a=1001a+110b=11\times (91a+10b)$ So $\overline{abbaabba}=11\times 73\times 137 \times (91a+10b)$

If $91a+10b$ is prime, it can be $11,73,137$ , or some other prime. But $a \ge 1$ , so $91a+10b \ge 91$ and cannot be $11$ or $73$ . If $91a+10b=137$ , then $11\times (91a+10b)=\overline{abba}$ . But $11\times 137=1507$ is not of this form. So $91a+10b$ must be some other prime, and $\overline{abbaabba}$ has $(1+1)(1+1)(1+1)(1+1)=16$ divisors.

If $91a+10b$ is composite, Case 1: $91a+10b=p^xq$ , where $p=11,73,$ or $137,x \ge 2,q=1$ or (a product of) some other prime(s). So $\overline{abbaabba}$ has at least $(3+1)(1+1)(1+1)=16$ divisors. [Case 1 is possible only if $91a+10b=11^2. \overline{abba}=1331.$ ]

Case 2: $91a+10b=pq$ , where $p=11,73,$ or $137,q$ is (a product of) some other prime(s). So $\overline{abbaabba}$ has at least $(2+1)(1+1)(1+1)(1+1)=24$ divisors.

Case 3: $91a+10b=11^x73^yr,73^x137^yr,11^x137^yr,$ or $11^x73^y,137^zr$ , where $x,y,z \ge 1,r=1$ or (a product of) some other prime(s). So $\overline{abbaabba}$ has at least $(2+1)(2+1)(1+1)=18$ divisors.

Case 4: $91a+10b=p^xq$ , where $p$ is a prime other than $11,73,$ and $137,x \ge 2,q=1$ or (a product of) some other prime(s). So $\overline{abbaabba}$ has at least $(1+1)(1+1)(1+1)(2+1)=24$ divisors.

Case 5: $91a+10b=p^xq^yr$ , where $p,q$ are primes other than $11,73,$ and $137,x,y \ge 1,r=1$ or (a product of) some other prime(s). So $\overline{abbaabba}$ has at least $(1+1)(1+1)(1+1)(1+1)(1+1)=32$ divisors.

In all cases, $\overline{abbaabba}$ has at least $16$ divisors. whew :)

Calvin Lin Staff - 7 years ago

Anoopam Mishra
May 20, 2014

I think the answer is 4. If you take a and b = 1, then the number is 11111111. 11111111 = 11 73 101*137.

Comments and replies:

Calvin: Note that 1 and 11111111 are divisors of 11111111. The question asks for the minimum number of divisors, not the minimum number of prime divisors.

You do raise a good question: What is the minimum number of prime divisors for the 8-digit number $\overline{abbaabba}$ , where $a$ and $b$ are integers from 1 to 9?

Anoopam:

brilliant can you tell whats the correct answer, i hope that my answer is right

Calvin:

Anoopam, I never tell if a stated numerical answer is correct, since it could have been a random lucky guess. I won't want students to keep on asking 'Is 1 the correct answer? Is 2 the correct answer? Is 3 the correct answer? ...' Also, it is possible that your numerical answer is correct, while your reasoning behind it is wrong. I would much rather have you explain your steps. If you display your working, I'd look over it and point out areas that I agree/disagree with.

I asked you to differentiate between the minimum number of divisors and the minimum number of prime divisors. If you read the blog post on Divisors of an integer, you would understand that the number 11111111=11 73 101*137 would have (1+1)(1+1)(1+1)(1+1)=16 divisors, and not 4 as you claimed. So, your reasoning for the answer of 4 would be invalid. (That's not to say that 4 is not the correct answer).

Anoopam:

ok i now understood the difference between minimum number of divisors and the minimum number of prime divisors. so according to me the answer is 16. procedure is the same as you have told. is it correct? if not please give the numerical answer. also, i have guessed the answer so there is no point of explaining how i arrived at this solution.

Calvin:

I do not state whether a given numerical answer is correct or wrong, much less reveal what it actually is, as there is no learning opportunity from that process. If you want, you can pretend that I told you that 16 is wrong, what are you going to do next? And then also pretend that I told you that 16 is correct, what are you going to do next? Do both of those things.

I'd rather have the students work on it, discuss what they are doing and why, and see how they can improve their solution. Take a look at Rishav's posts as an example.

All you have given is an example. So your conclusion would be that the minimum is at most 16. Work on a solution (that is not simply a guess) and we can discuss it.

Anoopam:

abbaabba = 10001 * abba = 73 * 137 * abba abba = 1000a + 100b + 10b + a = 1001a + 110b = 11(91a + 10b) 91a + 10b is a prime number. abbaabba = 73 * 137 * 11 * (91a + 10b). Hence, there are 4 prime factors of abbaabba. The minimum number of divisors are 16.

Calvin:

Why must 91a+10b be a prime number? For example, it need not be prime if a=10 and b = 91.

Anoopam:

We are talking about the minimum number of divisors so if we put a=1 and b=1, then it will equal to 101. 101 is a prime number. If we put a=10 and b=91 it will give a value of 1820 which is a composite number. But we are talking of the minimum number of divisors, so we can put any value of a and b which gives a prime number so that it will give a total of 16 divisors.

Calvin:

Why must the minimum occur when 91a+10b is a prime? Why can't it occur when 91a+10b is a composite number? Look at what Rishav has been doing. He's still missing (at least) a case though.

Anoopam:

The numbers a and b are numbers from 1 to 9, so there is no possibility that they are equal to 10 and 91. And if there are numbers from 1 to 9 the number 91a+10b is surely a prime number, as i think. I can't think of another way of getting the divisors as you said. I am giving up can you tell the answer or give a hint atleast.

Calvin Lin Staff - 7 years ago

Clarence Chew
May 20, 2014

abbaabba has obvious divisors 10001 and 11, both prime. Dividing by these give a 91+b 10 When a=1, b=3, we get an extra 2 divisors of 11. Thus 13311331=11^3*10001 Thus it has 8 divisors at least, with the above construction.

To show it has at least 8 divisors, we note that there must be at least 4 divisors to start with, since it is divisible by 110011.

If a 91+b 10 has extra divisors besides 11 and 10001, we are done. Else, it must have 2 divisors of 11, and we are also done.

Comments and replies:

Calvin:

Clarence, can you explain why 10001 is prime? Note that Anoopam (whose post your thread is nested in) has stated that 11111111=11 73 101*137

Calvin Lin Staff - 7 years ago

Kumar Ashutosh
May 20, 2014

I think the answer is 6. abbaabba is divisible is 11 because difference of the sum of digits at alternate places is 0 (abbaabba - (a+b+a+b) - (a+b+a+b) = 0. Further abbaabba = abba x 10000 +abba = abba x 10001. Therefore the 6 factors of abbaabba are: 1, 11, 10001, abbaabba, abbaabba/11, abba. That's it

Comments and replies:

Calvin:

Your first sentence should be that the alternating sum of digits is a multiple of 11 (not just 0).

How do you know that 10001 is prime?

Since $\gcd(11, 10001)=1$ , if 11 and 10001 divides the number, then so would $11 \times 10001 = 110011$ .

Calvin Lin Staff - 7 years ago

Minimum Number of Divisors

The answer is 16.

7 solutions

Since gcd ⁡ ( 11 , 10001 ) = 1 \gcd(11, 10001)=1 g cd ( 1 1 , 1 0 0 0 1 ) = 1 , if 11 and 10001 divides the number, then so would 11 × 10001 = 110011 11 \times 10001 = 110011 1 1 × 1 0 0 0 1 = 1 1 0 0 1 1 .

0 pending reports

Since $\gcd(11, 10001)=1$ , if 11 and 10001 divides the number, then so would $11 \times 10001 = 110011$ .