Applying Euler's Methods

Date: 07/27/99 at 11:53:17
From: Tamara Cunningham
Subject: Euler, Math History

I have a few questions for you that have come up in my History of 
Mathematics class where we are studying Euler. If you don't know the 
answers could you tell me how to get started? I'm going to list 
several questions and would appreciate any help you can provide on any 
or all of them. Thank You!

1) Find a prime divisor smaller than 1103 for 5368709011, which is 
   equivalent to (2^29)-1.

2) Find a prime divisor of (2^83)-1.

3a) Describe precisely the steps for the ruler-and-compass 
    construction of a triangle ABC given its centroid G, circumcenter 
    O, and vertex A.

 b) Same as (a) but with a given orthocenter H, circumcenter O, and 
    vertex A.

 c) Same as (a) but with a given incenter I, circumcenter O, and 
    vertex A.

4) How would you decompose quartic polynomials into the product of 
   two quadratic polynomials with real coefficients?

For Example:

     x^4 + a^4
     X^4 + 4X^3 + 8X^2 + 4X + 1
     X^4 - 4X^3 + 2X^2 + 4X + 4

5) What are 3 positive rational roots for

     2X^3 - 35X^2 + 202X - 385 = 0?

Thank you in advance for all your help!

Date: 07/27/99 at 13:26:39
From: Doctor Rob
Subject: Re: Euler, Math History

Thanks for writing to Ask Dr. Math!

(1) and (2):
Every prime factor q of 2^p - 1 must have the form q = 2*a*p + 1, if p 
is a prime number. This restricts the number of trials you have to 
make. For each trial, you can compute the sequence 2^n (mod q) for
n = 3, 6, 7, 14, 28, 29 (for problem 1) and for n = 5, 10, 20, 40, 41, 
82, 83 (for problem 2). If the last one is 1, you have a divisor. If 
not, you don't. For example: The first trial for p = 29 is with a = 1, 
q = 2*1*29 + 1 = 59. Then

      2^3                            =   8 (mod 59),
      2^6 = (2^3)^2  = 8^2     =  64 =   5 (mod 59),
      2^7 = 2*(2^6)  = 2*5           =  10 (mod 59),
     2^14 = (2^7)^2  = 10^2    = 100 = -18 (mod 59),
     2^28 = (2^14)^2 = (-18)^2 = 324 =  29 (mod 59),
     2^29 = 2*(2^28) = 2*29    =  58 =  -1 (mod 59),

so 59 is not a factor. 

Next a = 2, q = 117 is not prime.
Next a = 3, q = 175 is not prime.
Next a = 4, q = 233 is prime, and has to be tested.
You finish.

3) In each part, you have a vertex A and the circumcenter O. The other 
two vertices must lie on the circumcircle, with center O and radius 
OA. The trick is to use the third piece of information to restrict 
their locations to just two points on the circumcircle. For this, you 
can use the fact that the orthocenter, incenter, circumcenter, and 
centroid have a known relation to each other (known to Euler, that 
is). You finish.

4) These are done by factoring using a difference of squares. The 
trick is to find terms to add or subtract that will make most of the 
polynomial into a square. Thus the first one looks like (x^2+a^2)^2, 
except one term is missing: 2*a^2*x^2. If you add it in the middle, 
and subtract it at the end, you'll have the difference of two squares:

     x^4 + a^4 = (x^2+a^2)^2 - (sqrt[2]*a*x)^2.

The second one is similar, because it is almost (x+1)^4. The third one 
helps if you substitute x = y + 1, in which case it reduces to

     y^4 - 4*y^2 + 7

This is almost (y^2+sqrt[7])^2, and you can make it so by adding and 
subtracting the right term. Then express the result as a difference of 
squares, factor, and put y = x - 1.

5) The Rational Root Theorem says that if this polynomial has a 
rational root, its numerator must be a divisor of the constant term 
385, and its denominator must be a divisor of the leading coefficient 
2. The only possibilities are 385, 77, 55, 35, 11, 7, 5, 1 and their 
halves 385/2, 77/2, 55/2, 35/2, 11/2, 7/2, 5/2, and 1/2.

Now the sum of the roots is 35/2, which is the negative of the 
coefficient of the x^2 term divided by the leading coefficient. The 
product of the roots is 385/2, which is the negative of the constant 
term divided by the leading coefficient. Since the sum of the roots is 
35/2, all possibilities greater than this are eliminated, and you are 
down to 11, 7, 5, 1, 11/2, 7/2, 5/2, and 1/2. We have to choose three 
of these whose product is 385/2 = (5*7*11)/2, and whose sum is 35/2. 
One must have a 5 in the numerator, one a 7 in the numerator, and one 
an 11 in the numerator, and only one of the three can have a 2 in the 
denominator. There are three possible sets to test:

     {11, 7, 5/2}, {11, 7/2, 5}, and {11/2, 7, 5}.

Which one has sum 35/2?

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