Bossy Lobster

A blog by Danny Hermes; musing on tech, mathematics, etc.

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(Bn)Tor(Q)=?Z/2Z.J(B_n)_{\text{Tor}}\left(\mathbb{Q}\right) \stackrel{?}{=} \mathbb{Z}/2\mathbb{Z}.

WAT? In the above, J(Bn)J(B_n) is the Jacobian of the curve BnB_n given by y2=(x+2)fn(x)y^2 = (x + 2) \cdot f^n(x). Here fnf^n denotes

ffn times\underbrace{f \circ \cdots \circ f}_{n \text{ times}}

and f(x)=x22f(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(52n+1,132n+1,,p2n+1,)=2(1)\gcd\left(5^{2^n} + 1, 13^{2^n} + 1, \ldots, p^{2^n} + 1, \ldots \right) = 2 \qquad (1)

where the nn in the exponents is the same as that in BnB_n and where the values we are using in our greatest common divisor (e.g. 5,135, 13 and pp above) are all of the primes p5mod8p \equiv 5 \bmod{8}.

My buddy, being sadistic and for some reason angry with me, passed me along the stronger statement:

gcd(52n+1,132n+1)=2(2)\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 52+122=1325^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)(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)(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)(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,n = 0, we see trivially that

gcd(520+1,1320+1)=gcd(6,14)=2\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 22 hence the gcd\gcd over all the primes must be 22.

Now, if n>0,n > 0, we will show that 22 divides our gcd,\gcd, but 44 does not and that no odd prime can divide this gcd\gcd. First, for 2,2, note that

p2n+1(±1)2n+12mod4p^{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 22 and none by 44.

Now assume some odd prime pp^{*} divides all of the quantities in question. We'll show no such pp^{*} can exist by contradiction.

In much the same way we showed the gcd\gcd wasn't divisible by 4,4, we seek to find a contradiction in some modulus. But since we are starting with

p2n+10modpp^{2^n} + 1 \equiv 0 \bmod{p^{\ast}}

if we can find some such pp with

p1modpp \equiv 1 \bmod{p^{\ast}}

then we'd have our contradiction from

0p2n+112n+12modp0 \equiv p^{2^n} + 1 \equiv 1^{2^n} + 1 \equiv 2 \bmod{p^{\ast}}

which can't occur since pp^{*} is an odd prime.

With this in mind, along with a subsequence of the arithmetic progression {5,13,21,29,},\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,8, but we also want to know about the residue modulo pp^{*}. Naturally, we look for a subsequence in

Z/8Z×Z/pZ\mathbb{Z}/8\mathbb{Z} \times \mathbb{Z}/p^{*}\mathbb{Z}

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

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

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

But since 1+kpr5mod8,1 + kp^{\ast} \equiv r \equiv 5 \bmod{8}, we have kp4mod8kp^{\ast} \equiv 4 \bmod{8} and k=4(p)1 mod 8k = 4\left(p^{*}\right)^{-1} \text{ mod }{8} since pp^{*} is odd and invertible mod 88. But this also means its inverse is odd, hence k4(2k+1)4mod8k \equiv 4\cdot(2k' + 1) \equiv 4 \bmod{8}. Thus we have 1+4pZ/8pZ1 + 4 p^{\ast} \in \mathbb{Z}/8p^{\ast}\mathbb{Z} corresponding to our residue pair. Thus every element in the arithmetic progression

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

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

What's more, since 5(Z/8Z)×5 \in \left(\mathbb{Z}/8\mathbb{Z}\right)^{\times} and 1(Z/pZ)×,1 \in \left(\mathbb{Z}/p^{*}\mathbb{Z}\right)^{\times}, we have 1+4p(Z/8pZ)×1 + 4 p^{*} \in \left(\mathbb{Z}/8p^{*}\mathbb{Z}\right)^{\times} (again by the Chinese remainder theorem). Thus the arithmetic progression SS satisfies the hypothesis of Dirichlet's theorem. Hence there must be at least one prime pp occurring in the progression (since there are infinitely many). But that also means pp occurs in {5,13,29,37,}\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)(2)

gcd(52n+1,132n+1)=2\gcd\left(5^{2^n} + 1, 13^{2^n} + 1\right) = 2

By similar arguments as above, if any odd prime pp^{*} divides this gcd,\gcd, then we have

52n1modp5^{2^n} \equiv -1 \bmod{p^{\ast}}

hence there is an element of order 2n+12^{n+ 1}. This means the order of the multiplicative group φ(p)=p1\varphi\left(p^{*}\right) = p^{*} - 1 is divisible by 2n+12^{n + 1}. Beyond that, who knows? We're still thinking about it (but only passively, more important things to do).