Some sum of gcd

Number Theory Level 3

Let R(a, b) = (gcd(1, a) + gcd(2, a) + gcd(3, a)... + gcd(b, a))/b

find R(6, 2304)

Hint:

R(6, 2082) = R(6, 1152)

1 solution

A Former Brilliant Member
Sep 23, 2020

The value of $gcd(6,b)$ repeates periodically with a period $6$ , the values obtained in each cycle are $1,2,3,2,1,6$ , whose sum is $15$ .

In $R(6,2304)$ , there are $\frac{2304}{6}$ or $384$ cycles,

whose total sum is $15\times 384$ or $5760$ .

So, $R(6,2304)=\dfrac {5760}{2304}=\boxed {2.5}$ .

In fact, the value of $R(6,6b)$ is always $\frac{15}{6}=\boxed {2.5}$ .

Your last statement is only true when $b$ is a multiple of $6$ - $R(6,7) = \tfrac{16}{7}$ , for example.

Mark Hennings - 8 months, 3 weeks ago

Yes. You're right. Editing.

A Former Brilliant Member - 8 months, 3 weeks ago