0

Let $n\in\mathbb Z_{>0}$ and $a\in\mathbb Z$.

a) Prove $\overline a=\overline{-a}\iff \overline a=\overline0.$

b) Prove that

  1. if $n$ is odd, then $\overline a=\overline{-a}\iff\overline a=\overline0,$

  2. if $n$ is even, then $\overline a=\overline{-a}\iff\overline a=\overline0$ or $\overline a=\overline{n/2}.$

c) Prove that if $n>2$, then $\phi(n)$ is even.

I've shown a) and b). Here $\phi$ is the Euler function, defined by

$\phi(n)=\#\{a\in\mathbb Z\mid1\leq a\leq n, \gcd(a,n)=1\}$.

However, I have no clue how to use a) and b) to prove this. Could someone give me a hint? I was considering using induction.

Consider $\mathbb N$\ $m\mathbb N$. Assume that for some $n\in\mathbb N$, it holds that $\phi(n)$ is even. Now consider $n+1$. We know that $\phi(n+1)=\phi(n)$ if $\gcd(n+1,m)\neq 1$, and $\phi(n+1)=\phi(n)+1$ if $\gcd(n+1,m)=1$. But I should be able to show that we can only add 2, and not 1. But I wouldn't know how to proceed?

Community
  • 1
Sha Vuklia
  • 3,960
  • 4
  • 19
  • 37
  • I know what the Euler function $\phi(n)$ is, but what the heck does $\overline a$ mean?? – bof Mar 11 '17 at 21:04
  • My apologies, I thought it was common notation. In this case $\overline a=\overline b$ means $a\equiv b\mod n$ (i.e., $a$ and $b$ have the same remainder after division by $n$). – Sha Vuklia Mar 12 '17 at 15:10

1 Answers1

2

If $n$ is odd with $n>1$, you can pair up $a$ and $n-a$. If one of those is relatively prime to $n$, then so is the other.

If $n$ is even with $n > 2$, then $n/2$ is not relatively prime to $n$, hence the pairing used for the odd case still works.

quasi
  • 58,772
  • I don't understand why we have to consider an odd and even case? If $n>2$ is even, then $n/2$ doesn't have to be even (e.g., $n=42$). I think it suffices to show $\gcd(a,n)=1\iff\gcd(n-a,n)=1$ for any $n\in\mathbb N_{>2}$. We rewrite $xa+yn=1$ to $(x+y)a+y(n-a)=1$, and the other way around as well. – Sha Vuklia Mar 12 '17 at 15:08
  • @Sha Vuklia: You're quite right that $n$ even and $n > 2$ doesn't force $n/2$ to be even. But you still need to worry about the case where $a$ and $n-a$ don't form a pair, and that only happens when $n$ is even and $a=n/2$, so the pairing argument still needs to deal with that. I'll fix my answer -- thanks for alerting me to the flaw. – quasi Mar 12 '17 at 15:54