MathDB

3

Part of 2003 Kurschak Competition

Problems(1)

Lower estimate on Sum gcd(i,j)

Source: Kürschák 2003, problem 3

7/8/2014
Prove that the following inequality holds with the exception of finitely many positive integers nn:
∑i=1n∑j=1ngcd(i,j)>4n2.\sum_{i=1}^n\sum_{j=1}^n gcd(i,j)>4n^2.
inequalitiesnumber theoryAnalytic Number Theoryexpected valueProbabilistic MethodSummationphi function