Exercise 2.3.46* (Number of integers $a,\ 1\leq a \leq n$, for which $(a,n) = 1$ and $(a+1,n) = 1$)

Proof.

a)

This is a particular case of Problem 47, so I use the result of Problem 47:

if ${\Phi }_f(m)$denotes the number of integers $a,1\le a\le m$, such that $f(a)\wedge m=1$, then

$${\varphi }_f(n)=n\underset{p\mid n}{\prod }\left(1-\frac{N(p)}{p}\right),$$

where $N(p)$denotes the number of solutions of the congruence $f(x)\equiv 0(\mathit{mod}m)$.

Consider the polynomial $f(x)=x(x+1)\in [x]$. Since $a\wedge n=1$ and $(a+1)\wedge n=1$ is equivalent to $a(a+1)\wedge n=1$, we obtain

$$\psi (n)={\Phi }_f(n).$$

Moreover, the congruence $x(x+1)\equiv 0(\mathit{mod}p)$ has only two solutions, since $p$ is prime:

$$\begin{array}{llll}\hfill x(x+1)\equiv 0(\mathit{mod}p)& ⟺p\mid x(x+1)& \hfill & \\ \hfill & ⟺p\mid x\text{ or }p\mid x+1& \hfill & \\ \hfill & ⟺x\equiv 0\text{ or }x\equiv -1(\mathit{mod}p).& \hfill & \end{array}$$

Therefore $N(p)=2$, and Problem 47 gives

$$\begin{array}{llll}\hfill \psi (n)& =n\underset{p\mid n}{\prod }\left(1-\frac{N(p)}{p}\right)& \hfill & \\ \hfill & =n\underset{p\mid n}{\prod }\left(1-\frac{2}{p}\right).& \hfill & \end{array}$$

b)

If $\psi (n)=0$, there is some $p\mid n$ such that $1-\frac{2}{p}=0$, thus $p=2\mid n$, so $n$ is even.

Conversely, if $n$ is even, then for all integers $a$, $a$ or $a+1$ is even, thus $a\wedge n>1$ or $a\wedge (n+1)>1$: there is no integer $a,1\le a\le n$ for which both $a\wedge n=1$ and $a+1\wedge n=1$. This shows that $\psi (n)=0$.

$$\psi (n)=0⟺2\mid n.$$