Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many ordered pairs $(a, b)$ of positive integers $a$ and $b$ are there such that $\gcd(a, b)= 1$ and $1\leq a,b\leq N$?

My approach is as follows.

Note that $a= b$ only when $a= b= 1$. So this will always give one solution. Now consider the case when $a$ is not equal to $b$. By symmetry assume $a>b$. We can multiply by $2$ later go get our final answer. Now for $N$ let the answer be $f(N)$. Now we need to find the number of ordered pairs $(a, b)$ of positive integers $a$ and $b$ are their such that $\gcd(a, b)= 1$ and $1\leq a<b\leq N+1$. Note that $f(N+1)= f(N) + \phi(N+1)$. This is because $1\leq a<b\leq N$ has $f(N)$ solutions, so $1\leq a<b\leq N+1$ also has these $N$ solutions, but in addition when calculating $f(N+1)$ we can set $b= N+1$ and get $\phi(N)$ possible values of $N$. So $f(N+1)= f(N) + \phi(N)$. Thus solving this recurrence relation we get $$f(N)= \phi(N) + \phi(N-1) + \dots + \phi(4) + f(3)= \phi(N) + \phi(N-1) + \dots + \phi(4) + 2.$$

My question is, is my approach correct here? Can we further simplify $$\phi(N) + \phi(N-1) + \dots + \phi(4) + f(3)= \phi(N) + \phi(N-1) + \dots + \phi(4) + 2\text{ ?}$$

Note:- the original question was to find the number of ordered pairs $(a, b)$ of positive integers $a,b$ such that $1\leq a,b\leq 50$ and $\gcd(a, b)= 1$.

share|improve this question
    
Please see here for how to typeset common math expressions with MathJax, and see here for how to use Markdown formatting. –  Zev Chonoles Jun 18 '13 at 18:49
2  
The approximate value, for $n$ large, is $6n^2/\pi^2$. I don't think there is a closed formula for a particular $n$. –  Thomas Andrews Jun 18 '13 at 18:53
1  
Take a look at oeis.org/A018805 for formulas and such. I agree with Thomas that there seems to be no closed formula for a particular n. –  Matthew Conroy Jun 18 '13 at 19:18

1 Answer 1

This is essentially the same question I recently answered here, since your quantity is $$ -1+2\sum_{k=1}^n\varphi(k)=\sum_{k=1}^n\mu(k)\left\lfloor\frac nk\right\rfloor^2. $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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