Conference rusure::math

The first non-trial-and-error solution that comes to mind is available
through the greatest common divisor algorithm applied to (85,41):
85 = 2(41) + 3
41 = 13(3) + 2
 3 = 2     + 1
Now solve for 1 in terms of 41 and 85:
 1 = 3 - 2
   = 3 + 13(3) - 41
   = 14(3) - 41
   = 14(85 - 2(41)) - 41
   = 14(85) - 29(41)
So one solution is X = 29 and Y = 14.  A bunch (countably many) of others
are {(X,Y)| X = 29 + 85n, Y = 14 + 41n, n is an integer}.  I suspect that
this exhausts neither the solutions nor the methods which might be applied.
I would call it "trial-and-error once removed".
--Joe

    re. .1
    
         In general:
    
            The equation  mx + ny = k  is solvable in integers if and
            only if  (m.n) divides k.
                    
    
    Some more problems:
    
       1:   Solve the Diophantine equation  mx + ny = (m,n) for
            m = 5775,  n = 1008.
                                                               
       2:   solve   18203x - 9077y = 17
    
       3:   Is the Diophantine equation  111x + 69y = 191 solvable?
    
       4:   Give all solutions of the Diophantine equation  
            32x + 14y = 22.
    
    
    Enjoy,
    
    Kostas G.
    
    
    =

    Re .1: 

    The solutions you give are all of the solutions.  To prove this,
    consider a general linear Diophantine equation in two variables, Ax+By
    = C.  Without loss of generality, assume A and B are relatively prime.
    There is a number A' such that A'A is congruent to one modulo B
    (construction of this number is given in another note).  Consider
    A'Ax+A'By = A'C.  Since A'By is a multiple of B, A'Ax is congruent to
    A'C modulo B.  A'A is congruent to one, so A'Ax is congruent to x, so x
    is congruent to A'C modulo B.  Thus, for every solution, x is congruent
    to A'C modulo B, so the set of solutions is limited.  For each x
    congruent to A'C modulo B, observe that By = C-Ax.  C-Ax is congruent
    to C-A(A'C) modulo B, or to C-A'AC.  Since A'A is congruent to one,
    A'AC is congruent to C, so C-A'AC is congruent to 0, so C-Ax is a
    multiple of B, so y = (C-Ax)/B is an integer.  We see that each value
    of x such that x is congruent to A'C modulo B provides a solution for
    the equation, and only those values of x do so. 


    Re .2: 

       > 1:   Solve the Diophantine equation  mx + ny = (m,n) for
       >      m = 5775,  n = 1008.

    x = 11-48k, y = -63+275k. 

       > 2:   solve   18203x - 9077y = 17

    x = 3520+9077k, y = 7059+18203k. 
    
       > 3:   Is the Diophantine equation  111x + 69y = 191 solvable?

    No. 
    
       > 4:   Give all solutions of the Diophantine equation  
       >      32x + 14y = 22.

    x = -5+7k, y = 13-16k. 


				-- edp
                          

    RE. .3
    
    Also some more solutions to 2: and 4:
    
    2:         18203x -9077y = 17
    
               x = 17 * 741  = 12,597
               y = 17 * 1486 = 25,262
    
    4:         32x + 14y = 22
    
               x = -33
               y = 77
    
               The general solution is
               x = -33 + 7i
               y = 77 - 16i          where (i=0, +1, -1, +2, -2, ...)
    
    KGG
    
    

Thanks to edp (.3) for doing my dirty work.  Eric, was this an idle
question, or does the answer have some application?  Was there a more
general set of problems?  Have they been addressed?
--Joe

    Re .4:
    
    .3 contains general solutions.
    
    
    				-- edp

    In answer to Joseph's question about why I wanted to solve that
    particular Diphontine equation.  It's actually of novel use.
    
    Start with it:
    
    41X-85Y=1

    Multiply through by 160:
    
    41X*160-85Y*160=160
        
    Assume the following equivalences:
    
    y=Y*160
    x=X*160
    
    So we have
    
    41x-85y=160
    
    massage:
    
    41x-85y=160
    85y-41x=-160
    90y+9x=50x+5y-160
    10y+x=(50x+5y-160)/9
    10y+x=5(10x+y-32)/9
    
    Now, assume the following equivalences:
    
    c=10y+x
    f=10x+y
    
    Substituting, we have:
    
    c=5(f-32)/9
    
    but what's this ?  Just the formula for converting Fahrenheit to
    Celsius temperatures !
    
    And because our c and f are 10y+x and 10x+y, then if we solve for
    x and y, we'll know what two-digit temperature(s) can be converted
    merely be reversing their digits.  Of course, the further restraint
    must be made that c and f are between 1 and 9 inclusive.
    
    Please see other recent topics about Fahrenheit to Celsius
    conversions, both in MATH and BRAIN_BOGGLERS conferences.
    
    /Eric

Let c=5(f-32)/9, and let's find a integer solution (c,f) such that
f is a 'reversal' of c.

Now (5x, 9x+32) is the set of integral solutions of c=5(f-32)/9.
We want to disallow any c that ends with a 0 (because), and so we
instead take (10x+5,18x+41) as the set of possible solutions.  Thus,
c should end with, and f should start with, a 5.

Since f starts with a 5, we know that c starts with either a 2 or 3
(actually, c's starting digits are in the range of 277... thru 333...).
Thus, f must end with either a 2 or 3.  But, 18x+41 cannot end with
a 2, and so our potential solutions are (50x+45,90x+113).

This greatly reduces the search space.  Using this, it's easy to discover
(with the aid of la computer) that there is no positive integral solution
with c < 100,000,000.

Continuing, we see that c must end with either 45 or 95.  Thus, f must
start with either 54... or 59..., and so c must start with either
3000... thru 3055... or 3277... thru 3333..., respectively, and so f must
end with either 03, 23, or 33.  However, note that if c ends with 45, the
solutions are (100x+45,180x+113), and so f cannot end with 03.

If c ends with 95, our general solution is (100x+95,180x+293), and we
need f to end with either 23 or 33.  But 180x+293 cannot end with 23,
so f must end with 33, and we have (100(5x+4)+95,180(5x+4)+293) =
(500x+495,900x+1013) as our general solution.

Thus c ends with 95 and f ends with 13.  Similarly, f begins with 59
and c begins with 31.  However, given these bounds on the magnitudes
of c and f, we see that c=5(f-32)/9 cannot be satisfied!

Note that the above argument did not consider negative amounts, nor
values of c that end with a 0.  Perhaps there is a solution in one of
these areas (or perhaps I erred in my hasty calculations).  The above
techniques can be used to search these other solution spaces, as well.

					- Gilbert

    
    I hate to have to ask, but how did you get from the modulo theory
    to the solutions of .2's examples? It's been a while for me, but
    I was curious about what note the construction of your A' was in,
    or at least how it is related to the solutions you offered, which
    are rather nice, thank you. I can see bit and pieces of the action,
    but can't quite put it all together to try ti out on an application
    with denominations of travelers checques here at the office. Any ideas?
             D. Martin  clever::rmartin

     RE: .3

       I have worked with some info from Mr. Postpischil, and he has helped
     me to set up a way to generate the A' needed in any situation. It goes
     like this with the equation below as an example:

     Solve  17X + 80Y = 7

     A = 17, B = 80, C = 7

     We start by setting up a generating number table, with the first 2 entries
     always equal to 0, 1 as below:

      f1 f2 f3 f4 f5 f6      
      -- -- -- -- -- --
      0,  1

     Then we divide A into B to get:

     B/A = Q remainder of R;
     in this case

     80/17 = 4 remainder of 12

     Now to get the next factor in the table, we say

     f3 = f1 - Q * f2, 

     in this case f3 = 0 - 4*(1)= -4 and now our table becomes:

     f1  f2  f3  f4  f5  f6      
     --  --  --  --  --  --
     0,  1   -4

     To find f4 we make our old divisor the new dividend, and our old remainder
     the new divisor (as in the Euclidian algorithm), and continue:

     f4 = f2 - Q * f3  so  17/12 = 1 remainder of 5 and f4 becomes

     1 - (1) * (-4) = 5, and the table becomes

     f1  f2  f3  f4  f5  f6      
     --  --  --  --  --  --
     0,  1   -4   5

     And so the process continues:

     12/5 = 2 remainder of 2 so f5 = f3 - Q * f4; f5 = -4 - (2) * (5) = -14

     so the table is

     f1  f2  f3  f4   f5  f6      
     --  --  --  --  ---  --
     0,  1   -4   5  -14

     One more time for this particular example

     5/2 = 2 remainder of 1, so f6 = f4 - Q * f5; f6 = 5 - (2) * (-14) = 33

     and the table becomes

     f1  f2  f3  f4   f5  f6      
     --  --  --  --  ---  --
     0,  1   -4   5  -14  33

     2/1 = 2 remainder of 0; divisor = 1 when remainder = 0 means (17,80) were
     relatively prime, and remainder = 0 shows us that at this point, f6 = A'

     (If current_divisor > 1 when remainder = 0, (A,B) are not relatively prime;
     the equation has no solution if C/(current_divisor) is not an integer.)

     Now, to test it out on the original equation 17X + 80Y = 7 (Let "=="
     mean congruent; "#" mean modulo):

     X == 33 * 7 # 80

     But 33 * 7 = 231, so x == 231 # 80, so X = 71 + 80K, K being an integer

     17(71 + 80K) + 80Y = 7

     1207 + 1360K + 80Y = 7

     80Y = -1200 - 1360K

     Y = -15 - 17K

     Does 17(71 + 80K) + 80(-15 - 17K) = 7 ?

     1207 + 1360K - 1200 -1360K = 7 ?

     Yes. 1207 - 1200 + 1360K - 1360K = 7

     Many thanks to others for showing me this.

     Just for kicks and whatever else it may be worth.

     Dick Martin


Article: 22043
From: [email protected] (Chris Long)
Newsgroups: rec.puzzles,sci.math
Subject: Another Diophantine Puzzler
Message-ID: <[email protected]>
Date: 26 Oct 91 22:32:20 GMT
Organization: Rutgers Univ., New Brunswick, N.J.
 
 
Find the smallest rational number x (smallest in the sense of smallest
numerator and denominator) such that there exist rational numbers
y and z and
 
             x^2 - 157 = y^2, x^2 + 157 = z^2.
-- 
Chris Long, 272 Hamilton St. Apt. 1, New Brunswick NJ  08901  (908) 846-5569
 
"The proofs are so obvious that they can be left to the reader."
Lars V. Ahlfors, _Complex Analysis_

>Find the smallest rational number x (smallest in the sense of smallest
>numerator and denominator) such that there exist rational numbers
>y and z and
 
>             x^2 - 157 = y^2, x^2 + 157 = z^2.

We can get into the realm of integers fairly easily: let x=x1/x2, y=y1/y2;
then the first equation becomes

	x1^2*y2^2 - 157*(x2*y2)^2 = y1^2*x2^2

and since {x1,x2} and {y1,y2} are assumed relatively prime, we have

	y2 | x2 and x2 | y2, so x2 = y2, and
	x1^2 - 157*x2^2 = y1^2

If now we set y1 = 1, this becomes a "Pellian" equation and there are 
standard, but laborious by hand, methods for solving them using continued
fractions. One solution (for y1 = 1) is

        {x1 = 46698728731849, x2 = y2 = 3726964292220}

I leave the second equation, and the simultaneous solution of both, to the 
interested reader :-) .

    The Modulo inverse described in .3 is also referenced in
    HEAVY::ALGORITHMS, note 5 and replies.