Edit on GitHub

# 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.

He was trying to determine if

$J(B_n)_{\text{Tor}}\left(\mathbb{Q}\right) \stackrel{?}{=} \mathbb{Z}/2\mathbb{Z}.$

WAT? In the above, $J(B_n)$ is the Jacobian of the curve $B_n$ given by $y^2 = (x + 2) \cdot f^n(x)$. Here $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^{*}$ divides all of the quantities in question. We'll show no such $p^{*}$ 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^{*}$ 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^{*}$. Naturally, we look for a subsequence in

$\mathbb{Z}/8\mathbb{Z} \times \mathbb{Z}/p^{*}\mathbb{Z}$

corresponding to the residue pair $(5 \text{ mod }{8}, 1 \text{ mod }{p^{*}} )$. Due to the Chinese remainder theorem this corresponds to a unique residue modulo $8p^{*}$.

Since this residue $r$ has $r \equiv 1 \bmod{p^{\ast}} ,$ we must have

$r \in \left\{1, 1 + p^{*}, 1 + 2p^{*}, \ldots, 1 + 7p^{*}\right\}.$

But since $1 + kp^{\ast} \equiv r \equiv 5 \bmod{8},$ we have $kp^{\ast} \equiv 4 \bmod{8}$ and $k = 4\left(p^{*}\right)^{-1} \text{ mod }{8}$ since $p^{*}$ 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

$\displaystyle S = \left\{(1 + 4p^{*}) + (8p^{*})k \right\}_{k=0}^{\infty}$

is congruent to $1 + 4 p^{*} \text{ mod }{8p^{*}}$ and hence $5 \text{ mod }{8}$ and $1 \text{ mod }{p^{*}}$.

What's more, since $5 \in \left(\mathbb{Z}/8\mathbb{Z}\right)^{\times}$ and $1 \in \left(\mathbb{Z}/p^{*}\mathbb{Z}\right)^{\times},$ we have $1 + 4 p^{*} \in \left(\mathbb{Z}/8p^{*}\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 be 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\right) = 2$

By similar arguments as above, if any odd prime $p^{*}$ 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^{*}\right) = p^{*} - 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).