# Thread: A prime factor problem.

1. ## A prime factor problem.

A certain integer has only two distinct prime factors. The number of its divisors is 6, and the sum of its divisors is 28. The integer is?

2. Originally Posted by Incognitoi
A certain integer has only two distinct prime factors. The number of its divisors is 6, and the sum of its divisors is 28. The integer is?
By trial and error, the divisors are 5, 5, 5, 5, 5, 3. So, the integer is 5x5x5x5x5x3=9375.

3. Originally Posted by alexmahone
By trial and error, the divisors are 5, 5, 5, 5, 5, 3. So, the integer is 5x5x5x5x5x3=9375.
Thanks for the reply. To be frank, i was already aware of the trial & error method. A much concrete method(if it exists) would be much appreciated.

4. Originally Posted by Incognitoi
A certain integer has only two distinct prime factors. The number of its divisors is 6, and the sum of its divisors is 28. The integer is?
Ugh. I just had this whole thing typed in and lost it. Ah well.

I have a systematic way of solving the problem, but I admit that it's long and trial and error is much shorter. Here it is, briefly. You can easily fill in the steps.

We want to find a z such that z = (x^a)(y^b) where x and y are distinct primes, a and b are positive integers such that a + b = 6, and ax + by = 28.

We can say that b = 6 - a, so the second condition becomes ax + (6 - a)y = 28. We need to solve this equation.

First note that, according to the problem statement x and y are interchangeable. Let's start then, by letting x = 2. When we do this we run into a contradiction. So x is not 2 and since x and y are interchangeable, neither is y.

So x and y are both (distinct) odd primes.

Now, since ax + (6 - a)y = 28 either ax and (6 - a)y are both even or they are both odd.

Assume ax and (6 - a)y are both even. Then a must be even since x and y are odd. Let a = 2n. Then n = 1 or n = 2. Both cases create a contradiction, so ax and (6 - a)y both cannot be even.

So ax and (6 - a)y must both be odd. Thus a is odd. Let a = 2n - 1. Then n = 1, 2, or 3. Since x and y are interchangeable n = 1 and n = 2 both provide the same result. n = 3 gives a contradiction. Thus let n = 1. So we (finally) have that x + 5y = 28.

Now, x and y are distinct primes, not equal to 2. Thus x = 3, y = 5; x = 5, y = 7; x = 3, y = 7, etc. Of these only x = 3, y = 5 can be a solution since all other possibilities give x + 5y > 28.

Thus the only solution is x = 3, y = 5 and since n = 1 we know that a = 1 and b = 5, which gives z = (3^1)(5^5) = 9375.

One would hope for a shorter solution method....

-Dan

5. But 9375 has 12 divisors. We should be looking for an integer of the form p^2q where p and q are distinct primes. That's how I would interpret it at least. Since the factors add up to a small number, it's not hard to find p and q.

6. Originally Posted by LoblawsLawBlog
But 9375 has 12 divisors. We should be looking for an integer of the form p^2q where p and q are distinct primes. That's how I would interpret it at least. Since the factors add up to a small number, it's not hard to find p and q.
Oooh! Good catch.

-Dan

7. Originally Posted by LoblawsLawBlog
But 9375 has 12 divisors. We should be looking for an integer of the form p^2q where p and q are distinct primes. That's how I would interpret it at least. Since the factors add up to a small number, it's not hard to find p and q.
$1+p+q+pq+p^2+p^2q=28$

$1+p+p^2+q(1+p+p^2)=28$

$(1+p+p^2)(1+q)=28$

By inspection $p=2$ and $q=3$

$n=2^2 \times 3=12$

PS: This means that posts #2 and #4 are incorrect.

8. Originally Posted by topsquark
Ugh. I just had this whole thing typed in and lost it. Ah well.

I have a systematic way of solving the problem, but I admit that it's long and trial and error is much shorter. Here it is, briefly. You can easily fill in the steps.

We want to find a z such that z = (x^a)(y^b) where x and y are distinct primes, a and b are positive integers such that a + b = 6, and ax + by = 28.

why $a+b=6$. shouldn't it be $(a+1)(b+1)=6$. also why is the expression for the sum of divisors ax+by. i guess it should be product of two geometric series?? .

We can say that b = 6 - a, so the second condition becomes ax + (6 - a)y = 28. We need to solve this equation.

First note that, according to the problem statement x and y are interchangeable. Let's start then, by letting x = 2. When we do this we run into a contradiction. So x is not 2 and since x and y are interchangeable, neither is y.

So x and y are both (distinct) odd primes.

Now, since ax + (6 - a)y = 28 either ax and (6 - a)y are both even or they are both odd.

Assume ax and (6 - a)y are both even. Then a must be even since x and y are odd. Let a = 2n. Then n = 1 or n = 2. Both cases create a contradiction, so ax and (6 - a)y both cannot be even.

So ax and (6 - a)y must both be odd. Thus a is odd. Let a = 2n - 1. Then n = 1, 2, or 3. Since x and y are interchangeable n = 1 and n = 2 both provide the same result. n = 3 gives a contradiction. Thus let n = 1. So we (finally) have that x + 5y = 28.

Now, x and y are distinct primes, not equal to 2. Thus x = 3, y = 5; x = 5, y = 7; x = 3, y = 7, etc. Of these only x = 3, y = 5 can be a solution since all other possibilities give x + 5y > 28.

Thus the only solution is x = 3, y = 5 and since n = 1 we know that a = 1 and b = 5, which gives z = (3^1)(5^5) = 9375.

One would hope for a shorter solution method....

-Dan
am i mistaken?

9. why . shouldn't it be . also why is the expression for the sum of divisors ax+by. i guess it should be product of two geometric series?? .
I was under the mistaken impression (as was the OP it seems) that the number of factors of z was the sum of each factor of the form p*p*p*p*q*q, say. Which is 6. As LoblawsLawBlog pointed out, this is a mistake.

-Dan