19
$\begingroup$

The integer

$5685858885855807765856785858569666876865656567858576786786785^{22}$

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

2 Answers 2

31

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$.

  • 1
    That's extraordinary. I was just typing up a far inferior response. +12012-12-26
  • 0
    Very nice one lol2012-12-26
  • 2
    @Ethan I'm not sure "lol" makes much sense in this context.2012-12-26
  • 2
    Ethan uses lol like Jasper uses QED. I think it's a personal catchphrase or something.2012-12-26
  • 0
    Marvis how did you know it was the 23^5, did you type that in on wolfram alpha and did it list it as an alternative representation? Amazing fast answer though2012-12-26
  • 0
    @Ethan Yes, I used WA to get the prime factorization of $6436343 $ and was pleasantly surprised to find that it was $23^5$. However, I think you could easily obtain the factorization using some simple divisibility rules or using your calculator as well.2012-12-26
  • 0
    Dumb question. Without factoring $n$, does this show that it can't have less than 5 factors? For example, does anything prevent $k=4,a_1=a_2=a_3=1,a_4=24?$2012-12-26
  • 0
    @Mike Do you mean $n$ or the number of divisors?2012-12-26
  • 0
    Amazing answer though2012-12-26
  • 0
    @marvis I meant using $6436343=23^5$, without explicitly factoring $n$ out as you had done at the end.2012-12-26
  • 0
    @Mike Valid point. Yes. $\prod_{m=1}^k (1+a_m) = 23^5 \implies k \leq 5$. Hence, we only get $k \in \{2,3,4,5\}$. Currently, I do not have an immediate way to conclude that $k$ has to be indeed $5$. Do you have an easy way out?2012-12-26
  • 0
    @Marvis I wish I did. The number is certainly long enough to have a single prime factor repeated several times.2012-12-26
  • 0
    @Mike: Can you explain "The number is certainly long enough to have a single prime factor repeated several times" please?2012-12-26
  • 0
    @pambos I count $61$ digits in $n$. $5\times7^{24}\times11^{24}$ has only $46$. That number to the 22nd power would also have $23^5$ factors. If you consider just one prime factor to the 24th power, a 61 digit number is still more than big enough to be divisible by some quite sizable prime numbers.2012-12-26
  • 1
    @Mike: The numbers $5\cdot17^{24}\cdot19^{24}$ and $5\cdot7\cdot11\cdot251^{24}$ have $61$ digits.2012-12-26
  • 1
    @Mavis: You can reject $k=2$ since $2^{(23^3-1)/22}=2^{553} \gt 10^{166}$ and $2^{(23^4-1)/22}$ is even bigger.2012-12-26
  • 2
    @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}$.2012-12-26
  • 0
    @pambos Very nice. That still leaves one case left to disprove though.2012-12-26
  • 0
    @Pambos - Just beat me to it! It's just Fermat's Little Theorem.2012-12-26
  • 0
    @Pambos Nice. Note that $k=3$ can also have a decomposition of the form $5pq^{553}$. But yes, $q^{553} > 10^{61}$ even for $q=2$. Hence, it can be ruled out. Nice Pambos.2012-12-26
  • 0
    @Henry Yes. Neat. A very nice collaborative proof in progress :).2012-12-26
  • 0
    Theres a $\frac{6}{\pi^2}=.607927..$ chance that the number of prime divisors of k is equal to $\frac{ln(d(k))}{ln(2)}$2012-12-26
  • 0
    @Ethan $\omega(n)$ has mean and variance $\ln(\ln(n)) \approx 8.03192$. Hence, the probability that $k \leq 4$ is approximately $0.0775$.2012-12-26
  • 0
    What do you mean? if d(k) is square free its equal to $2^{\omega(k)}$, therefore $\frac{ln(d(k)}{ln(2)}=\omega(k)$ when k is square free, and the asymptotic probability of any integer being square free is $\frac{6}{\pi^2}$2012-12-26
  • 0
    @Ethan We do not know that $n$ is square free yet. If $n$ is square free, then we can immediately conclude that $n=p_1p_2p_3p_4p_5$. What I meant is the asymptotic for $\omega(n)$ goes as $\ln \ln n$ and with variance $\ln \ln n$. See equation $3$ and $5$. http://mathworld.wolfram.com/DistinctPrimeFactors.html2012-12-26
  • 0
    @Ethan A better asymptotic as the above link shows is $\omega(n) \sim \ln \ln n + 0.2615$ with variance $\ln \ln n - 1.8357$. For our case, this gives us $\omega(n) \approx 8.2934$, and variance is $6.19622$. Hence, $\mathbb{P}(\omega(n) \leq 4) = \mathbb{P}(z \leq \dfrac{-4.2934}{2.489}) = 0.0423$. But $\mathbb{P}(\omega(n) \leq 5) = \mathbb{P}(z \leq \dfrac{-3.2934}{2.489}) = 0.0923$ and $\mathbb{P}(\omega(n) \leq 3) = \mathbb{P}(z \leq \dfrac{-5.2934}{2.489}) = 0.017$. Hence, given that the number of prime factors is either $4$ or $5$, the probability it is $4$ is approximately $0.327$.2012-12-26
5

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.