3
$\begingroup$

Sorry if this question is too simple.

I once read, on a number theory textbook - forget the title, in one of the problems list that all Pythagorean triplets when multiplied are divisible by 60.

I proved that using the generating functions (is this the correct name? I got the name from my Discrete Mathematics textbook):

\begin{align} a &= p^2 - q^2 \\\ b &= 2pq \\\ c &= p^2 + q^2. \end{align}

I proved it by proving all possible parities of $p$ and $q$. It's tedious because I have to prove some cases are not possible (like $a$, $b$, and $c$ can't be all even or odd).

My questions are:

  1. Who and how someone came up with the generating functions?

  2. If you don't know the generating functions or don't want to prove it like I did, is there any other way to prove it? Geometrically? Using Calculus? I mean there're many ways to prove Pythagorean theorem using Geometry, Number Theory, etc.

$\endgroup$
  • $\begingroup$ A generating function for a sequence is a function or expression whose Taylor-series expansion has the terms of the sequence as its coefficients. You can find this out by googling "Generating function" and reading the Wikipedia article. Anytime you have questions about math, especially about terminology, Wikipedia is really the place to start. $\endgroup$ – Andrew Critch Nov 6 '09 at 3:30
14
$\begingroup$
  1. Generating functions is not really the right name. I would say "parameterization."

  2. These formulas were known to the Babylonians. The simple proof goes as follows: assume WLOG that a, b, c are relatively prime. Since a, b, c cannot all have the same parity, WLOG b, c have different parity. Then a^2 = (c + b)(c - b) where the factors on the RHS are odd and relatively prime (use the Euclidean algorithm), so they must both be squares, say p^2 and q^2 (use unique prime factorization.) Then c = p^2 + q^2, b = p^2 - q^2, and this gives a = 2pq.

  3. It's equivalent to showing that abc is divisible by 3, 4, 5. This is straightforward if you know that squares are congruent to 0, 1 mod 3, congruent to 0, 1 mod 4, and congruent to 0, 1, 4 mod 5 because 1 + 1 != 1 mod 3 or mod 4 and 1 + 1, 1 + 4, and 4 + 4 are not equal to 1 or 4 mod 5. This implies that two squares which are not divisible by 3, 4, 5 cannot sum to a square which is not divisible by 3, 4, 5.

$\endgroup$
  • 2
    $\begingroup$ (A side comment: I much prefer the acronym WOLOG because WLOG could be taken to mean “with loss of generality”. There is presedence: Some people use “wo” as shorthand for “without”.) $\endgroup$ – Harald Hanche-Olsen Nov 6 '09 at 0:49
  • $\begingroup$ Thanks for reply. I'm trying to figure out your answers (2 and 3). Btw, do you think we can come up with the functions ourselves if we don't know that the Babylonians knew them already? $\endgroup$ – mailsuite Nov 6 '09 at 1:02
  • $\begingroup$ Sure, they're pretty easy to discover and have probably been rediscovered countless times. In addition to the nice geometric solution, there is a way to do it using what are called the Gaussian integers: en.wikipedia.org/wiki/Gaussian_integer $\endgroup$ – Qiaochu Yuan Nov 6 '09 at 1:24
  • 2
    $\begingroup$ +1 for 3. especially. This is one of my favorite problems to assign to students who are learning about congruences. The conclusion is interesting, and once you realize you can just check this mod 3,4,5, it becomes a straightforward computation (which, as QY says, will teach you the significance of knowing the squares modulo N). Using the parameterization of all Pythagorean triples seems like overkill. $\endgroup$ – Pete L. Clark Feb 28 '10 at 8:46
  • 1
    $\begingroup$ I dont see how just congruence modulo 4 would work. What if $b,c$ are odd (so $b^2,c^2$ congruent to 1 mod 4), but $a$ congruent to 2 mod 4. This will satisfy $a^2+b^2=c^2$ mod 4, but $abc$ is not divisible by 4. In this case I think one needs to go modulo 8. Since $b$ and $c$ are odd, $b^2,c^2$ are congruent to 1 mod 8, so $a^2$ is divisible by 8, and hence by 16. This forces a to be divisible by 4. Or am I missing something simple? $\endgroup$ – Poincare-Lelong Jul 26 '16 at 6:41
4
$\begingroup$

Wikipedia explains how to come up with the parametrization (I think I've seen the term "generating functions" for this, but really that term means something entirely different).

Update: Ha! apparently you can also use Hilbert's theorem 90 to obtain the parametrization (Elkies' note).

$\endgroup$
  • $\begingroup$ Thanks for the reply. I think I will need time to understand Elkies' note :) $\endgroup$ – mailsuite Nov 6 '09 at 1:03
  • 1
    $\begingroup$ I think "generating functions" would be a perfectly good name for this if it didn't already mean something else. These are functions that generate something. $\endgroup$ – Michael Lugo Jan 25 '10 at 17:22

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.