Thursday, 7 July 2011

Problem on divisibility and GCD

1) For x,y,z are positive integer, 1x+1y=1z, (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.
Assume
x=kxkxykxzkxyz
y=kykxykyzkxyz
z=kzkxzkyzkxyz
Recall that (kx,ky,kz)=(kxy,kxz,kyz)=1
Since (x,y,z)=1, kxyz=1.
Consider x+y=xyz=kxkykz(kxy)2, what we are going to proof is that kxkykz=n2, but of course it's good if it is 1, so we will proof that kx=ky=kz=1 by showing that kxy is equal to x,y or z.
When xyz is an integer, we say all factors of z has been used up by x and y, then kxzkyz=z, then obviously kz=1. Similarly (Q1) we can show similar case for x and y. Then x+y=k2xy 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 a2+b2ab+1=kis 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 xy, 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 x2kbx+b2k=0, by the given information a is one of the root. Let a' be another root. By Viete's theorem, a+a=kb, aa=b2k, then a' is an integer. Note that a' is also a set of solution that a2+b2ab+1=k.
By k(1+ab)=a2+b2>0, b>1, then we have a'>0.
Also, a=b2ka<b2a<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 kx=ky=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, n219n+89 is not a perfect square.
Q7 Find all positive interger n such that n2+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