## 2008年12月6日 星期六

### A Solution to the "Ten-Minute" Problem

It should be easy to observe that z must be odd. We are looking for positive integer solution to

$4024x+4178y=3757057-4609z$

By manually doing division algorithm once, you can show that $gcd(4024,4178)=2$. Simultaneously, you can find a particular integer solution to $4024x'+4178y'=2$, which is

$x'=-624$
$y'=601$

Now, set $2a=3757057-4609z$ Then we have

$x =-624a-2089K$
$y =601a+2012K$

as general solution. To keep x and y both positive, we may have a "sense" that when $-624a(\mod 2089)$ is small, we can adjust K to keep x small but positive, and hence "allow room" for y to be positive.

Take $z=1$, we have $a=1876224$. However, $-624a\equiv 1651(\mod 2089)$. The remainder 1651 is too large to be x.

Now observe that when z is increased by 2, a drops by 4609. Notice $-624\times 4609\equiv 537(\mod 2089)$. That means when we increase z by 2, $-624a(\mod 2089)$ drops by 537.

Increase z from 1 to 7, $-624a(\mod 2089)$ drops from 1651 to $1651-3\times 537=40$. Setting $x=40$, we get $y=853$. A possible solution is given by

$x = 40$
$y = 853$
$z = 7$