Must Have A Lot Of Factors

Let $n=p_1^{a_1} p_2^{a_2} \ldots p_k^{a_k}$ . If $a=p_i^{a_i}$ is the smallest prime power dividing $n$ (Given that $p_i^{a_i} \mid \mid n$ ), then $b=\dfrac {n}{p_i^{a_i}}$ . Note that these two numbers are co-prime. Thus, we have

$\begin{aligned} p_i^{a_i} + \dfrac {n}{p_i^{a_i}} - 1 &\mid n\\ p_i^{a_i} + \dfrac {n}{p_i^{a_i}} - 1 &\mid p_i^{a_i}\left ( p_i^{a_i} + \dfrac {n}{p_i^{a_i}} - 1 \right )\\ \implies p_i^{a_i} + \dfrac {n}{p_i^{a_i}} - 1 &\mid p_i^{2a_i} + n - p_i^{a_i}\\ \implies p_i^{a_i} + \dfrac {n}{p_i^{a_i}} - 1 &\mid p_i^{2a_i} - p_i^{a_i}\\ \implies p_i^{a_i} + \dfrac {n}{p_i^{a_i}} - 1 &\leq p_i^{2a_i} - p_i^{a_i}\\ \implies \dfrac {n}{p_i^{a_i}} &\leq (p_i^{a_i}-1)^2 \end{aligned}$

If $n$ has three or more prime factors, choose 2 prime powers distinct from $p_i^{a_i}$ (Call these two powers $p_x^{a_x}$ and $p_y^{a_y}$ .) We get the following:

$p_x^{a_x} p_y^{a_y} \leq \dfrac {n}{p_i^{a_i}} \leq (p_i^{a_i}-1)^2 < p_x^{a_x} p_y^{a_y}$

This is a contradiction, so $n$ has at most 2 prime factors.

Let $n=p_1^{a_1} p_2^{a_2}$ . WLOG $p_1 < p_2$ . We have as follows:

$\begin{aligned} p_1 + p_2 - 1 &\mid n\\ \implies 1+\dfrac {p_2-1}{p_1} &\mid p_1^{a_1-1}p_2^{a_2}\\ \implies p_1 &\mid p_2 - 1\\ \implies p_2 - 1 &= kp_1^x \end{aligned}$

where $p_1^x \mid \mid p_2-1$ . We will now consider three cases:

Case 1: $a_1 > 1$

Let $a=p_1^2$ , and $b=p_2$ . We have:

$\begin{aligned} p_1^2 + p_2 - 1 &\mid n\\ \implies p_1^2 + kp_1^x &\mid n\\ \implies p_1^2(1+kp_1^{x-2}) &\mid n \quad \text{ if } x \geq 2\\ \implies p_2 \mid 1+kp_1^{x-2} &\mid \dfrac {n}{p_1^2} \quad \text{since gcd}(p_1, 1+kp_1^{x-2})=1\\ \implies 1+kp_1^x \mid 1+kp_1^{x-2} &\mid \dfrac {n}{p_1^2} \end{aligned}$

Which is a contradiction. Thus, $x=1$ . From this, we get

$\begin{aligned} p_1^2 + kp_1 &\mid n\\ \implies p_1+k &\mid n\\ \implies p_2 &\mid p_1 + k \mid n\\ \implies kp_1 + 1 &\mid p_1 + k\\ \implies kp_1 + 1 &\leq p_1 + k\\ \implies kp_1 -k - p_1 + 1 &\leq 0\\ \implies (k-1)(p_1-1) &\leq 0\\ \implies k&=1\\ \implies p_1=2&, p_2=3\\ \implies n=2^c 3^d\\ \implies 2+3-1 \mid n\\ \implies 4 \mid n \end{aligned}$

If $c \geq 3$ , $8+3-1 \mid n \implies 10 \mid n$ , but $5$ doesn't divide $n$ , which is a contradiction. Thus, $c=2$ . Therefore, $n=4\times 3^d$ . If $d \geq 2$ , $9+2-1 \mid n \implies 10 \mid n$ , but $5$ doesn't divide $n$ . Thus, $d=1$ . Therefore, $n=12$ , which we verify below:

Factors of $12$ are $1, 2, 3, 4, 6, 12$ . Co-prime pairs are $(1, 1)$ , $(1, 2)$ , $(1, 3)$ , $(1, 4)$ , $(1, 6)$ , $(1, 12)$ , $(2, 3)$ , $(3, 4)$ , which yield $a+b-1$ as $1, 2, 3, 4, 6, 12, 4, 6$ respectively, and these are all factors of $12$ as well, so we're done in this case.

