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.

Improve this question
$\endgroup$
1
  • $\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
    Commented Nov 6, 2009 at 3:30

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
7
  • 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
    Commented Nov 6, 2009 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
    Commented Nov 6, 2009 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
    Commented Nov 6, 2009 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
    Commented Feb 28, 2010 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
    Commented Jul 26, 2016 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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the reply. I think I will need time to understand Elkies' note :) $\endgroup$
    – mailsuite
    Commented Nov 6, 2009 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
    Commented Jan 25, 2010 at 17:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .