9

I came across an old Putnam problem that i was having some difficulty with, and I was wondering if I could get some assistance of this community.

For a given positive integer $m$, I need to find all the triples $(n,x,y)$ of positive integers, with $n$ relatively prime to $n$, which statisfy $$(x^2+y^2)^m = (xy)^n.$$

At first it seems like the best place to start is through some form of relevant base cases, i.e. starting with $m = 2, n = 3.$ i.e. find $x$ and $y$ solutions such that $$(x^2+y^2)^2 = (xy)^3$$ $$\implies x^4 + 2x^2y^2 + y^4 = x^3y^3.$$

I can tell that this holds for $x = 0, y = 0,$ but how would I go about finding all cases from even this one example? This seems very unweildy when we consider high degree polynomials. What is the best strategy to tackle this kind of problem?

Barbara
  • 281

2 Answers2

2

John Scholes answers this (and almost all Putnam problems) on his site:

https://mks.mff.cuni.cz/kalva/putnam/psoln/psol923.html

It's rather terse, so expanding on it a little here; start by extracting the $gcd(x,y)=g$

$x=gX, y=gY$

$((gX)^2+(gY)^2)^m=(gXgY)^n$
$\therefore (g^2X^2+g^2Y^2)^m=g^{2n}(XY)^n$
$\therefore g^{2m}(X^2+Y^2)^m=g^{2n}(XY)^n$
$\therefore (X^2+Y^2)^m=(XY)^ng^{2(n-m)}$

Now $X$ and $Y$ have no shared divisors, because we divided out the $gcd$. So if $p$ is a divisor of $X$ then it divides the $RHS$ but not the $LHS$, because $p$ would also have to divide $Y$, but $Y$ does not share the divisor $p$. So $X=1$. By the same argument $Y=1$. So that last line becomes:

$(1 + 1)^m=(1.1)^ng^{2(n-m)}$
$\therefore 2^m=g^{2(n-m)}$

That same line also tells us that $g | (X^2+Y^2)^m=2^m$, so $g$ is a power of $2$.

$x=gX = g.1 = 2^r$, for some integer $r$. Similarly for $y=2^r=x$.

We now have $x,y$ so substituting into the original equation:

$(2^{2r}+2^{2r})^m=(2^r.2^r)^n$
$\therefore 2^{(2r+1)m}=2^{2rn}$
$\therefore (2r+1)m=2rn$

But $2r+1$ and $2r$ are coprime. So all the factors of $2r+1$ must be in $n$, or $n=N(2r+1)$ and similarly $m=M.2r$. Substituting and cancelling gives $M=N$. But $m,n$ are coprime. So $M=N=1$.

So in summary $x=y=2^r$, $m=2r, n=2r+1$. Or alternatively, $m$ must be even and the only solution is $n=m+1, x=y=2^{m/2}$.

Roger Marlow
  • 171
  • Just out of curiosity (great answer!), in what math course would you solve problems such as these – Mike H Apr 02 '18 at 01:48
  • Concepts such as GCD and co-primality are taught in schools, and again at university in maths and comp sci degrees. But that's not really what these questions are about: these are competition problems. It is often not clear which concepts to apply. Plus you typically need four or five insights strung together with deft "plug and chug" skills to get to the answer. So as well as your understanding they are testing your tenacity, patience and accuracy. And they are hard to teach. They only come with practice. Putnam in particular is famously difficult: in 1999 and 2000 the median score was zero! – Roger Marlow Apr 02 '18 at 09:14
  • Thank you. Since the tag was just polynomials I wasn't sure if it fell under some kind of higher math – Mike H Apr 02 '18 at 14:42
1

Another place to find discussion of old Putnam problems is: The Art of Problem Solving

GEdgar
  • 111,679