Let’s say we have a number m. Is it possible to find in O(\sqrt{m}) time, the GCD of all numbers between 1 and m in a set S. For example if m=9
GCD(1,9)=1 ,GCD(2,9)=1 , GCD(3,9)=3 ... GCD(9,9)=9
So we have 3 pairs S=\{\{1,6\}\{3,2\}\{9,1\}\}. Where the element{a,b} in set S means b numbers between 1 and m have a gcd of a with m.How do I calculate this?
Interestingly enough, when m is odd, \frac{1}{m}\sum^{\{a,b\}\in S} b*2^{ak} is the number of subsets of the set \{1,2,3...km\} such that the sum of all elements in the subset are divisible by m. Why does it not work for even numbers, or why the sum even evaluates to an integer is beyond me. I was first asked to evaluate this with m=9, but the pattern i noticed seems to apply to all numbers unless they are even.Amazingly, if m can be written as 2^p m_0 and S_0 is the set of all GCDs from 0 to m_0 with m_0, it evaluates to \frac{1}{m}\sum^{\{a,b\}\in S_0} b*2^{ak2^p}