Thread: Problem 31
View Single Post
  #9  
Old July 22nd, 2007, 07:22 PM
ThePerfectHacker's Avatar
ThePerfectHacker ThePerfectHacker is offline
Global Moderator

  
Join Date: Nov 2005
Location: New York City
Posts: 11,186
Country:
Thanks: 482
Thanked 3,754 Times in 3,070 Posts
ThePerfectHacker has a reputation beyond reputeThePerfectHacker has a reputation beyond reputeThePerfectHacker has a reputation beyond reputeThePerfectHacker has a reputation beyond reputeThePerfectHacker has a reputation beyond reputeThePerfectHacker has a reputation beyond reputeThePerfectHacker has a reputation beyond reputeThePerfectHacker has a reputation beyond reputeThePerfectHacker has a reputation beyond reputeThePerfectHacker has a reputation beyond reputeThePerfectHacker has a reputation beyond repute
Default
Both of the problems I posted require the nice application of Complex Numbers.


The first problem was from the United States national competition. My solution differs slightly from the offical solution which is a little bit more elementary.

We will use something called the roots of unity. Given the equation z^n=1 there are exactly n complex solution given by:
\left\{ \cos \frac{2\pi 0}{n}+i\sin \frac{2\pi 0}{n} , \cos \frac{2\pi}{n} + i \sin \frac{2\pi}{n}, ... , \cos \frac{2\pi (n-1)}{n}+i\sin \frac{2\pi (n-1)}{n} \right\}
Hence,
\left\{ \cos \frac{2\pi k}{n} + i\sin \frac{2\pi k}{n} \right\} \mbox{ for }0\leq k\leq n-1
Is a complete set of solutions.
Now if k\geq 1 and \gcd(k,n)=1 then if \zeta = \cos \frac{2\pi k}{n}+i\sin \frac{2\pi k}{n} then \{\zeta , \zeta^2 ,...,\zeta^n\} is a complete set of solution. So that is basically what you need to know. I write them here as a chance to learn if you never did.


Now returning to the problem. We want to show x-1 divides f(x) which is equivalent to saying 1 is a zero of f(x), i.e. f(1)=0.

Before doing the problem there is one thing you need to know about roots of unity. The sum of the roots of unities is zero!

We know that,
f(x^5)+xg(x^5)+x^2h(x^5)=(x^4+x^3+x^2+x+1)r(x)
Let \zeta = \cos \frac{2\pi}{5}+i\sin \frac{2\pi}{5}.
Substitute that to get,
f(1)+\zeta g(1) + \zeta^2 h(1) = 0
Now \zeta^2 generates the set of roots of unity because \gcd(2,5)=1.
Thus,
f(1)+\zeta^2 g(1)+\zeta^4 h(1) = 0.
Now \zeta^4 also generates the set of roots of unitys because \gcd(4,5)=1.
Thus,
f(1)+\zeta^4g(1)+\zeta^3h(1)=0.

Note, we wrote \zeta^3 since \zeta^8 = \zeta^5 \zeta^3=\zeta^3.

What he have above is a homogenous system of linear equations. Note the determinant,
\left| \begin{array}{ccc}1&\zeta&\zeta^2\\1&\zeta^2&\zeta^4 \\ 1&\zeta^4&\zeta^3 \end{array} \right| \not = 0.
Which means there are only trivial solution.
Hence,
f(1)=0.
Q.E.D.
__________________

To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.


"Democracy has proved only that the best way to gain power
over people is to assure the people that they are ruling
themselves. Once they believe that, they make wonderfully
submissive slaves." - Joseph Sobran


To view links or images in signatures your post count must be 10 or greater. You currently have 0 posts.
The Following 2 Users Say Thank You to ThePerfectHacker For This Useful Post:
Donate to MHF