Number of pairs $(a,b)$ such that $a+b<n$ and such that $\gcd(a,b,n)=1$

153 Views Asked by At

Let $n$ be a positive integer. What is the number of pairs $(a,b)$ of positive integers such that $a+b<n$ and such that $\gcd(a,b,n)=1$?

I know that the number of positive integer $a$ such that $\gcd(a,n)=1$ is just $\varphi(n)$. Maybe we can express the answer for my question above in terms of $\varphi(n)$ and other arithmetic functions.

1

There are 1 best solutions below

0
On

This is A000741 the number of compositions of $n$ into $3$ ordered relatively prime parts. Write $c=n-a-b,$ so that $(a,b,c)$ is a composition of $n$. Some of the scripts given on OEIS seem to relate to the divisor function, but I don't know any of the languages, so I can't be sure.