# Large integer help

The integer

$5685858885855807765856785858569666876865656567858576786786785^{22}$

has 6436343 divisors. Using only a scientific calculator, find a way to show it has exactly 5 prime divisors.

-

Calling $5685858885855807765856785858569666876865656567858576786786785$ as $n$, we have that $n^{22}$ has $6436343$ divisors. Let $n = p_1^{a_1}p_2^{a_2} \ldots p_k^{a_k}$, where $p_j$ are primes and $a_j \in \mathbb{Z}^+$. Then $$n^{22} = p_1^{22a_1}p_2^{22a_2} \ldots p_k^{22a_k}$$ Hence, the number of divisors is $$(1+22a_1)(1+22a_2)\cdots(1+22a_k) = 6436343 = 23^5$$ Hence, we get that $\require{enclose} \enclose{horizontalstrike}{k=5}$ and $\require{enclose} \enclose{horizontalstrike}{a_1 = a_2 = a_3 = a_4 = a_5 = 1}$. Hence, we get that $$\require{enclose} \enclose{horizontalstrike}{5685858885855807765856785858569666876865656567858576786786785 = p_1 p_2 p_3 p_4 p_5}$$ By adding the digits, we find that $3$ doesn't divide $n$. Hence, $p_1 = 5$.

The actual prime factorization (obtained using Wolframalpha) is $$5 \times 13 \times 647 \times 25414873859387 \times 5319740909859534399143659720463597175586901$$

EDIT

A good point was raised by Mike in his comments. If we have $$(1+22a_1)(1+22a_2)\cdots(1+22a_k) = 23^5$$ This only implies $k \leq 5$. We also know that $k \geq 2$, since $5 \vert n$. So the answer is incomplete.

EDIT

Some more updates after some very insightful comments from Mike, Henry and Pambos. Let us assume that we can use divisibility rules to check divisibility up-to $13$ and divide $n$ by numbers up-to $13$. Note that $5 \vert n$ and $13 \vert n$. Hence, $n = 65 \times m$. Let $m = \prod_{j=1}^k p_j^{a_j}$. Hence, we get that $23 \times 23 \times \prod_{j=1}^k (1+22a_j) = 23^5 \implies \prod_{j=1}^k (1+22a_j) = 23^3$. Hence, the number of distinct primes in $m$ can be at most $3$. We want to show that the number of distinct primes dividing $m$ is exactly $3$.

Case $1$: $m$ is a perfect prime power i.e. $m = p^a$ where $p\geq 17$. This means we have $(1+22a) = 23^3 \implies a = \dfrac{23^3-1}{22} = 553$. But the number $m$ is only $59$ digits long. But then $p^{553} \geq 17^{553}$ is more than $500$ digits long. Hence, not possible. This means that the number of distinct primes dividing $m$ is either $2$ or $3$.

Case $2$: $m$ is of the form $m=p_1^{a_1} p_2^{a_2}$. In this case, we have $$(1+22a_1)(1+22a_2) = 23^3$$ Without loss of generality, let us take $a_1 = 1$ and $a_2 = 24$ i.e. $m = p_1 p_2^{24}$.

$$p_2^{8} \equiv 1 \pmod{2^5}$$ $$p_2^{6} \equiv 1 \pmod{3^2}$$ $$p_2^{4} \equiv 1 \pmod{5^1}$$ $$p_2^{6} \equiv 1 \pmod{7^1}$$ $$p_2^{12} \equiv 1 \pmod{13^1}$$ Hence, we get that $$p_2^{24} \equiv 1 \pmod{131040}$$ But we have $m \equiv 74369 \pmod{131040}$. (Note that I have assumed that we have divisibility rules up-to $13$. Divisibility by $2^5$ is trivial since all we need to check is if the last $5$ digits of $m$ is divisible by $2^5$.)

This means $p_1 \equiv 74369 \pmod{131040}$. This gives us $p_2 < p_1$ and hence $p_2^{24} < 10^{54} \implies p_2 < 10^{0.25} 10^{2} < 178$.

-
That's extraordinary. I was just typing up a far inferior response. +1 –  mixedmath Dec 26 '12 at 5:14
@Ethan I'm not sure "lol" makes much sense in this context. –  Alex Becker Dec 26 '12 at 5:18
Ethan uses lol like Jasper uses QED. I think it's a personal catchphrase or something. –  anon Dec 26 '12 at 5:19
@Mike: The numbers $5\cdot17^{24}\cdot19^{24}$ and $5\cdot7\cdot11\cdot251^{24}$ have $61$ digits. –  P.. Dec 26 '12 at 9:04
@Marvis: Also you can eliminate the case $k=3$ if you look $\pmod {10}$. Easily $5 \mid n$ and $25 \nmid n$. So in case $k=3$ necessarily $n=5\cdot p^{24}\cdot q^{24}$ for some primes $p,q$. The last digit of $\frac{n}{5}$ is $7$ but $1^{24}, \ 3^{24}, \ 7^{24}, \ 9^{24} \equiv 1 \pmod {10}$. –  P.. Dec 26 '12 at 18:23
show 21 more comments

Im not really answering my own question, but its to large to put in a comment, I was thinking of using the fact that $$\lim_{s\to\infty}\frac{\ln(d(k^s))}{\ln(1+s)}=\text{number of prime divisors k has}$$ $d(k)=$ number of divisors of $k$

And then using the fact $s$ is very large, I could say $$\frac{\ln(d(k^{22}))}{\ln(23)}\sim \text{number of prime divisors k has}$$ It gives me $5$ also, but this isn't really a proof, it works with $s=2$, also btw.

Also I was just experimenting it looks like $\dfrac{\ln(d(k))}{\ln(2)}=$ (number of prime diviors of $k$) very often.

-