Tag Archives: proof

Applications of Complex Number Analysis to Divisibility Problems : Two Undergrad Problems

Posted on by

Problem
  1. Prove that {(x+y)}^n-x^n-y^n is divisible by xy(x+y) \times (x^2+xy+y^2) if n is an odd number not divisible by 3.
  2. Prove that {(x+y)}^n-x^n-y^n is divisible by xy(x+y) \times {(x^2+xy+y^2)}^2 if n \equiv \pmod{6}

Solution
1.Considering the given expression as a polynomial in y , let us put y=0 . We see that at y=0 the polynomial vanishes (for any x ). Therefore our polynomial is divisible by y. Similarly, it is divisible by x as well. Thus the polynomial is divisible by xy.
To prove that it is divisible by x+y , put x+y=0 \ {or} \ y=-x . It is evident that for odd n we have : {(x+(-x)}^n-x^n-{(-x)}^n = 0 for y=-x .
Consequently, our polynomial is divisible by x+y . It only remains to prove the divisibility of the polynomial by x^2 +xy+y^2 , which also be written as (y-x\epsilon)(y-x{\epsilon}^2 ) where \epsilon^2+\epsilon+1=0 .
For this purpose it only remains to replace y first by x \epsilon and then by x\epsilon^2 to make sure that with these substitutions the polynomial vanishes. Since, by hypothesis, n is not divisible by 3, it follows that n=3l+1 \ or \ 3l+2 , for every l \in \mathbb{Z} , in which 3l+1 is not acceptable since n is odd from the problem. At y=x\epsilon the polynomial attains the following value
{(x+x\epsilon)}^n-x^n-{(x\epsilon)}^n=x^n [{(1+\epsilon)}^n-1-\epsilon^n] \\ =x^n {(-\epsilon^2)}^n -1 -\epsilon^n .... since (1+\epsilon + \epsilon^2=0 ) substituting n=3l+2 we get
1+\epsilon+\epsilon^2 =0
Likewise we prove that at y=x\epsilon^2 the polynomial vanishes as well, and consequently, its by divisibility by xy(x+y) \times (x^2+xy+y^2) is proved.
2.To prove the second statement, let us proceed as follows. Let the quantities {-x, -y, \, and \, x+y} be the roots of a cubic equation X^3-rX^2-pX-q=0 . Then by virtue of the known relations between the roots of an equation and its coefficients we have r=-x-y-(x+y)=0 \\ -p=xy-x(x+y)-y(x+y) or p=x^2+xy+y^2 and q=xy(x+y).
Thus, -x, \, -y \, x+y are the roots of the equation X^3-pX-q=0 where p=x^2+xy+y^2 and q=xy(x+y)
Put {(-x)}^n-{(-y)}^n+{(x+y)}^n=S_n. Among successive values of S_n, there exist the relationship S_{n+3}=pS_{n+1}+qS_n,: S_1 being equal to zero.
Let us prove that S_n is divisible by p^2 if n \equiv 1 \pmod{6} using the method of mathematical induction. Suppose S_n is divisible by p^2 and prove that then S_{n+6} is also divisible by p^2.
So, using this relation we get that
S_{n+6}=p(pS_{n+2} + qS_{n+1}) + q(pS_{n+1}+qS_n) \\ =p^2S_{n+2}+2pqS_{n+1}+q^2S_n.
Since, by supposition, S_n is divisible by p^2 , it suffices to prove that S_{n+1} is divisible by p. Thus we only have to prove than S_n={(x+y)}^n+(-x)^n+(-y)^n is divisible by p=x^2+xy+y^2 if n \equiv 2 \pmod{6}, we easily prove our assertion. And so, assuming that S_n is divisible by p^2, we have proved that (from induction) S_{n+6} is also divisible by p^2. Consequently S_n ={(x+y)}^n+(-x)^n+(-y)^n={(x+y)}^n-x^n-y^n for any n \equiv 1 \pmod{6} is divisible by p^2={(x^2+xy+y^2)}^2 .
Now it only remains to prove its divisibility by x+y and by xy , which is quite elementary.