# Number of factors proof

Let n be a natural number with d(n) = 33 (number of factors are 33)

How would I prove that n and n + 1 don't have a common factor > 1?

-
I am curious, what motivated this question? –  Jonas Meyer Oct 18 '10 at 1:40
challenge questions in the back of number theory textbook –  fmunshi Oct 18 '10 at 1:42
Which book is this? I am very curious to see the book which poses such a question as a challenge question. –  Aryabhata Oct 18 '10 at 13:33

The first thing you would do is ignore the information that $d(n)=33$, because it is completely irrelevant.

HINT: Any common factor of $a$ and $b$ divides $a-b$.

-
so if I let a = n+1 and b = n then a-b = 1 and then how would I proceed? –  fmunshi Oct 18 '10 at 1:40
@fmunshi: You would dedicate at least 5 seconds to thinking about it! What divides 1? –  Arturo Magidin Oct 18 '10 at 1:44
I figured this one out. –  fmunshi Oct 18 '10 at 2:22
I appreciate your humor. –  mixedmath Jun 26 '11 at 22:37

fmunshi: I read the problem as proving that any 2 successive integers in the sequence of integers that each have 33 factors are coprime. Such a sequence of n could be represented as n1, n2, n3, n4, ..., ni. The difference between any pair of successive n would not necessarily be 1. i.e. n4-n3 does not likely equal 1.

If this interpretation is correct, the problem is not so trivial.

-
So do you know what text this comes from? –  Pete L. Clark Jun 12 '11 at 14:22
No, but I wish I did. I'd like to see some of the other challenge questions –  Leonard West Jun 16 '11 at 22:25

I make the following assumptions:

1) Set of positive integers.

2) Factors means all divisors including 1 and n.

3) All n is the set of positive integers satisfying d(n) = 33

4) That what fmunshi meant to say was $\; \; n_{i}\; \; and\; \; n_{i+1}\; \;$have no common factors

The number of divisors that n has is dependent entirely on the prime factorization of n. Every multiplicative combination of these primes will divide n and must be counted. The value of the primes does not make any difference, only how many different primes and the powers they are raised to. The problem therefore resulted in a short computer search the results of which are as follows:

$n= P_{1}^{10}P_{2}^{2}$

$n= P_{1}^{32}$

are the only prime decompositions that yield 33 divisors for n.

the smallest of the second form is $\; \; n= 2^{32}= 4,294,967,296$

the first form yields the smallest n as follows:

$n_{1}= 2^{10}3^{2}= 9,216$

$n_{2}= 2^{10}5^{2}= 25,600$

These are 2 successive n in the sequence and 2 is obviously a common factor, so the original conjecture that they don't have a common factor is false.

A very interesting discovery while doing the combinations search for the above is that the conjecture is true for all d(n)=prime, for all primes from 2 through 37 (my search stopped at 37). All n satisfying d(n)=prime are of the second form, so each successive n in the sequence (in fact all n in each sequence) are relatively prime. As an example, if the question had said d(n)=31, the only n with 31 divisors are

$n_{1}= 2^{30}$

$n_{2}= 3^{30}$

$n_{3}= 5^{30}$

$n_{4}= 7^{30}$

.

.

.

$n_{i}= P_{i}^{30}$

$Also, for\; \; d(n)\neq prime$

there were always composite representations for n with more than 1 prime. In other words, if n had prime factorization with more than 1 distinct prime, then the number of divisors d(n) was not prime. Once again, the search and therefore this result is only tested through d(n)=38.

-
If $n=p_1^{a_1}\cdots p_n^{a_n}$ is a prime factorization of $n$, with $p_i\neq p_j$ for $i\neq j$, then the number of divisors of $n$ is exactly $(a_1+1)(a_2+1)\cdots(a_n+1)$. In particular, if $n\gt 1$ and $a_i\gt 0$ for all $i$, then the number of divisors cannot be prime, since its a product of at least two positive integers greater than $1$. –  Arturo Magidin Jun 26 '11 at 22:35
Thanks Arturo - Yes, I thought there must a quick formula for calculating the number of divisors. That formula adds credence to the combinatorial search by computer, and that 9,216 and 25,600 are the first 2 in the sequence for d(n)=33. I wouldn't have used n in your formula though, since it is not the same n as used in d(n)=33 and can be confusing. –  Leonard West Jun 27 '11 at 2:32
It ($n$) shouldn't play the role of both the number and the index, but one can only edit comments during the first five minutes. Better to say $n=p_1^{a_1}\cdots p_k^{a_k}$, and if $k\gt 1$ and $a_i\gt 0$ then... Since $33=3\times 11$, the only ways to get $d(n)=33$ is with $k=2$, $a_1=2$, and $a_2=10$; or $k=2$, $a_1=10$, and $a_2=2$; or $k=1$ and $a_1=32$. Then it's just a matter of comparing $2^{32}$ and $2^{10}3^2$ to see which one is smaller if you want the smallest $n$. –  Arturo Magidin Jun 27 '11 at 3:23
@Arturo: I agree 100%, but I wasn't necessarily looking for the smallest n, I was looking for 2 successive n. The 2 smallest were the easiest to do that. I did look up the formula you gave for the exact number of divisors, and I found a derivation for it in my copy of Courant and Robbins "What Is Mathematics". I wish I'd done that in the first place since it makes this question rather easy and straightforward to analyze. –  Leonard West Jun 28 '11 at 0:20