# Thread: Number Theory - Multiplicative Functions

1. ## Number Theory - Multiplicative Functions

Another one of those interesting number theory questions:

2. Originally Posted by moolimanj
Another one of those interesting number theory questions:

F(7)=5
F(8)=0
F(9)=3
F(12)=0.
Is it right?

Keep Smiling
Malay

3. Now if $\displaystyle n$ is even, say $\displaystyle 6$ then $\displaystyle 1,2,3,4,5,6$ any two adjacent ones you take we have one is even and one is odd. Thus $\displaystyle \gcd (a,n) , \gcd (a+1,n)$ cannot be both 1 because at least one of them is at least 2.

For the converse consider $\displaystyle 1,2,...,n$ and pick the first two and so $\displaystyle \gcd(1,n) , \gcd(2,n)$ we know that $\displaystyle \gcd(1,n)=1$ but since $\displaystyle F(n)=0$ it means $\displaystyle \gcd (2,n) \not = 1$ (otherwise $\displaystyle F(n)\not = 0$) and so it has to be $\displaystyle \gcd(2,n) = 2$ which means $\displaystyle 2|n$.

4. If prime $\displaystyle p$ then in the integers $\displaystyle 1,2,...,p$ we see that $\displaystyle \gcd(1,p)=\gcd(2,p) = 1 , \gcd(2,p)=\gcd(3,p) = 1, ... ,\gcd(p-2,p)=\gcd(p-1,p)=1$. Thus we have $\displaystyle p-2$ cases.