Primitive
Pythagorean
Triples
| | Fred
Curtis
-
October
2000 |
| These
notes
are
just
a
defence
against
my
capacity
to
lose
back-of-envelope
derivations.
As
far
as
I'm
aware
all
the
results
are
well-known,
although
I
hadn't
previously
seen
General
Representation
(i). |
[Synopsis]
[Working]
[Source code]
[Chronology]
[References]
[Further Reading]
A
Pythagorean
Triple
is
a
triple
of
positive
integers
a,b,c
such
that
a2+b2=c2.
The
numbers
can
represent
the
sides
of
right-angle
triangle
-
call
a,b
and
c
the
sides
of
the
triple,
a
and
b
the
legs,
c
the
hypotenuse.
Example:
a=6,b=8,c=10.
A
Primitive
Pythagorean
Triple
is
a
Pythagorean
triple
a,b,c
with
the
constraint
that
gcd(a,b)=1,
which
implies
gcd(a,c)=1
and
gcd(b,c)=1.
Example:
a=3,b=4,c=5.
- Exactly
one
of
a,b
is
odd,
c
is
odd.
This
follows
from:
- At
least
one
leg
of
a
primitive
Pythagorean
triple
is
odd
since
if
a,b
are
both
even
then
gcd(a,b)>1
- At
most
one
leg
of
any
Pythagorean
triple
is
odd
since
if
a,b
both
odd
then
a2=b2=1(mod 4),
c2=1+1=2(mod 4),
but
c
even
means
c2=0(mod
4),
c
odd
means
c2=1(mod
4),
so
no
such
integer
c.
Some
properties
of
primitive
Pythagorean
triples:
Let
a
denote
the
odd
leg,
b
denote
the
even
leg,
c
denote
the
odd
hypotenuse
of
a
primitive
Pythagorean
triple.
Then:
- a,b,c
can
be
written
as:
General
Representation
(i)
-
a=ij,
b=(j2-i2)/2,
c=(j2+i2)/2
for
odd
i,j
where
gcd(i,j)=1,
i<j
- a,b,c
can
be
written
as:
General
Representation
(ii)
-
a=v2-u2,
b=2uv,
c=v2+u2
where
gcd(u,v)=1,
u<v
- the
two
representations
are
equivalent
under
the
substitution
i=v-u,
j=v+u.
- any
odd
number
s
or
even
number
s ¬= 2(mod
4)
can
appear
as
a
leg
of
a
primitive
Pythagorean
triple
in
Lp(s)=2n-1
ways
where
s
is
factored
as
s=p1k1p2k2...pnkn
- exactly
one
of
a,b
is
divisible
by
3
(see
Table
1)
- b
is
divisible
by
4
- exactly
one
of
a,b,c
is
divisible
by
5
(see
Table
2)
- exactly
one
of
a,b,(a+b),(a-b)
is
divisible
by
7
(see
Table
3)
- c
is
the
product
of
primes
of
the
form
4k+1
- at
most
one
of
a,b
is
a
square
Some
properties
of
(not
necessarily
primitive)
Pythagorean
triples:
These
properties
follow
directly
from
the
properties
of
primitive
triples
by
considering
an
arbitrary
triple
as
a
(possibly
unit)
multiple
of
a
primitive
triple.
Let
a,b,c
be
a
primitive
Pythagorean
triple,
a
denote
the
odd
leg,
b
denote
the
even
leg,
c
denote
the
odd
hypotenuse.
Write
c=b+ð
for
some
ð>0
| a2+b2 | = | (b+ð)2 |
| = | b2+2bð+ð2 |
| a2 | = | 2bð+ð2 |
| | ð(2b+ð) |
If
p
is
prime
and
p | ð
then
p | a2
and
p | a.
p¬|(2b+ð)
since
p | (2b+ð)
implies
p | 2b
implies
p | b
(since
p | a,
p ¬= 2)
and
gcd(a,b)>1.
Since
a2=ð(2b+ð)
and
gcd(ð,2b+ð)=1,
we
can
write
ð=i2,
2b+ð=j2
for
some
odd
i,j
with
i<j,
gcd(i,j)=1.
Substituting,
we
have:
| a | = | ij | | 2b+ð | = | j2 | | 2b | = | j2-i2 | | b | = | (j2-i2)/2 | | c | = | b+ð | | = | (j2-i2)/2+i2 | | = | (j2+i2)/2 |
| -- | General
Representation
(i)
-
a=ij,
b=(j2-i2)/2,
c=(j2+i2)/2
where
gcd(i,j)=1,
i<j |
Observe
that
4 | b
since
i2=j2=1(mod
8),
2b=j2-i2=0(mod
8),
so
b=0(mod
8)
or
b=4(mod
8),
i.e.
b=0(mod
4)
Observe
that
c
is
the
product
of
primes
of
the
form
4k+1,
since
if
n = a2 + b2,
prime
p = 3 (mod 4),
p | n
then
p | a
and
p | b,
i.e.
gcd(a,b) > p
This
analysis
agrees
with
a
statement
in
[Beiler]
page
115
that
an
odd
number
s
factored
as
s=p1k1p2k2...pnkn
can
occur
as
the
odd
leg
of
a
primitive
Pythagorean
triple
in
Lp(s)=2n-1
ways,
since
that
is
the
number
of
ways
s
can
be
partitioned
into
two
relatively
prime
factors
(the
way
a
is
partitioned
into
i
and
j
in
the
formulation
above
-
each
partitioning
of
a
leads
to
a
distinct
value
of
b).
Lp(s)=2n-1
is
also
true
for
the
number
of
ways
an
even
number
s=0(mod
4)
can
occur
as
the
even
leg
of
a
primitive
Pythagorean
triple
-
the
proof
of
this
statement
follows
from
a
decomposition
of
the
even
leg
similar
to
that
above
(recall
a,
b,
c
form
a
primitive
Pythagorean
triple,
a
the
odd
leg,
b
the
even
leg,
write
c=a+2µ):
| a2+b2 | = | (a+2µ)2 |
| = | a2+4aµ+4µ2 |
| b2 | = | 4aµ+4µ2 |
| | 4µ(a+µ) |
If
p
is
prime
and
p | µ
then
p | b2
and
p | b.
p¬|(a+µ)
since
p | (a+µ)
implies
p | a
and
gcd(a,b)>1.
Since
b2=4µ(a+µ)
and
gcd(µ,a+µ)=1,
we
can
write
µ=u2,
a+µ=v2
for
some
u,v
with
u<v,
gcd(u,v)=1.
Substituting,
we
have:
[Mathworld]
cites
this
general
representation
as
"known
to
the
early
Greeks".
4 | b,
b=2uv,
2 | uv,
therefore
uv
has
the
same
number
of
distinct
prime
factors
as
b.
The
number
of
ways
b
can
appear
as
the
even
leg
of
a
primitive
Pythagorean
triple
is
the
number
of
ways
relatively
prime
factors
u,v
of
b=2uv
can
be
chosen,
i.e.
Lp(b)=2n-1
where
b
is
factored
as
p1k1p2k2...pnkn.
At
most
one
of
a,b
is
a
square.
Suppose
both
a
and
b
are
squares,
say
a=r2
and
b=s2.
The
equation
a2+b2=c2
becomes
r4+s4=c2,
and
Fermat
showed
no
square
can
be
written
as
the
sum
of
fourth
powers
-
see
[Brown]
for
a
proof.
Table
1
shows
that
exactly
one
of
a,b
is
divisible
by
3.
Table
1
-
Values
of
a,b,c
modulo
3
Summary:
Possible
values
of
a,b,c
modulo
3
a
(mod
3) | b
(mod
3) | c
(mod
3) |
|---|
| 0 | ±1 | 2 | | ±1 | 0 | 1 | | | | The
values
in
the
table
on
the
right
were
obtained
by
considering
possible
values
of
i,j
in
General
Representation
(i) |
| | i
(mod
3) | j
(mod
3) | a=ij
(mod
3) | 2b=j2-i2
(mod
3) | 2c=j2+i2
(mod
3) |
|---|
| 0 | 0 | Invalid,
gcd(i,j)=1 | | 0 | 1 | 0 | 1
(b=2) | 1
(c=2) | | 0 | 2 | 0 | 1
(b=2) | 1
(c=2) | | 1 | 0 | 0 | 2
(b=1) | 1
(c=2) | | 1 | 1 | 1 | 0
(b=0) | 2
(c=1) | | 1 | 2 | 2 | 0
(b=0) | 2
(c=1) | | 2 | 0 | 0 | 2
(b=1) | 1
(c=2) | | 2 | 1 | 2 | 0
(b=0) | 2
(c=1) | | 2 | 2 | 1 | 0
(b=0) | 2
(c=1) |
|
Table
2
shows
that
exactly
one
of
a,b,c
is
divisible
by
5.
Table
2
-
Values
of
a,b,c
modulo
5
Summary:
Possible
values
of
a,b,c
modulo
5
a
(mod
5) | b
(mod
5) | c
(mod
5) |
|---|
| 0 | ±2 | ±2 | | ±1 | 0 | ±1 | | ±2 | ±1 | 0 | | | | The
values
in
the
table
on
the
right
were
obtained
by
considering
possible
values
of
i,j
in
General
Representation
(i) |
| | i
(mod
5) | j
(mod
5) | a=ij
(mod
5) | 2b=j2-i2
(mod
5) | 2c=j2+i2
(mod
5) |
|---|
| 0 | 0 | Invalid,
gcd(i,j)=1 | | 0 | 1 | 0 | 1
(b=3) | 1
(c=3) | | 0 | 2 | 0 | 4
(b=2) | 4
(c=2) | | 0 | 3 | 0 | 4
(b=2) | 4
(c=2) | | 0 | 4 | 0 | 1
(b=3) | 1
(c=3) | | 1 | 0 | 0 | 4
(b=2) | 1
(c=3) | | 1 | 1 | 1 | 0
(b=0) | 2
(c=1) | | 1 | 2 | 2 | 3
(b=4) | 0
(c=0) | | 1 | 3 | 3 | 3
(b=4) | 0
(c=0) | | 1 | 4 | 4 | 0
(b=0) | 2
(c=1) | | 2 | 0 | 0 | 1
(b=3) | 4
(c=2) | | 2 | 1 | 2 | 2
(b=1) | 0
(c=0) | | 2 | 2 | 4 | 0
(b=0) | 3
(c=4) | | 2 | 3 | 1 | 0
(b=0) | 3
(c=4) | | 2 | 4 | 3 | 2
(b=1) | 0
(c=0) | | 3 | 0 | 0 | 1
(b=3) | 4
(c=2) | | 3 | 1 | 3 | 2
(b=1) | 0
(c=0) | | 3 | 2 | 1 | 0
(b=0) | 3
(c=4) | | 3 | 3 | 4 | 0
(b=0) | 3
(c=4) | | 3 | 4 | 2 | 2
(b=1) | 0
(c=0) | | 4 | 0 | 0 | 4
(b=2) | 1
(c=3) | | 4 | 1 | 4 | 0
(b=0) | 2
(c=1) | | 4 | 2 | 3 | 3
(b=4) | 0
(c=0) | | 4 | 3 | 2 | 3
(b=4) | 0
(c=0) | | 4 | 4 | 1 | 0
(b=0) | 2
(c=1) |
|
Table
3
shows
that
exactly
one
of
a,b,(a+b),(a-b)
is
divisible
by
7
Table
3:
Possible
values
of
a,b,c
modulo
7
a
(mod
7) | b
(mod
7) | c
(mod
7) |
|---|
| 0 | ±1 | 1 | | 0 | ±2 | 2 | | 0 | ±3 | 4 | | ±1 | 0 | 1 | | ±1 | ±1 | 3 | | ±2 | 0 | 2 | | ±2 | ±2 | 6 | | ±3 | 0 | 4 | | ±3 | ±3 | 5 | |
Table
4:
Possible
values
of
a,b,c
modulo
11
a
(mod
11) | b
(mod
11) | c
(mod
11) |
|---|
| 0 | ±1 | 10 | | 0 | ±2 | 2 | | 0 | ±3 | 8 | | 0 | ±4 | 7 | | 0 | ±5 | 6 | | ±1 | 0 | 1 | | ±1 | ±2 | 7 | | ±1 | ±5 | 9 | | ±2 | 0 | 9 | | ±2 | ±1 | 4 | | ±2 | ±4 | 8 | | ±3 | 0 | 3 | | ±3 | ±4 | 5 | | ±3 | ±5 | 10 | | ±4 | 0 | 4 | | ±4 | ±2 | 3 | | ±4 | ±3 | 6 | | ±5 | 0 | 5 | | ±5 | ±1 | 2 | | ±5 | ±3 | 1 | |
Table
5:
Possible
values
of
a,b,c
modulo
13
a
(mod
13) | b
(mod
13) | c
(mod
13) |
|---|
| 0 | ±2 | ±2 | | 0 | ±5 | ±5 | | 0 | ±6 | ±6 | | ±1 | 0 | ±1 | | ±1 | ±3 | ±6 | | ±2 | ±3 | 0 | | ±2 | ±5 | ±4 | | ±3 | 0 | ±3 | | ±3 | ±4 | ±5 | | ±4 | 0 | ±4 | | ±4 | ±1 | ±2 | | ±5 | ±1 | 0 | | ±5 | ±6 | ±3 | | ±6 | ±2 | ±1 | | ±6 | ±4 | 0 | |
The
tables
of
values
of
a,b,c
in
larger
prime
modulii
were
created
with
a
perl
script
pptmod-pl.
- 2000
Oct
-
Started
this
page
- 2004
Feb
-
Added
this
chronology
+
reference
to
Fred
Barnes'
work.
