Thursday, 7 July 2011

Problem on divisibility and GCD

1) For x,y,z are positive integer, $\frac{1}{x}+\frac{1}{y}=\frac{1}{z}$, $(x,y,z)=1$, show that x+y, x-z and y-z are perfect squares.
There are quite a lot of methods to proof a number involved in a equation as a perfect square, we will finish this one by the factorization method introduced last time.
Recall that $(k_{x},k_{y},k_{z})=(k_{xy},k_{xz},k_{yz})=1$
Since $(x,y,z)=1$, $k_{xyz}=1$.
Consider $x+y=\frac{xy}{z}=\frac{k_{x}k_{y}}{k_{z}}(k_{xy})^2$, what we are going to proof is that $\frac{k_{x}k_{y}}{k_{z}}=n^2$, but of course it's good if it is 1, so we will proof that $k_{x}=k_{y}=k_{z}=1$ by showing that $\prod k_{xy}$ is equal to x,y or z.
When $\frac{xy}{z}$ is an integer, we say all factors of z has been used up by x and y, then $k_{xz}k_{yz}=z$, then obviously $k_{z}=1$. Similarly (Q1) we can show similar case for x and y. Then $x+y=k_{xy}^2$ and the proof is done. The proof for (x-z) and (y-z) is left for readers.

A famous solution on IMO 1988 Q6, where a,b are positive integers and $\frac{a^2+b^2}{ab+1}=k$is a integer, then it's a perfect square. The following infinite descent method is done by a contestant who won a special prize that year.
Assume k is not perfect square, then k>2. Since the expression is symmetrical we WLOG assume $x\geq y$, but for x=y, k<2 and the assumption can't stand, therefore a > b.
Consider the minimal pair of a+b. Consider the following equation $x^2-kbx+b^2-k=0$, by the given information a is one of the root. Let a' be another root. By Viete's theorem, $a+a'=kb$, $aa'=b^2-k$, then a' is an integer. Note that a' is also a set of solution that $\frac{a^2+b^2}{ab+1}=k$.
By $k(1+a'b)=a'^2+b^2>0$, b>1, then we have a'>0.
Also, $a'=\frac{b^2-k}{a}<\frac{b^2}{a}<a$, a'+b is smaller than a+b, contradicts the assmption that a+b is the minimal solution. Then k must a perfect square.

Q1 Refer to the bolded line, proof that $k_{x}=k_{y}=1$.
Q2 We have only proofed x+y is a perfect square only so far. Finish the proof by using similar idea with Q1.
Q3 Find number of pairs of natrual number where a-b is a prime and ab is perfect square.
Q4 a,b,c are natrual numbers, a=20, b|c, find all triples (a,b,c) that a,b,c are in harmonic progression.
Q5 Find all natural number triples (a,b,c) that [a,b,c]=a+b+c.
Q6 Show for all integer n>11, $n^2-19n+89$ is not a perfect square.
Q7 Find all positive interger n such that $n^2+89n+2010$ is a perfect square.

Extra question:
The proof on IMO 1988 Q6 is based on the contradictory point between (1) a+b is minimal; (2) k is not a perfect square. [i.e. prove by contradictory since (1) => (2) => ~(1)]
Then, show that how the proof failed when k is a perfect square.

No comments:

Post a Comment