work it out

[rust8y]

(a) Find all positive integers N such that the product 2005 x N has exactly 6 divisors.

 

(b) Find all composite integers M such that the product 2005 x M has exactly 8 divisors.

[Algebracus]

2005 = 5*401, both 5 and 401 being primes. A number p^v*q^b*r^n*... (standard prime factorization with uncommon notation) have (v + 1)(b + 1)(n + 1) divisors. We are seeking 6 = 2*3 (a*b*..., a,b,... > 1) divisors, so N = 5 or 401. (2005 itself has 4 divisors, 1, 5, 401 and 2005, and we shall only add two new divisors; in the case N = 5 we add 10025 and 25.)

 

8 = 4*2 = 2*2*2, so M can be 5^2 or 401^2 (all primes would also work, if it was not for the restriction of M being composite).

 

 

Here is a similar one:

Find the integer M with lowest abosulte value |M| such that there exists a positive integer N so that 2005N has exactly N + M divisors and for the given M, find the lowest N so that 2005N has exactly N + M divisors.

[huneynumb]

But what do you mean by "A number p^v*q^b*r^n*... (standard prime factorization with uncommon notation) have (v + 1)(b + 1)(n + 1) divisors. We are seeking 6 = 2*3 (a*b*..., a,b,... > 1) divisors" and how did you get the answers

[BigMoosie]

I'd suggest iteration

[Algebracus]

1: I was assuming positive divisors, but the wording "divisors" does not prohibit negative divisors. The reason of my assumption were merely based upon the fact that if we allow for negative divisors, the answers to the problem become very trivial; 2005N surely has the divisors -1, 1, 5, -5, 2005, - 2005, 401 and -401, 8 there is, and if N is not +/- 1, then the number possibly have more. So the answers are: (a) No such N exists, (b) M = 1 og M = -1.

 

2: Let's go on with positive divisors, and the formula for the numbers of positive divisors of a given natural number. There are several ways of finding the formula, I would better suppose a combinatorical argument and/or induction. Let d(N) be the number of positive divisors of N. Then:

 

N = 1 has exactly 1 positive divisor.

 

N = p^f, p a prime and f a natural number, has exactly (f + 1) positive divisors; 1, p, p^2, ..., p^f.

 

N = p^f*M, gcd(M,p^f) = 1, has exactly (f + 1)d(M) divisors: A divisor of N is p^g*M', M' a divisor of N. We can choose this in (f + 1)d(M) different ways; (f + 1) choices of g, d(M) choices of M', and no two choices give the same divisor, since p^g and M' are relatively prime.

 

The formula then must be

[MATH]d(\prod_{i = 1}^{n} p^{e_i}_i) = \prod_{i = 1}^{n} (e_i + 1)[/MATH]

 

How I got the answers? By finding the exponentials of 2005N and 2005M, respectively (what was the options??). Let's look at the latter case of finding M: We have [MATH]\prod_{i = 1}^{n} (e_i + 1) = 8 = 2^3[/MATH]. Now, 8 = 2*2*2 = 4*2 = 8*1, that is, e_1 = e_2 = e_3 = 1 or e_1 = 3, e_2 = 1 or e_1 = 7, all other exponents being zero. The first one gives threee single prime factors, but then M is a prime, that is, not composite. The third one gives p^7 = 2005M, surely not true for any prime p. So the second is the only one working, namely, 2005M = p^3*q for some primes p and q. Now, 2005 = 5*401, so p and q must be 5 and 401, that is 2005M = 5^3*401 or 2005M = 401^3*5, that is, M = 5^2 or 401^2. Got it?

 

 

I better give some hints for the problem I posed, since noone seems to bother about it right now:

Find all (I originally wrote 'the', but it possibly is two) integer M with lowest absolute value |M| such that there exists a positive integer N so that 2005N has exactly N + M divisors, and for such M, find the lowest possible N + M.

 

Hint 1: What about the case M = 1, N = 5?

Hint 2: For M = 0, does such an N exist. Suppose it does, in which cases do you get a contradiction, and in which cases does such an N exist (if in any)? Mere to say, a start would be:

 

Suppose p is a prime and e a non-negative integer. Then

(i) [MATH]p^e \geq e + 1[/MATH] with equality for p = 2, e = 1 or for e = 0.

(ii) [MATH]p^e \geq e + 2[/MATH] if p > 2 and e > 0, with equality for p = 3, e = 1.

(iii) [MATH]p^e \leq 2(e + 2)[/MATH] for p > 4 only if p = 5 and e = 0 or 1.

(iv) [MATH]p^e \leq 4(e + 1)[/MATH] only if p = 2, 0 < e < 5 or if p = 3, 0 < e < 4.

I will not give any proofs; they are easy and only based upon the simple fact that the left hand side grows faster than the right hand side.

 

And, for the case of M = 0,

(a) N = 5^f * 401^g * M, gcd(M,2005) = 1, f > 0, g > 0. Then d(2005N) = (f + 2)(g + 2)d(M) = N = 5^f * 401^g * M > (f + 2)(g + 2)d(M), a contradiction.

(b) N = 5^f * M, gcd(M,2005) = 1, f > 1. Then d(2005N) = 2(f + 2)d(M) = N = 5^f * M > (f + 2)d(M), a contradiction.

© N = 5M, gcd(M,2005) = 1. Then d(2005N) = 6d(M) = 5M. What next?

(d) N = 401^f * M, gcd(M,2005) = 1, f > 0. Then d(2005N) = 2(f + 2)d(M) = N = 401^f * M > (f + 2)d(M), a contradiction.

(e) gcd(N,2005) = 1. Then d(2005N) = 4d(N) = N. What next? For which N does we surely get a contradiction? What N are the "left-overs".

 

I must admit, making a computer program would be the simplest way of solving the problem; everything I have written it typically brute-force-methodic.