Case 2: $n=p_1 p_2^{a_2}$ ( $a_2 \geq 2$ ) or $n=p_1 p_2$ .

If $n=p_1 p_2^{a_2}$ ,

$\begin{aligned} p_1 + p_2^{a_2} - 1 &\mid p_1 p_2^{a_2}\\ \implies \dfrac {p_1 - 1}{p_2^{a_2}} + 1 &\mid p_1\\ \implies p_2^{a_2} &\mid p_1 - 2 \end{aligned}$

But this cannot be true since $p_1 < p_2$ by our WLOG assumption. Thus, $a_2 \not \geq 2$ .

If $n=p_1 p_2$ ,

$\begin{aligned} p_1 + p_2 - 1 &\mid n\\ \implies p_1 + p_2 - 1 &= p_1 p_2\\ \implies p_1 p_2 - p_1 - p_2 + 1 &= 0\\ \implies (p_1-1)(p_2-1) &= 0\\ \end{aligned}$

But this cannot happen as $p_1, p_2 > 1$ . Thus, $n \neq p_1 p_2$ .

Case 3: $n = p^x$

This can be proven to be true. One of $a$ or $b$ must be 1, since all other factors are powers of $p$ . WLOG $a=1$ . Thus, $a+b-1 = b$ , and we already know $b \mid n$ , so we are done. Thus, $n=p^x$ is a solution.

Computing this, we get the number of satisfying solutions under 1000 is 194.

Case 1: $n$ is an odd number

Let $n={a_{1}}^{p_{1}}{a_{2}}^{p_{2}}\cdots{a_{m}}^{p_{m}}$ be the prime factorization of $n$ . We will show that $m \neq 2,3$ .

Suppose that $m=2$ , let $n={a}^{p_{1}}{b}^{p_{2}}$ be the prime factorization of $n$ . We know that $a+b-1={a}^{q_{1}}{b}^{q_{2}}$ , where $0 \leq q_{1} \leq p_{1}, 0 \leq q_{2} \leq p_{2}$ .. We argue that one of $q_{1}$ or $q_{2}=0$ . Suppose this is not the case, then $a |b-1$ and $b |a-1$ . WLOG, let $a>b$ , then this contradicts $a|b-1$ since $b-1=ka \implies b=ka+1>a$ .

Without loss of generality, suppose that ${a}^{q_{1}}, q_{1} > 1$ is a factor of $n$ . Note that both $a^{q_{1}}+b-1$ and ${a}^{q_{1}}$ are factors of $n$ . From $a+b-1={a}^{q_{1}}$ , rearrange to get $b={a}^{q_{1}}+1-a$ . Write ${a}^{q_{1}}+b-1=2{a}^{q_{1}}-a={a}^{r_{1}}{b}^{r_{2}}$ . Note that if both $r_{1}, r_{2} \geq 1$ , then $a|b-1$ and $b|a^{q_{1}}-1$ . Note also that from $2{a}^{q_{1}}-a={a}^{r_{1}}{b}^{r_{2}}$ , we have $2a^{q_{1}}-2+2-a=2(bq)+2-a$ being divisible by $b$ . This implies $b|a-2$ . However, $a|b-1$ implies $b=ka+1>a$ , but $b|a-2$ implies $a=jb+2>b$ . This is clearly a contradiction, hence one of $r_{1}$ or $r_{2}$ must be $0$ . In this case, obviously, $r_{2}=0$ . Division of the equation on both sides by $a$ yields $2a^{q_{1}-1}-1=a^{r_{1}-1}$ . There is only $1$ solution to this equation, that is $q_{1}=k_{1}=1$ . However, this contradicts our assumption that $q_{1}>1$ . Hence, $m \neq 2$ .

Suppose that $m=3$ , let $n=a^{p_{1}}b^{p_{2}}c^{p_{3}}$ be the prime factorization of $n$ , and $a+b-1=kc$ , which follows from above (Since $m \neq 2$ , $a+b-1$ must have odd factors which are not $a$ or $b$ ). Note that $b+c-1$ and $a+c-1$ are also factors of $n$ . Note that $b+c-1$ and $a+c-1$ are both not divisible by $c$ . Suppose for the sake of contradiction that $b+c-1$ is divisible by $c$ , then this implies $b-1$ is divisible by $c$ . However, from $a+b-1=kc$ , this implies $a$ is divisible by $c$ , which is a contradiction. The proof for $a+c-1$ is analogous.

