Tuesday, September 10, 2013

Calculating a Greatest Common Divisor with Dirichlet's Help

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.

For today, I'm posting a result which was somewhat fun to figure out with/for one of my buddies from Michigan Math. I'd also like to point out that he is absolutely kicking ass at Brown.

While trying to determine if
\[J(B_n)_{\text{Tor}}\left(\mathbb{Q}\right) \stackrel{?}{=} \mathbb{Z}/2\mathbb{Z} \] where \(J(B_n)\) is the Jacobian of the curve \(B_n\) given by \(y^2 = (x + 2) \cdot f^n(x)\) where \(f^n\) denotes \(\underbrace{f \circ \cdots \circ f}_{n \text{ times}}\) and \(f(x) = x^2 - 2\).

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
\[\gcd\left(5^{2^n} + 1, 13^{2^n} + 1, \ldots, p^{2^n} + 1, \ldots \right) = 2 \qquad (1)\] where the \(n\) in the exponents is the same as that in \(B_n\) and where the values we are using in our greatest common divisor (e.g. \(5, 13\) and \(p\) above) are all of the primes \(p \equiv 5 \bmod{8}\).

My buddy, being sadistic and for some reason angry with me, passed me along the stronger statement:
\[\gcd\left(5^{2^n} + 1, 13^{2^n} + 1\right) = 2 \qquad (2)\] which I of course struggled with and tried to beat down with tricks like \(5^2 + 12^2 = 13^2\). After a few days of this struggle, he confessed that he was trying to ruin my life and told me about the weaker version \((1)\).

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 \((1)\) 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 \((1)\)  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 \(n = 0\), we see trivially that
\[\gcd\left(5^{2^0} + 1, 13^{2^0} + 1\right) = \gcd\left(6, 14\right) = 2\] and all the remaining terms are divisible by \(2\) hence the \(\gcd\) over all the primes must be \(2\).

Now, if \(n > 0\), we will show that \(2\) divides our \(\gcd\), but \(4\) does not and that no odd prime can divide this \(\gcd\). First, for \(2\), note that
\[p^{2^n} + 1 \equiv \left(\pm 1\right)^{2^n} + 1 \equiv 2 \bmod{4}\] since our primes are odd. Thus they are all divisible by \(2\) and none by \(4\).

Now assume some odd prime \(p^{\ast}\) divides all of the quantities in question. We'll show no such \(p^{\ast}\) can exist by contradiction.

In much the same way we showed the \(\gcd\) wasn't divisible by \(4\), we seek to find a contradiction in some modulus. But since we are starting with \(p^{2^n} + 1 \equiv 0 \bmod{p^{\ast}}\), if we can find some such \(p\) with \(p \equiv 1 \bmod{p^{\ast}}\), then we'd have our contradiction from
\[0 \equiv p^{2^n} + 1 \equiv 1^{2^n} + 1 \equiv 2 \bmod{p^{\ast}}\] which can't occur since \(p^{\ast}\) is an odd prime.

With this in mind, along with a subsequence of the arithmetic progression \(\left\{5, 13, 21, 29, \ldots\right\}\), 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 \(8\), but we also want to know about the residue modulo \(p^{\ast}\). Naturally, we look for a subsequence in
\[\mathbb{Z}/\mathbb{8Z} \times \mathbb{Z}/\mathbb{p^{\ast}Z}\] corresponding to the residue pair \((5 \bmod{8}, 1 \bmod{p^{\ast}})\). Due to the Chinese remainder theorem this corresponds to a unique residue modulo \(8p^{\ast}\).

Since this residue \(r\) has \(r \equiv 1 \bmod{p^{\ast}}\), we must have
\[r \in \left\{1, 1 + p^{\ast}, 1 + 2p^{\ast}, \ldots, 1 + 7p^{\ast}\right\} .\] But since \(1 + kp^{\ast} \equiv r \equiv 5 \bmod{8}\), we have \(kp^{\ast} \equiv 4 \bmod{8}\) and \(k \equiv 4\left(p^{\ast}\right)^{-1} \bmod{8}\) since \(p^{\ast}\) is odd and invertible mod \(8\). But this also means its inverse is odd, hence \(k \equiv 4\cdot(2k' + 1) \equiv 4 \bmod{8}\). Thus we have \(1 + 4 p^{\ast} \in \mathbb{Z}/8p^{\ast}\mathbb{Z}\) corresponding to our residue pair. Thus every element in the arithmetic progression \(S = \left\{(1 + 4p^{\ast}) + (8p^{\ast})k \right\}_{k=0}^{\infty}\) is congruent to \(1 + 4 p^{\ast} \bmod{8p^{\ast}}\) and hence \(5 \bmod{8}\) and \(1 \bmod{p^{\ast}}\).

What's more, since \(5 \in \left(\mathbb{Z}/8\mathbb{Z}\right)^{\times}\) and \(1 \in \left(\mathbb{Z}/p^{\ast}\mathbb{Z}\right)^{\times}\), we have \(1 + 4 p^{\ast} \in \left(\mathbb{Z}/8p^{\ast}\mathbb{Z}\right)^{\times}\) (again by the Chinese remainder theorem). Thus the arithmetic progression \(S\) satisfies the hypothesis of Dirichlet's theorem. Hence there must at least one prime \(p\) occurring in the progression (since there are infinitely many). But that also means \(p\) occurs in \(\left\{5, 13, 29, 37, \ldots\right\}\) hence we've reached our desired contradiction. RAA.

Now What?

We still don't know if the strong version \((2)\)
\[\gcd\left(5^{2^n} + 1, 13^{2^n} + 1, \ldots, p^{2^n} + 1, \ldots \right) = 2\] By similar arguments as above, if any odd prime \(p^{\ast}\) divides this \(\gcd\), then we have
\[5^{2^n} \equiv -1 \bmod{p^{\ast}}\] hence there is an element of order \(2^{n + 1}\). This means the order of the multiplicative group \(\varphi\left(p^{\ast}\right) = p^{\ast} - 1\) is divisible by \(2^{n + 1}\). Beyond that, who knows? We're still thinking about it (but only passively, more important things to do).