# Proof for relation between p-adic valution of the total number of divisors and the sum of multiplicities

The final point $$(9)$$ is the lemma that I am establishing a proof for, all the relevant lemma are there I guess I just need help fine tuning things, Although I have no idea how I will prove $$(10)$$ if indeed it is true for all primes.

Consider the Unique prime factorization of a natural number $$n$$:

$$n=\prod _{j=1}^{\omega \left( n \right) }{p_{{n,j}}}^{\nu_{{n,j}}}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(0)$$

One could, in a heuristic sense, expect that the sum of all sums up to and including the multiplicity of all the distinct prime factors of $$n$$ will have proportion to the total number of divisors of $$n$$ somehow.

So we begin by defining the sum of the multiplicities of the unique prime factors of $$n$$:

$$\Upsilon \left( n \right) =\sum _{j=1}^{\omega \left( n \right) }\nu_{ {n,j}} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(1)$$

$$\sum _{k=1}^{\Upsilon \left( n \right) +1}{\frac { \left( \Upsilon \left( n \right) +1 \right) !}{k!\, \left( \Upsilon \left( n \right) -k+1 \right) !}}=2^{\Upsilon \left( n \right) +1}-1 \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(2)$$

$${\Biggl\{\frac {{2}^{n} \left( {2}^{\Upsilon \left( n \right) +1}-1+{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1}-1,\tau \left( n \right) \right) \right) }{{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad\quad\quad\quad\quad\quad\quad(3)$$

$${\Biggl\{\frac {\tau(n)\left( {2}^{\Upsilon \left( n \right) +1}-1+{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1}-1,\tau \left( n \right) \right) \right) }{2{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad\quad\quad\quad(4)$$

$${\Biggl\{\frac {{2}^{n} }{{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(5)$$

$${\Biggl\{\frac {\tau(n)\left( {2}^{\Upsilon \left( n \right) +1}-1 \right) }{2{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=\frac{1}{2}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(6)$$

$$\exists k \in \mathbb N \land k \gt 1\quad \operatorname{s.t} \sqrt{n}=k \Rightarrow \quad{\Biggl\{\frac {\tau(n)\left({\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) \right) }{2{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1}-1,\tau \left( n \right) \right) }} \Biggr\}=\frac{1}{2}\quad\quad\quad(7)$$

$$\not\exists k \in \mathbb N \land k \gt 1 \quad\operatorname{s.t} \sqrt{n}=k \Rightarrow \quad{\Biggl\{\frac {\tau(n)\left({\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) \right) }{2{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1}-1,\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad(8)$$

$$\exists k \in \mathbb N \land k \gt 1 \quad\operatorname{s.t} \sqrt{n}=k \Rightarrow{\Biggl\{\frac{{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right)}{2}}\Biggr\}=\frac{1}{2}\quad\quad\quad(7\operatorname{i})$$

$$\not\exists k \in \mathbb N \land k \gt 1\quad \operatorname{s.t} \sqrt{n}=k \Rightarrow{\Biggl\{\frac{{\it \gcd} \left( {2}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right)}{2}}\Biggr\}=0\quad\quad\quad(8\operatorname{i})$$

Where $${\{x}\}$$ is the fractional part of $$x$$.

Where $$\tau(n)$$ is the total number of divisors of $$x$$.

The 2-adic valuation of the total number of divisors of $$n$$ can also be expressed in term of the sum of the multiplicities of the unique prime factors of $$n$$:

$$\nu_{{2}} \left( \tau(n) \right)=\frac{\ln(\gcd(2^{\Upsilon \left( n \right)+1},\tau(n)))}{\ln(2)}\quad\quad\quad(9)$$

The generalization to the p-adic valuation of the total number of divisors of $$n$$ also seems to be true: $$\nu_{{p}} \left( \tau(n) \right)=\frac{\ln(\gcd(p^{\Upsilon \left( n \right)+1},\tau(n)))}{\ln(p)}\quad\quad\quad(10)$$

Indeed, the following generalizations to any $$p$$ would appear to be true , giving more substance to the truth value of $$(10)$$,I am too tired to use my talking words tbh:

$${\Biggl\{\frac {\tau(n)\left( {p}^{\Upsilon \left( n \right) +1}-1+{\it \gcd} \left( {p}^{\Upsilon \left( n \right) +1}-1,\tau \left( n \right) \right) \right) }{{\it \gcd} \left( {p}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad\quad\quad\quad(4\operatorname{i})$$

$${\Biggl\{\frac {{p}^{n} }{{\it \gcd} \left( {p}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\}=0\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(5\operatorname{i})$$

$${\Biggl\{\frac {{\it \gcd} \left( {p}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }{{p}^{\Upsilon \left( n \right)-n+1} }} \Biggr\}=0\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad(5\operatorname{ii})$$

$$1 \leq {\frac {\tau(n)\left( {p}^{\Upsilon \left( n \right) +1}-1 \right) }{\gcd\left( {p}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }}-p\Biggl\lfloor {\frac {\tau(n)\left( {p}^{\Upsilon \left( n \right) +1}-1 \right) }{p\gcd\left( {p}^{\Upsilon \left( n \right) +1},\tau \left( n \right) \right) }} \Biggr\rfloor \leq p-1\quad\quad\quad\quad\quad\quad(11)$$

• What you have in mind is unclear, if $n$ is squarefree it simplifies a lot since $\tau(n) = 2^{\omega(n)}$ – reuns Sep 30 '18 at 23:36
• In the case that $n$ is square free yes we have $\Upsilon \left( n \right)=\omega(n)$ you are correct, but I don't understand what you are referring to when you say "it" simplifies, seeing that the relation I have posted the discussion about is for the p-adic valuation for $\tau(n)$, which is obviously going to be equal to $1$ for all $p$ that divide $\tau(n)$ and $0$ for those that don't in the case that $n$ is square free – Adam Sep 30 '18 at 23:56
• Well yes the sum of the multiplicities of the unique prime factors of a number is going to be greater than or equal to the p-adic valuation for any particular prime number, but the fact that this is the total number of divisors I think requires more than that. Also, a divisibility relation cannot be simply justified with an inequality in my opinion, but I'm also not entirely sure of what else I want as proof over and above it – Adam Oct 1 '18 at 0:28
• I think the inequality $(11)$ that I just included into the post now is probably the most important part that needs rigorous proof at this point – Adam Oct 1 '18 at 0:39

Summing up my comments and filling in some gaps:

To show (10) (which includes (9) as a special case):

For any prime $$p$$ and integer $$x$$, by definition of the $$p$$-adic value, we have $$\nu_p(x)=\log_p(\gcd(p^r,x))$$ if and only if $$r$$ is an integer $$\ge \nu_p(x)$$. So equation (10) boils down to the claim that $$\Upsilon(n)+1≥\nu_p(\tau(n))$$ for all $$p$$ and $$n$$.

Now to see this, use that $$\displaystyle \tau(n) = \prod_{j=1}^{\omega(n)} (\nu_{n,j}+1)$$ (according to wikipedia, where $$\tau$$ is called $$\sigma_0$$). So for any $$p$$,

$$\nu_p(\tau(n)) = \sum_{j=1}^{\omega(n)} \nu_p(\nu_{n,j}+1)$$

Now for any integer $$a$$ and prime $$p$$, we have $$\nu_p(a) \le a-1$$, hence we even have the stronger

$$\nu_p(\tau(n)) \le \sum_{j=1}^{\omega(n)} \nu_{n,j} =\Upsilon(n).$$

To show (11):

Calling $$x=$$ the first fraction in (11), and looking at the function $$f(x)=x−p \lfloor x/p\rfloor$$, shows that (11) is equivalent to $$x$$ not being within any of the intervals $$(kp−1,kp+1)$$ with $$k \in \Bbb Z$$. Since the denominator of $$x$$ divides $$\tau(n)$$, the fraction $$x$$ is actually an integer itself, so the claim is equivalent to $$x$$ not being of the form $$kp$$ with $$k \in \Bbb Z$$.

This in turn is true by (10), since according to that, the denominator of $$x$$ is exactly $$p^{\nu_p(\tau(n))}$$, which exactly cancels the powers of $$p$$ that are in $$\tau(n)$$, and the other factor $$(p^{whatever}-1)$$ is obviously not divisible by $$p$$.

• Ok so my only remaining issue is then those I have labelled $(7\operatorname{i})$ & $(8\operatorname{i})$ – Adam Oct 3 '18 at 2:57
• Note that the formula I quoted from WP shows that if $n$ is a square, $\tau(n)$ is odd. This easily proves both 7i and 8i. – Torsten Schoeneberg Oct 3 '18 at 3:12
• Ok thankyou so much for your assistance Torsten I can see now this was far more straight forward than the considerations I had been previously considering – Adam Oct 10 '18 at 21:52