Triangunit divisors and quadratic reciprocity

Recall that the triangunit numbers are defined as the numbers you get by appending the digit 1 to the end of triangular numbers. Put another way, U_n = 10T_n + 1 where T_n denotes the nth triangular number, and U_n the nth triangunit number. The challenge, posed by Patrick Vennebush, is to discover and prove something interesting about the divisors of triangunit numbers. (There are spoilers ahead, so if you still want to think about this problem yourself first, stop reading now and go read my previous post instead.)

As you may have discovered, all the divisors of triangunt numbers seem to end in either 1 or 9. This is certainly a striking pattern, and if it’s true, can we explain why?

First, we can start with the formula for triangular numbers (which I have shown how to derive before), T_n = n(n+1)/2, and compute as follows:

U_n = 10T_n + 1 = 5n(n+1) + 1 = 5n^2 + 5n + 1

So every triangunit number is of the form 5n^2 + 5n + 1 for some natural number n.

The next thing to notice is that if we take any two numbers which end with 1 or 9 and multiply them together, their product also ends with 1 or 9. The last digit of a product depends only on the last digits of the factors; multiplying by 1 doesn’t change anything; and 9 times 9 is 81 which ends with 1. Another way to look at it is to note that 9 is the same as (-1) when working mod 10, so we’re really just saying that (\pm 1) \cdot (\pm 1) = \pm 1.

So it’s enough to show that all the prime divisors of triangunit numbers end with 1 or 9; if this is true then all the other divisors, being products of the prime divisors, will also end with 1 or 9.

As I noted before, the OEIS page for the triangunit numbers lists the following proof, due to Nick Hobson:

If p is an odd prime different from 5 then 5n^2 - 5n + 1 = 0 \pmod p implies 25(2n - 1)^2 = 5 \pmod p, whence p = 1 or -1 \pmod {10}.

But this is extremely telegraphic, and only makes sense by itself if you have a good background in number theory — so it’s a great proof to include on the OEIS but not so good for all the rest of us! Thankfully, Adam Glesser fleshed it out a bit in a comment on my previous post. I’m re-formulating his explanation in my own words, partly to try to make it as accessible as possible, and partly to make sure I understand it!

Suppose p is a prime number which divides the triangunit number 5n^2 + 5n + 1. Obviously, p cannot be 2 since triangunit numbers always end with 1 (and are therefore odd). p also cannot be 5 for the same reason (multiples of 5 always end with 0 or 5).

The fact that p is a factor of 5n^2 + 5n + 1 can be written using a modular equation as

5n^2 + 5n + 1 \equiv 0 \pmod p.

(In case you have never seen this sort of equation before, x \equiv y \pmod m means that x and y have the same remainder when divided by m.)

The next step is the crucial one which I never figured out — but I don’t feel too bad about it (and neither should you, if you didn’t figure it out either) since it requires some experience and background in number theory to think of it. The idea is to complete the square since this lets us use quadratic reciprocity. What’s that, you say? Read on! We multiply both sides of the equation by 20, then do a bit of rearranging:

\begin{array}{rcl}   100n^2 + 100 n + 20 & \equiv & 0 \pmod p \\  100n^2 + 100 n + 25 - 5 & \equiv & 0 \pmod p \\  (10n + 5)^2 & \equiv & 5 \pmod p  \end{array}

OK, so why is this helpful? This is where the law of quadratic reciprocity comes in. I’ll explain exactly what it is in my next post, but in this particular instance, from the fact that 5 is congruent to a square \pmod p, it allows us to conclude that p must also be congruent to a square \pmod 5 (although not necessarily the same square!).

Well, there aren’t too many possibilities for squares when working \pmod 5:

\begin{array}{rcl}  0^2 & \equiv & 0 \pmod 5 \\   1^2 & \equiv & 1 \pmod 5 \\  2^2 & \equiv & 4 \pmod 5 \\  3^2 = 9 & \equiv & 4 \pmod 5 \\  4^2 = 16 & \equiv & 1 \pmod 5  \end{array}

We already know p is not 5. So it must be congruent to 1 or 4 \pmod 5. That means that it ends with 1, 4, 6, or 9. But it can’t end with 4 or 6 because it is prime. Tada!

“But what about that magical quadrilateral recipricosi-thingummy or whatever it was in the middle!?” I hear you cry. Never fear, I shall explain it soon! It is rather famous and interesting and deserves its own post…

About these ads
This entry was posted in arithmetic, modular arithmetic, number theory, primes, proof and tagged , , , , . Bookmark the permalink.

5 Responses to Triangunit divisors and quadratic reciprocity

  1. mixedmath says:

    To explain quadratic reciprocity in one post – whoa. This sounds like a very brave task, most likely running through moduli, Legendre symbols, and reciprocity. I look forward to it.

    • Brent says:

      Well, it may take more than one post. =) On the other hand, I’m no expert and I don’t intend to give a complete overview…

  2. VK says:

    I’ve recently become interested in mathematics and this blog is awesome for someone (like me) who doesn’t have much knowledge in the subject.

    Great job explaining! I’ve actually managed to understand the proof…I think. And I had no idea what mod even meant before reading this post.

    Adding 1 to triangular numbers and then finding a pattern in the divisors of those numbers seems so arbitrary. Is there any real-life application to it? It’s fascinating how completely arbitrary mathematical concepts turn out to model the real world.

  3. Tom says:

    Fantastic proof! Wonderful :D Spent a train trip tinkering with the problem, but could only demonstrate the (relatively trivial) fact that the divisors couldn’t end in 0, 2, 4, 6, 8 or 5.

    Hope the change of host is working well!

  4. Pingback: Wild About Math bloggers 3/25/11 » Fun Math Blog

Comments are closed.