$b+c-1$ must be divisible by $a$ or $b$ if we have $m=3$ . Suppose that $b+c-1$ is divisible by $a$ , then $a+c-1$ is not divisible by $a$ . Suppose that $a+c-1$ is divisible by $a$ , then $c-1$ is divisible by $a$ , and this implies from $b+c-1=ka$ that $b$ is divisible by $a$ , clearly a contradiction. Therefore, we have the following system of equations:

$a+b-1=kc$

$b+c-1=ma$

$a+c-1=nb$

which gives $(m+1)a=(k+1)c=(n+1)b$ . Solving yields $m+1=bce, k+1=abe, n+1=ace$ . Upon substitution back into the original equation, we get $a+b+c=abce+1$ . There is no solution for this equation when $a,b,c \geq 3$ . The proof is left as an exercise to the readers.

Now, if we suppose that $b+c-1$ is divisible by $b$ , then $a+c-1$ is divisible by $a$ . The proof is analogous to the part where we assume $b+c-1$ to be divisible by $a$ . We have the following system of equations:

$a+b-1=kc$

$b+c-1=lb$

$a+c-1=ma$

The system of equations imply that $c-1$ is divisible by both $a$ and $b$ . Write $c=pab+1$ . Substitution into the first equation gives $a+b-1=k(pab+1)=kpab+k$ . However, note that for $a,b \geq 3$ ,

$kpab+k>kpab>ab>a+b>a+b-1$

so there is no solution to the equations above.

Having proven that $m \neq 2,3$ , we proceed to show that $n>1000$ for $m \geq 4$ since $3.5.7.11=1155>1000$ . Therefore, $m=1$ . It is easy to note that any numbers in the form of $n=a^{p_i}$ is indeed cool since the factors of $n$ are $1,a,a^{2} \cdots a^{p_{n}}$ , of which only the pairs of factors $(1,a^{p_{i}})$ meet the criteria of $\gcd(a,b)=1$ . But $a+b-1=1+a^{p_{i}}-1=a^{p_{i}}$ , and these are clearly factors of $n$ .

Case 2: $n$ is an even number.

We neglect the case where $n$ is a power of $2$ , since these are obviously cool numbers. (Proof is analogous to our proof of $n=a^{p_{i}}$ as cool numbers). Therefore, we can assume that $n$ has the factors $2$ and $a$ , where $a$ is odd.

Since $a$ is relatively prime to $2$ , $2a$ is a factor of $n$ as well. By the definition of cool numbers, $a+2-1=a+1$ is a factor as well. Since $a$ is relatively prime to $a+1$ , $a(a+1)$ is also a factor. Therefore, $n$ has the following factors: $1,2,a,1+a,2a, a(a+1)$ .

The family of factors above is closed under the operation of $a+b-1$ as long as $\gcd(a,b)=1$ . This fulfills the condition of cool numbers above as long as the factors of $a+1$ belong to the family above. In particular, since $a+1$ is coprime with $a$ , $a+1$ must only have $2$ as its factor (besides $1$ and itself). This leaves the only possibility, that is $a+1=4 \implies a=3$ . These factors define $n$ as $12$ .

Now, suppose that $a \neq 3$ . If $a+1$ is divisible by odd factors, then we are done. The proof follows from the part where we prove $m \neq 2,3$ . The proof still holds even when $n$ is even, so we can conclude that no such $n$ exists. If $a+1$ is not divisible by any odd factors, it is a power of $2$ . Since $a+1 \neq 4$ , $a+1$ must equal $2^{n}$ , where $n \geq 3$ . Thus, we have the following factors for $n: 1,2,4,8,a,a+1,2a$ .

By definition of cool numbers, $4+a-1=a+3$ and $8+a-1=a+7$ are also factors. Suppose that $\gcd(a,a+3)=\gcd(a,3)=1$ , then this implies $a+3$ is a power of $2$ . Since both $a+1$ and $a+3$ are powers of $2$ , $a=1$ but we know this is not the case. Suppose now that $\gcd(a,a+3)=3 \neq 1$ , then we know $a=3^{n}, n>1$ . Note that $\gcd(a,a+7)=\gcd(a,7)=\gcd(3^{n},7)=1$ , so $a+7$ is not divisible by $3$ , hence a power of $2$ . But now both $a+1$ and $a+7$ are powers of $2$ , which is impossible. Our proof is complete. All cool numbers below $1000$ must be in the form $n=a^{p_{i}}$ with $a$ prime and $p_{i}>0$ , bar the exception of $12$ .

A quick computation (with aid of a list of prime numbers under $1000$ ) shows that there are $\boxed{194}$ such numbers.