Determining the 2 adic divisibility of the totient of a Natural number

64 Views Asked by At

Basically I wanted to determine exactly what the largest power of 2 the totient of a natural number will be divisible by,I'm sure I have done something silly at some point, but that's how it is with direct proofs sadly no dignity spared there:

Anyway this is my attempt thus far,

I began with the Euler product of $n$:

$$E(n)=\prod_{p |n}(1-\frac{1}{p})$$ which is equivalent to:

$$E(n)=\frac{\prod_{p |n}(p-1)}{\prod_{p |n}(p)}$$

So likewise the Euler totient function of $n$ can be seen to have proportion to $n$ itself and $n$ divided by it's own radical:

$$\phi(n)=n \cdot \frac{\prod_{p |n}(p-1)}{\prod_{p |n}(p)}$$

And since the radical of a number (denominator of $E(n)$) is a divisor of that number we can assert that:

$\forall n \in \mathbb N\,$s.t$\,n \gt 1$ $\,\,\exists k \in \mathbb N $ s.t:

$$\phi(n)=k \cdot \prod_{p |n}(p-1)$$

And because $\prod_{p |n}(p-1)$ is a product of $\omega(n)-1$ even numbers when $n$ is even, and $\omega(n)$ even numbers when $n$ is odd, we can state that:

$$2^{\omega(n)-\frac{1}{2}{((-1)^n+1)})} \,\,\,|\,\,\, \phi(n)$$

And then accounting for the 2-adic order contributed by the other factor of $\phi(n)$, $\frac{n}{\\rad(n)}$:

$$2^{v_{2}(\frac{n}{{rad(n)}})} \,\,\,|\,\,\, \phi(n)$$

Hence collectively we can assert that the 2-adic order for $\phi(n)$ is:

$$v_2(\phi(n))=\omega(n)-\frac{1}{2}((-1)^n+1)+v_{2}(\frac{n}{{rad(n)}})$$ where:

$\omega(n)$ is the number of distinct prime factors of $n$

$rad(n)$ is the radical of $n$ wiki
$v_p(n)$ is the p-adic order of $n \,\,\,$wiki

EDIT: In enumerating the concluding result for my attempt as above, it appears that I have indeed made a mistake somewhere here because my conclusion does not hold for all $N$, the actual results only suggests that the following be true:

$$2^{\omega(n)-{((-1)^n+1)}+v_{2}(\frac{n}{{rad(n)}})} \,\,\,|\,\,\, \phi(n)$$