On the sum of relatively prime number $<N$

92 Views Asked by At

Let $A(N)$ be a function which is the sum of all numbers relatively prime and $<N$ and $B(N)$ the sum of remaining $N−\phi(N)$ numbers. Then I have the following questions-

Q-1 For what values of $N$ , $A(N) >B(N)$ ? And for what is $A(N)<B(N)$?

Q-2 What are the asymptotics of the function $A(N)$ and $B(N)$?


I have tried working by observing $A(N)= N \phi(N)/2$ and $B(N)=\frac{N(N-1)-N \phi(N)}{2}$ but in Vain. And I have no hint for the asymptotics

1

There are 1 best solutions below

5
On BEST ANSWER

Note that $A(N)<B(N)$ is equivalent to $$\phi(N)<{N-1\over2}$$ Also, $$\phi(N)=N\prod_{p\mid N}(1-p^{-1})$$ so $A(N)<B(N)$ is equivalent to $$\prod_{p\mid N}(1-p^{-1})<{1\over2}-{1\over2N}$$ So it's mostly a question of whether there are enough small prime divisors of $N$ to bring that product down below $1/2$.