Find the Smallest Triangle

Date: 05/25/2001 at 14:59:13
From: Malau
Subject: To find the triangle length depending on the condition

Hello sir,

Here is the problem:

Given a triangle whose three sides are consecutive numbers, i.e.
x, x+1, and x+2 (where x is an integer, and the area of which is 
divisible by 20, find the smallest possible x for which these 
conditions hold true:

  two sides are odd numbers;
  at least one side is a prime number.

Date: 05/29/2001 at 13:05:42
From: Doctor Rick
Subject: Re: To find the triangle length depending on the condition

Hi, Malau.

This question caught my interest, and kept me thinking through the 
weekend. I found an answer soon enough, but I did so using a 
spreadsheet to test a thousand numbers or so - and that's not math, in 
my opinion. Though it answers the question at hand, it does not give 
me any insight into the problem; in particular, it tells me nothing 
about whether there is another solution, or how many more thousands of 
numbers I might have to test in order to find the next one.

I'll tell you how I started. Tell me why you are interested in this 
problem: is it a problem in a class (what class?) or recreational 
math? What have you done with it? After I've seen your work, I can 
tell you more of what I have figured out.

I started with Heron's formula for the area, k, of a triangle in terms 
of the three sides a, b, and c (you can find this in our Dr. Math 
FAQ):

  s = (a+b+c)/2 (the semi-perimeter)

  k = sqrt(s(s-a)(s-b)(s-c))

I defined the consecutive side lengths in terms of the middle number 
rather than the first; I often find that such a "symmetrical" choice 
of variable allows some terms in my equations to cancel out. Thus, the 
three sides are

  a = n-1; b = n; c = n+1

Before getting on with your problem, I considered a broader problem: 
under what conditions will this triangle have an integer area? Heron's 
formula gave me a condition. After some manipulation to simplify the 
condition (and use a variable that would have smaller values), I set 
up the spreadsheet to calculate the square root of a number that 
should be a perfect square. Then I looked down the column for numbers 
without decimal places. I found 7 solutions, only one of which gave an 
area that was divisible by 20.

Once I had a little table of triangles with integer area, I noticed 
that they obeyed a Fibonacci-like rule that related one value in my 
table to the two values directly above it. I have not yet proved that 
this rule works. I have also not yet found a second solution with an 
area divisible by 20, because the numbers got too large for my 
spreadsheet. So there is plenty of work left to be done.

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/   

Date: 05/29/2001 at 14:29:55
From: Malav Pandya
Subject: Re: To find the triangle length depending on the condition

Hello sir,

I got this problem from a family friend, and at least seven people 
have been working on it for the last 30 days, but we could not even 
manually figure it out. We tried to reach a solution by comparing the 
area of a triangle with different equations such as 1/2bh and 
sqrt(s(s-a)(s-b)(s-c)), but are still not getting anything near it, 
and it's too long to go for it manually. I wrote a program in C 
language but it's not giving the answer, though I don't know where the 
problem is.

Dr. Math is a well-known math solver I know and trust, so I e-mailed 
it to you guys. The rest is up to you.  Thank you very much for taking 
an interest. I appreciate it.

Best of luck and thank you once again.
- Malau

Date: 05/30/2001 at 11:27:30
From: Doctor Rick
Subject: Re: to find the triangle length depending on the condition

Hi, Malav.

Thanks for writing back! I had wondered if this was related to a class 
in number theory, but I guess not. There is interesting math here 
beyond the solution of your problem. It led me to study a significant 
topic in number theory with which I was not familiar.

To restate the problem: A triangle has sides whose lengths are 
consecutive integers. Its area is a multiple of 20. Find the smallest 
triangle that satisfies these conditions.

This is what I did. Start with Heron's formula for the area of a 
triangle in terms of the three sides a, b, and c:

  s = (a+b+c)/2 (the semi-perimeter)

  K = sqrt(s(s-a)(s-b)(s-c))

Define the consecutive side lengths in terms of the middle number, 
rather than the first. I often find that such a "symmetrical" choice 
of variable allows some terms in my equations to cancel out. Thus, the 
three sides are

  a = n-1; b = n; c = n+1

Using these sides, we get for the area squared

  K^2 = 3n^2(n+2)(n-2)/16

Under what conditions will this triangle have an integer area? Clearly 
we have a condition:

  3n^2(n+2)(n-2) = 16K^2

where K is some integer.

We can simplify the condition. If n is odd, then none of the factors 
n, n+2, and n-2 will have a factor of 2. But their product must be a 
multiple of 16, so it must be that n is even. Therefore, let

  n = 2m

and recast our condition in terms of m:

  3m^2(m+1)(m-1) = K^2

Divide through by m^2:

  3(m+1)(m-1) = (K/m)^2

Since the left side is an integer, k/m must be an integer. Define

  K = pm

and our condition becomes

  3(m+1)(m-1) = p^2

One more change: note that, if p^2 is divisible by 3, then p must be 
divisible by 3, since 3 is prime. Thus we can define

  p = 3q

making our condition

  (m+1)(m-1) = 3q^2

This can also be written

[1]  m^2 - 3q^2 = 1

At this point I went to a spreadsheet to test values of q up to 1000. 
You could easily write a program to do the same. For each value of q, 
compute sqrt(3*q*q+1). Take the nearest integer; this will be m. Then 
calculate m*m-1 and see if the result is equal to 3*q*q. If so, you've 
found an integer solution to [1].

I found the following values of q that gave integer values of m:

    q  m=sqrt((q^2-1)/3)  K=3qm   sides=2m-1, 2m, 2m+1
------------------------------------------------------
    1               2         6   3,4,5 (familiar right triangle)
    4               7        84   13,14,15
   15              26      1170   51,52,53
   56              97     16296   193,194,195
  209             362    226974   723,724,725
  780            1351   3161340   2701,2702,2703

That last line is the smallest solution to the original problem, 
because the area K=3161340 is divisible by 20.

As I said before, this spreadsheet or programming approach is not very 
satisfying to me; it doesn't give me any insight into the problem, nor 
does it tell me whether there are any larger solutions, let alone how 
big they might be. I want to dig deeper.

While trying to find a way to find solutions of [1] without brute-
force testing, I noticed that each value of m in the table is roughly 
4 times the value above it. Looking more closely, I was surprised to 
discover this Fibonacci-like recursive rule that fits the table so 
far:

  m[0] = 1, m[1] = 2
  m[i] = 4m[i-1] - m[i-2]

Putting the recursive formula into the spreadsheet gave me 13 more 
values of m that work, before the numbers get too big for the 
spreadsheet's 10-digit precision. The formula appears to work - but 
this is not a mathematical proof; the rule may be just a fluke. Can we 
prove that the rule gives exactly the solutions of [1]?

We are in the realm of number theory, and I am no expert; I need to go 
to books for this. In particular, I looked at an old book in my 
library: Uspensky and Heaslet, Elementary Number Theory.

I found that Fermat in 1657 challenged mathematicians "to prove that 
the equation

[2]  t^2 - au^2 = 1

has infinitely many solutions and to invent a method for the discovery 
of all of them. ... The first complete proof and exhaustive discussion 
of Fermat's equation was made by Lagrange in 1767, and his work stands 
as an outstanding achievement in the history of the theory of 
numbers." This is exactly our problem, with a = 3.

The explanation of the solution requires a lot of preparatory 
knowledge that I am not competent to give. Here is the solution given 
in my book:

Let T and U be the smallest positive integers that satisfy eq. [2]. In 
our case (a = 3), T=1 and U=2 (see my table). If t, u is any other 
solution in positive integers, then

  t + u*sqrt(a) = (T + U*sqrt(a)^n

Thus, in our case, all solutions (m, q) of [1] can be found by 
computing the rational and irrational parts of

  m + q*sqrt(3) = (2 + sqrt(3))^n

for n = 1, 2, 3, ...

Let's do a few, to see that they match my results. For n = 2, we have

  (2 + sqrt(3))^2 = 4 + 4*sqrt(3) + 3

  m = 7, q = 4

For n = 3:

  (2 + sqrt(3))^3 = (7 + 4*sqrt(3))(2 + sqrt(3))
                  = 26 + 15*sqrt(3)

  m = 26, q = 15

In general:

  (2 + sqrt*(3))^n = (m[n-1] + q[n-1]*sqrt(3))(2 + sqrt(3))
                   = 2m[n-1] + 3q[n-1] + (m[n-1] + 2q[n-1])sqrt(3)

  m[n] = 2m[n-1] + 3q[n-1]
  q[n] = m[n-1] + 2q[n-1]

Thus we have a recurrence relation for q and m together. I'd like to 
get a recurrence relation in m alone, to compare with my observation. 
We can do this as follows. Write the recurrence relations for m[n-1] 
and q[n-1]:

  m[n-1] = 2m[n-2] + 3q[n-2]
  q[n-1] = m[n-2] + 2q[n-2]

Along with the relation for m[n], we have three equations in 6 
variables. We want to eliminate the q's. First, eliminate q[n-2] from 
the last pair:

  2m[n-1] - 3q[n-1] = 4m[n-2] - 3m[n-2]

Use this to eliminate q[n-1] from the m[n] relation:

  3q[n-1] = 2m[n-1] - 4m[n-2] + 3m[n-2]

  m[n] = 2m[n-1] + 2m[n-1] - 4m[n-2] + 3m[n-2]
       = 4m[n-1] - m[n-2]

There, we've derived my recurrence relation from Lagrange's solution 
to Fermat's equation!

I leave further consideration of the "area divisible by 20" part of 
the problem to you. I've labored enough on the problem of integer 
area. It was fun, though; I learned something new!

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/   

Date: 05/30/2001 at 12:04:17
From: Malav Pandya
Subject: Re: To find the triangle length depending on the condition

Hello sir,

Thank you very, very much. I can write a C program for what you have 
given me in terms of equations. For me, the right solutions and 
equations are important, so thank you very much!

Have a nice day,
Malau