Using your Head is Permitted

September 2009 riddle

Three months ago, in the June riddle, I said that the riddle was inspired in part by a suggestion from James Ge. In fact, James's original question to me related to the naturals, not to finite fields. The question therefore becomes "Given a natural, n, how many Pythagorean triplets does n participate in?".

This question can be divided into two:

  1. How many (ordered) pairs of positive integers, (a,b), are there, such that a2+n2=b2?
  2. How many (unordered) pairs of positive integers, {a,b}, are there, such that a2+b2=n2?
To make these questions more general, let's substitute n2 with an arbitrary natural, m, and ask:
  1. How many (ordered) pairs of positive integers, (a,b), are there, such that a2+m=b2?
  2. How many (unordered) pairs of positive integers, {a,b}, are there, such that a2+b2=m?
We assume that the factorization of m is fully known.

The problem with asking these two questions as monthly riddles is that the former is too easy and the latter is too difficult. The reader is welcomed to answer them as bonus questions. As a monthly riddle, instead of these two questions, I decided to ask something slightly different, namely to prove a lemma that is a major stepping stone in proving the second question. The lemma is:

Prove that for any natural n>1 and for any integer i such that i2=-1 (mod n) there is exactly one ordered pair of positive integers (x,y) such that

  1. x and y are co-prime.
  2. ix=y (mod n).
  3. x2+y2=n.
Readers are asked to prove this lemma for credit. Readers who continue from this lemma to a full answer to the question regarding the enumeration of Pythagorean triplets are welcomed to send this answer, too.

As always, we ask for original solutions only, not ones based on prior familiarity or Internet searching.

List of solvers:

Pei Wu (27 September 01:10)

Elegant and original solutions can be submitted to the puzzlemaster at riddlesbrand.scso.com. Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.

Enjoy!

To solution

Back to main page