Problems & Puzzles: Puzzles

Puzzle 146.  Solutions of A² +X² = Y², A = odd

Isaac Rojas, from Costa Rica, noticed (13/06/01) than in the equation A² +X² = Y² if A is an odd prime then there is only one solution-pair (x, y).

For example:

If A= 3 the the unique solution is (x, y) = (4, 5)

if A=5 then the unique solution is (x, y) = (12, 13)

But if A = 9 then the solutions are two: (x, y) = (12, 15) & (40, 41)

Solution

Several puzzlers attempted the solution of this puzzle, but only Chris Nash got (23/7/01) the complete one:

" ...We seek the number of solutions to A^2+X^2=Y^2 where A is odd. We note A^2=Y^2-X^2=(Y-X)(Y+X) In other words, every solution X,Y with Y>X>0 gives a factorization of A^2 into two distinct integers. Also the reverse applies - if A^2 is factorized into two distinct integers, PQ, (with P>Q) then both P and Q are odd, and a solution for X and Y exists - X = (P-Q)/2, Y=(P+Q)/2.

Hence the result we seek is the number of ways to factor A^2 into distinct integers. We recall the result:

If X=p1^r1.p2^r2.....pn^rn is the prime factorization of X, then X has precisely (r1+1)(r2+1)....(rn+1) distinct factors including itself and 1.

We find the prime factorization of A, let us call it p1^r1.p2^r2.....pn ^rn. Then A^2 has exactly (2.r1+1)(2.r2+1).....(2.rn+1) distinct factors. This is an odd number, and all of them can be paired to form two numbers whose product is A^2, except for A itself. Hence the number of solutions is exactly ((2.r1+1)(2.r2+1).....(2.rn+1) - 1)/2 where the r_i are the powers of the primes in the factorization of *A*.

For example, if A is prime, then r1=1, and the solution count is indeed 1. For A=9, the factorization has r1=2, and so the number of solutions is ((2*2+1)-1)/2=2. As another example, if A is the product of the first 100 primes, then the number of solutions is exactly (3^100-1)/2."