Having just left Google and started my PhD in Applied Mathematics at Berkeley, I thought it might be appropriate to write some (more) math-related blog posts. Many of these posts, I jotted down on napkins and various other places on the web and just haven't had time to post until now.
He was trying to determine if
WAT? In the above, is the Jacobian of the curve given by . Here denotes
Now, his and my interests diverged some time ago, so I can't appreciate what steps took him from this to the problem I got to help with. However, he was able to show (trivially maybe?) that this was equivalent to showing that
where the in the exponents is the same as that in and where the values we are using in our greatest common divisor (e.g. and above) are all of the primes .
My buddy, being sadistic and for some reason angry with me, passed me along the stronger statement:
which I of course struggled with and tried to beat down with tricks like . After a few days of this struggle, he confessed that he was trying to ruin my life and told me about the weaker version .
When he sent me the email informing me of this, I read it at 8am, drove down to Santa Clara for PyCon and by the time I arrived at 8:45am I had figured the weaker case out. This felt much better than the days of struggle and made me want to write about my victory (which I'm doing now). Though, before we actually demonstrate the weaker fact I will admit that I am not in fact tall. Instead I stood on the shoulders of Dirichlet and called myself tall. Everything else is bookkeeping.
Let's Start the Math
First, if we see trivially that
and all the remaining terms are divisible by hence the over all the primes must be .
Now, if we will show that divides our but does not and that no odd prime can divide this . First, for note that
since our primes are odd. Thus they are all divisible by and none by .
Now assume some odd prime divides all of the quantities in question. We'll show no such can exist by contradiction.
In much the same way we showed the wasn't divisible by we seek to find a contradiction in some modulus. But since we are starting with
if we can find some such with
then we'd have our contradiction from
which can't occur since is an odd prime.
With this in mind, along with a subsequence of the arithmetic progression it seems that using Dirichlet's theorem on arithmetic progressions may be a good strategy. However, this sequence only tells us about the residue modulo but we also want to know about the residue modulo . Naturally, we look for a subsequence in
corresponding to the residue pair . Due to the Chinese remainder theorem this corresponds to a unique residue modulo .
Since this residue has we must have
But since we have and since is odd and invertible mod . But this also means its inverse is odd, hence . Thus we have corresponding to our residue pair. Thus every element in the arithmetic progression
is congruent to and hence and .
What's more, since and we have (again by the Chinese remainder theorem). Thus the arithmetic progression satisfies the hypothesis of Dirichlet's theorem. Hence there must be at least one prime occurring in the progression (since there are infinitely many). But that also means occurs in hence we've reached our desired contradiction. RAA.
We still don't know if the strong version
By similar arguments as above, if any odd prime divides this then we have
hence there is an element of order . This means the order of the multiplicative group is divisible by . Beyond that, who knows? We're still thinking about it (but only passively, more important things to do).