Just recently I came across a question on Quora Indonesia (so it’s in Indonesian, which is obvious) about simplifying this expression:
I already wrote my answer there, in Indonesian. That is not as simple as I would expect, but it definitely is interesting enough to force me to write this post.
I was thinking, what if I replace that by a general positive integer ? In other words, what can we say about
As in what I wrote as an answer in that Quora post, let’s denote by . Every pair of integers will be associated with a complex number .
First, it is quite trivial if or is even. If , the above expression just boils down to . Now, if for some , then , so the whole product will just be . We shall assume from this point that is an odd number greater than .
Now, if either or is , then . Since there are pairs of where at least one of or is , then we can say that
It is the last product that we should be interested at. Before anything, we shall make a couple of observations about the symmetry of .
- For any and , and
- For any , for any .
These two observations enable us to write
By now I hope it is already clear why I wrote ‘product of cosines’ in the title. is, after all, product of cosines. For simplicity, let us define, for every where
Our function is therefore
Now, an observation can be made if is prime. Define
and observe that
We then observe that , since none of will be a multiple of if is prime and both and are less than . Hence,
for every , and thus for prime we conclude that
Well, in fact, this is what I initially thought the answer of that Quora question was going to be after trying some small odd integers to replace . Until I realised that it is going to be more complicated if is composite. In this case, there will be such that is a multiple of , and thus implying . In this case, we cannot use the same argument above to find : we need to think of another way.
At this stage, I really should try to work on the case of but I think it will be much, much more complicated. So, at least for the time being, I will give you a case where where and are two distinct odd primes.
The result above regarding can still be salvaged, though. It does still work for those such that . So we need to know: how many such are there? We can use the Principle of Inclusion-Exclusion to find out.
So, out of the first positive integers, there will be numbers that are divisible by and numbers that are divisible by . There will be no number that is divisible by both and in the first positive integers. Hence, there are
such that are relatively prime to , where .
Now, how about those that share the common factor or ? Let’s have a look at those integers where . We can write for some integer . Now, in the expansion of
there will be exactly terms that are either or , coming from those that are multiples of . How do we compute the product of other terms?
Well, there’s a trick that we can use. We need to split the product into smaller products.
The plus and minus sign there is due to the product of for all . It won’t matter which one is the actual sign anyway, since we are interested in .
Now, have a look at the first product. Since and , none of the will be an integer multiple of . Therefore, we can apply the argument involving the product and as above to deduce that the first product must be
The rest of the products can be viewed exactly as the first product after you apply a suitable trigonometric identity first. For example, in the second product, you need to use .
We can then conclude that the product in every group will be . Since there are smaller products altogether, we conclude that for such that ,
Using the same reasoning, for such that , we have that
We are now ready to compute ! From the first positive integers, there are exactly integers whose . There are integers whose , and finally integers whose
You already see how complicated it is just in the case where is a product of two distinct primes. In the original Quora question, , so there are more cases to consider: those such that . However, the idea stays the same. In this case, .
I might soon add the case where for some . Hopefully I will have time and energy to do the general case 😛
By the way, I am quite certain there is a more elegant way to find . You know, is too simple for the product to be this complicated. But maybe I am wrong…