MathDB

N8

Part of 2017 IMO Shortlist

Problems(1)

Number of times to do Euclidean GCD.

Source: IMO Shortlist 2017 N8

7/10/2018
Let pp be an odd prime number and Z>0\mathbb{Z}_{>0} be the set of positive integers. Suppose that a function f:Z>0×Z>0→{0,1}f:\mathbb{Z}_{>0}\times\mathbb{Z}_{>0}\to\{0,1\} satisfies the following properties:
[*] f(1,1)=0f(1,1)=0. [*] f(a,b)+f(b,a)=1f(a,b)+f(b,a)=1 for any pair of relatively prime positive integers (a,b)(a,b) not both equal to 1; [*] f(a+b,b)=f(a,b)f(a+b,b)=f(a,b) for any pair of relatively prime positive integers (a,b)(a,b).
Prove that ∑n=1p−1f(n2,p)⩾2p−2.\sum_{n=1}^{p-1}f(n^2,p) \geqslant \sqrt{2p}-2.
IMO Shortlistnumber theoryEuclidean algorithm