The Ramanujan Equation

Sirix asks about how to list all (integer) solutions to the Ramanujan equation, x^2 + 7 = 2^n. He has the basic method right: factor the left-hand side in Q(SQRT(-7)), whose ring of integers, Z[0.5+0.5SQRT(-7)], has class number 1.

Now, let’s denote SQRT(-7) by s to make things easier. We get (x + s)(xs) = 2^n. If x is even, x^2 + 7 is not divisible by 2, and there are no solutions; hence, suppose that x is odd. Then x (+/-) s is divisible by 2, yielding ((x + s)/2)((xs)/2) = 2^m, where m = n – 2.

In Q(SQRT(-7)), 2 splits completely as ((1 + s)/2)((1 – s)/2), and (x (+/-) s)/2 isn’t divisible by 2. So (x (+/-) s)/2 is a power of (1 + s)/2 – in fact, an mth power. Since the ring has integral basis {1, (1 + s)/2}, we can let r = (1 + s)/2, whose conjugate r‘ is (1 – s)/2 = 1 – r.

Sirix goes on to define a sequence b(m) based on the r-coefficient of r^m. Since r^2 = (-2 + r), we get that if r^m = a + br, then r^(m + 1) = -2b + (a + b)r. It easily follows that b(m) = b(m – 1) – 2b(m – 2), with b1 = b2 = 1. Finding the set of all m‘s for which b(m) = (+/-)1 is then equivalent to solving the Ramanujan equation.

A possible way of showing that the only m‘s for which b(m) = (+/-)1 are 1, 2, 3, 5, and 13 is proven in this paper. But I’ll follow a more direct proof, which does not depend on the sequence b(m), though of course it proves the fact about the sequence indirectly.

First, suppose n = 2k. Then 2^nx^2 splits in Z as (2^k + x)(2^kx) = 7. Assuming x is positive, it means 2^k + x = 7 and 2^kx = 1, so that k = 2, n = 4, and x = 3. Now, suppose n > 4, which means n is odd and m > 2.

Then (x (+/-) s)/2 = ((1 (+/-) s)/2)^m implies (+/-)s = r^mr‘^m. Now s = rr‘, so if s = r^mr‘^m, then rr‘ = r^mr‘^m. But r‘ = 1 – r, so r^2 = (1 – r‘)^2 = 1 – 2r‘ + r‘^2 = 1 mod r‘^2 since r‘ divides 2. Since m is odd, this means that r^m = r mod r‘^2, so rr‘ = r^mr‘^m = r mod r‘^2, which implies r‘ = 0 mod r‘^2, a contradiction.

We therefore get –s = r^mr‘^m; multiplying both sides by 2^m and using a binomial expansion, we get –s*2^m = (1 + s)^m – (1 – s)^m = 2s(m – 7*C(m, 3) + 49*C(m, 5) – … + 7^((m – 1)/2)), where C(n, k) is n over k, the number of ways to choose k elements out of n.

After dividing by 2s, we get -2^(m – 1) = m mod 7. The sequence of residue classes of 2^(m – 1) mod 7, beginning with m = 1, is (1, 2, 4). So solutions to the equation are determined by the residue class of m mod 21; the only possible solutions are then m = 3, 5, or 13 mod 21.

Since 3, 5, and 13 solve the Ramanujan equation, it suffices to show that if m and m‘ are solutions that have the same residue class mod 21, then m = m‘. To do that, let 7^k divide mm‘, with k > 0. It suffices to show that 7^(k + 1) divides mm‘ as well, since then mm‘ is infinitely divisible by 7, making it 0.

The group of nonzero residue classes mod 7^(k + 1) has 6*7^k elements, so 2^(6*7^k) = 1 mod 7^(k + 1). In fact 2^(3*7^k) = 1 mod 7^(k + 1), because 2 is a quadratic residue of 7, hence of every power of 7. Since 3*7^k = lcm(21, 7^k) divides mm‘, it means 2^(mm‘) = 1 mod 7^(k + 1).

Also, (1 + s)^(mm‘) = 1 + (mm‘)s – 7*C(mm‘, 2) – … (+/-) s^(mm‘). All terms except the first two are divisible by 7^(k + 1); this is obvious for all terms except the last, for which it holds since 7^(k + 1) divides s^(2k + 2), and 2k + 2 < 7^k < mm‘ for all k > 0. So (1 + s)^(mm‘) = 1 + (mm‘)s mod 7^(k + 1), and r^(mm‘) = 1 + (mm‘)s mod 7^(k + 1).

Finally, (1 + s)^m = 1 mod s, and 2*4 = 1 mod s, so that r^m = 4^m mod s. Now r^mr^m‘ = r^m‘(r^(mm‘) – 1) = (r^m‘)(mm‘)s mod 7^(k + 1) = (4^m)(mm‘)s mod 7^(k + 1). The last equality is the trickiest. It requires noting that (mm‘)s is divisible by s*7^k, so that the residue class of r^mr^m‘ mod 7^(k + 1) depends only on this of r^m‘ mod s.

Taking conjugates, we get that r‘^mr‘^m‘ = -(4^m)(mm‘)s mod 7^(k + 1); note that m‘ is not the conjugate of m, despite the notation. We get by subtracting r^mr^m‘ – r‘^m + r‘^m‘ = 2(4^m)(mm‘)s mod 7^(k + 1). But r^mr‘^m = r^m‘ – r‘^m‘ = –s, since we assume m > 2. So 2(4^m)(mm‘)s = 0 mod 7^(k + 1). As 2 and 4 are not divisible by 7, this reduces to (mm‘)s = 0 mod 7^(k + 1).

Finally, note that m and m‘ are in Z. The congruence mod 7^(k + 1) implies that mm‘ is divisible by s*7^k, i.e. that (mm‘)/7^k is divisible by s. But the only integers that are divisible by s are divisible by 7, since the ideal (s) intersects Z in (7). Therefore mm‘ is divisible by 7^(k + 1), which is enough to prove that the only solutions to the Ramanujan equation are those with m = 1, 2, 3, 5, or 13.

2 Responses to The Ramanujan Equation

  1. sirix says:

    It seems ok, though I still hope there exist a solution that is more from_the_Book🙂.

    “But I’ll follow a more direct proof, which does not depend on the sequence b(m), though of course it proves the fact about the sequence indirectly.”

    “We therefore get -s = r^m – r‘^m;”

    Small remark: In fact, you are quite directly proving that b_m is not -1: closed form for b_m is exactly b_m = 1/s * (r^m – r’^m).

    Is it your solution? If not, can you give a reference?

  2. Alon Levy says:

    It’s not mine; the proof is from Stewart and Tall’s book Algebraic Number Theory. I tried proving it by using the fact that b(n) is a Fibonacci-type sequence, but when I tried constructing a closed form equation for it, all I got was Im((1 + s)^n)/s.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: