Contest Problem - Divisibility

347 Views Asked by At

Find all ordered pairs (x, y) of positive integers x, y such that $x+y$ divides 2014 and (simultaneously) $x^yy^x$ divides $(x+y)^{(x+y)}$ .

This is a contest problem from U Tenn, FERMAT contest.

My try:

Let S = x+y

The prime factorization of 2014 is {2,19,53}

S divides 2014 would mean S = 2,19,38,53,106,1007.

The condition that it should simultaneously hold the second condition would lead to

$$x^{(S-x)}(S-x)^x *K = S^S$$

$$\frac{(x+y)^x}{y^x}\frac{(x+y)^y}{x^y}= k$$

$$\left(1+\frac{x}{y}\right)^x\left(1+\frac{y}{x}\right)^y = k$$

If x and y are positive integers the Left Hand side could never be a whole number and k will not be an integer. Thus x = y.

Further x = y can only hold for even possibilities of S which again is 38 and 106.

Therefore the ordered pair (x,y) that satisfy both divisibility rules are:

(19,19) and (53,53).

Correct me if I am wrong.

2

There are 2 best solutions below

2
On BEST ANSWER

The assertion that the product of your rationals can only be an integer if $x=y$ is correct, but needs proof.

I prefer to work directly with integers. We are told that $x^yy^x$ divides $(x+y)^{x+y}$. Let $d=\gcd(x,y)$, and let $x=da$ and $y=db$. Then $a$ and $b$ are relatively prime. Our divisibility condition says that $d^{x+y} a^yb^x$ divides $d^{x+y}(a+b)^{x+y}$. It follows that $a^yb^x$ divides $(a+b)^{x+y}$. Suppose that one of $a$ or $b$, say $a$, is greater than $1$. We have that $a^y$ divides $(a+b)^{x+y}$. This is impossible since $a$ and $a+b$ are relatively prime.

Thus $a=b=1$ and therefore $x=y$.

0
On

Your reasoning is nice but you missed an easy one: $x=y=1$. That is what you get if you look at $S=2$.