1
$\begingroup$

Theorem: For every positive integer n greater than $2$, then $\phi(n)$ is an even integer.

I know this theorem and the same is used much, but I was curious how it would be to demonstrate it, show me anyone know how or where to find it?

$\endgroup$
5
$\begingroup$

One way to prove it is the following: When $n\geq 3$ we have that $-1\neq 1$ in $\mathbb{Z}/n\mathbb{Z}$, so $-1$ is an element of order $2$ in $(\mathbb{Z}/n\mathbb{Z})^*$ and the result follows by Lagrange since $\varphi(n)$ is the order of that group.

$\endgroup$
2
$\begingroup$

Let $n = p_1^{a_1} \cdot p_2^{a_2}\cdot \ldots \cdot p_k^{a_k}$. Then for $\phi(n)$ we have:

$$\phi(n) = p_1^{a_1}\left(\frac{p_1-1}{p_1}\right)\ldots$$ $$\phi(n) = p_1^{a_1 - 1}\cdot (p_1-1)\ldots$$

And since $\phi(n)$ is integer for every natural number $n$, for $p_1$ is odd, $(p_1 - 1)$ is even so $\phi(n)$ has 2 as a factor, i.e $\phi(n)$ is even number.

Now check the case when $n$ is a power of two, because every other number has at least one odd prime factor. Note that then $a_1 - 1 > 0$ and $p_1 = 2$ if $n$ is power of $2$. So $p_1^{a_1-1}$ is a even factor of $\phi(n)$, hence $\phi(n)$ is even number.

$\endgroup$
2
$\begingroup$

If $n$ has no odd prime divisor, then $n=2^r$, so that $\phi(n)=2^r-2^{r-1}$ is even for $r\ge 2$. Otherwise $n$ has an odd prime divisor $p$, which yields an even factor $p-1$ in the product formula for $$ \phi(n)=\frac{n}{\prod_{p\mid n}p}\prod_{p\mid n}(p-1). $$ This proof shows more: $2^s \mid \phi(n)$, not just $2\mid \phi(n)$, where $s$ is the number of odd prime divisors of $n$.

$\endgroup$
1
$\begingroup$

Note that if $x$ is relative prime to $n$, so is $n-x$ except for $n=2$, since you double count $x=1=2-1=n-x$.

$\endgroup$
1
$\begingroup$

Lemma: If $\gcd(n,k)=1$ then $\gcd(n,n-k)=1$.

Proof: Suppose $d|n,d|n-k$ so $d|n-(n-k)$ and $d|k$. So we have $d|k$ and $d|n$ and according to the first part, $d=1$. Thus, $\gcd(n,n-k)=1$.
This means you count each $k$ that $\gcd(n,k)=1$ twice.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.