(Ny side: Problem10 ----) |
|||
| Linje 1: | Linje 1: | ||
Problem10 | Problem10 | ||
---- | ---- | ||
| + | Define <tex>f(n) = \sum^n_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{n}</tex>. We will be using that <tex>\sum^m_{k=1}\cos \frac{2 \pi k}{m} = \Re(\sum^m_{k=1}e^{i\frac{2 \pi k}{m}}) = \Re(e^{i\frac{2 \pi}{m}}\frac{e^{mi\frac{2 \pi}{m}}-1}{e^{i\frac{2 \pi}{m}-1}}) = 0</tex>. | ||
| + | |||
| + | Consider a prime p. Then <tex>f(p) = \sum^p_{k=1} \gcd(k,p)\cos \frac{2 \pi k}{p} = \sum^p_{k=1} \cos \frac{2 \pi k}{p} +(p-1)\cos \frac{2 \pi p}{p} = p-1</tex>. We will show that if <tex>a_1,a_2,...,a_r</tex> are distinct prime factors, then <tex>f(a_1...a_r) = (a_1-1)...(a_r-1)</tex> by induction on <tex>r</tex>. We have already shown this for <tex>r = 1</tex>, so suppose it is true for <tex>s \leq r</tex>. | ||
| + | |||
| + | Let <tex>n = a_1...a_s</tex>, and let <tex>a_{s+1}</tex> be a prime not among the prime factors of <tex>n</tex>. <tex>f(na_{s+1}) = \sum^{na_{s+1}}_{k=1} \gcd(k,na_{s+1})\cos \frac{2 \pi k}{na_{s+1}} = \sum^{na_{s+1}}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{na_{s+1}} + (a_{s+1}-1)\sum^{n}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{n} \\ =\sum^{na_{s+1}}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{na_{s+1}} +(a_{s+1}-1)f(n)</tex>. | ||
| + | |||
| + | So it remains to show that <tex>\sum^{np}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} = 0</tex> whenever <tex>p</tex> is a prime not among the distinct prime factors of <tex>n</tex>. Now, <tex>\sum^{np}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} = | ||
| + | \sum^{n}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} + \sum^{2n}_{k=n+1} \gcd(k,n)\cos \frac{2 \pi k}{np} + ... + \sum^{np}_{k=n(p-1)+1} \gcd(k,n)\cos \frac{2 \pi k}{np} \\ = \sum^{n}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} + \sum^{n}_{k=1} \gcd(k+n,n)\cos \frac{2 \pi (k+n)}{np} + ... + \sum^{n}_{k=1} \gcd(k+(p-1)n,n)\cos \frac{2 \pi (k+(p-1)n)}{np} \\ = \sum^{n}_{k=1} \gcd(k,n)\left(\cos \frac{2 \pi k}{np} +\cos (\frac{2 \pi k}{np}+\frac{2\pi}{p}) + \cos (\frac{2 \pi k}{np}+\frac{2\pi2}{p}) + ... + \cos (\frac{2 \pi k}{np}+\frac{2\pi(p-1)}{p}) \right)</tex>. | ||
| + | |||
| + | But for each <tex>k</tex> between <tex>1</tex> and <tex>n</tex>, we have <tex>\cos \frac{2 \pi k}{np} +\cos (\frac{2 \pi k}{np}+\frac{2\pi}{p}) + \cos (\frac{2 \pi k}{np}+\frac{2\pi2}{p}) + ... + \cos (\frac{2 \pi k}{np}+\frac{2\pi(p-1)}{p}) = \Re(e^{ i\frac{2 \pi k}{np}} +e^{i (\frac{2 \pi k}{np}+\frac{2\pi}{p})} + e^{i (\frac{2 \pi k}{np}+\frac{2\pi2}{p})} + ... + e^{i(\frac{2 \pi k}{np}+\frac{2\pi(p-1)}{p})}) \\ = \Re(e^{ i\frac{2 \pi k}{np}}(1+e^{i \frac{2\pi}{p}} + e^{i\frac{2\pi2}{p}} + ... + e^{i\frac{2\pi(p-1)}{p})}) = 0</tex>. | ||
| + | |||
| + | Thus we conclude that <tex>f(na_{s+1})=(a_{s+1}-1)f(n)=(a_1-1)...(a_s-1)(a_{s+1}-1)</tex>, and we are done. | ||
| + | |||
| + | Now, <tex>2010 = 2 \times 3 \times 5 \times 67</tex> is a product of distinct prime factors, so <tex>\sum^{2010}_{k=1} \gcd(k,2010)\cos \frac{2 \pi k}{2010} = f(2010) = (2-1)(3-1)(5-1)(67-1)=528</tex>. | ||
Revisjonen fra 4. feb. 2011 kl. 02:29
Problem10
Define <tex>f(n) = \sum^n_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{n}</tex>. We will be using that <tex>\sum^m_{k=1}\cos \frac{2 \pi k}{m} = \Re(\sum^m_{k=1}e^{i\frac{2 \pi k}{m}}) = \Re(e^{i\frac{2 \pi}{m}}\frac{e^{mi\frac{2 \pi}{m}}-1}{e^{i\frac{2 \pi}{m}-1}}) = 0</tex>.
Consider a prime p. Then <tex>f(p) = \sum^p_{k=1} \gcd(k,p)\cos \frac{2 \pi k}{p} = \sum^p_{k=1} \cos \frac{2 \pi k}{p} +(p-1)\cos \frac{2 \pi p}{p} = p-1</tex>. We will show that if <tex>a_1,a_2,...,a_r</tex> are distinct prime factors, then <tex>f(a_1...a_r) = (a_1-1)...(a_r-1)</tex> by induction on <tex>r</tex>. We have already shown this for <tex>r = 1</tex>, so suppose it is true for <tex>s \leq r</tex>.
Let <tex>n = a_1...a_s</tex>, and let <tex>a_{s+1}</tex> be a prime not among the prime factors of <tex>n</tex>. <tex>f(na_{s+1}) = \sum^{na_{s+1}}_{k=1} \gcd(k,na_{s+1})\cos \frac{2 \pi k}{na_{s+1}} = \sum^{na_{s+1}}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{na_{s+1}} + (a_{s+1}-1)\sum^{n}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{n} \\ =\sum^{na_{s+1}}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{na_{s+1}} +(a_{s+1}-1)f(n)</tex>.
So it remains to show that <tex>\sum^{np}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} = 0</tex> whenever <tex>p</tex> is a prime not among the distinct prime factors of <tex>n</tex>. Now, <tex>\sum^{np}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} = \sum^{n}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} + \sum^{2n}_{k=n+1} \gcd(k,n)\cos \frac{2 \pi k}{np} + ... + \sum^{np}_{k=n(p-1)+1} \gcd(k,n)\cos \frac{2 \pi k}{np} \\ = \sum^{n}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} + \sum^{n}_{k=1} \gcd(k+n,n)\cos \frac{2 \pi (k+n)}{np} + ... + \sum^{n}_{k=1} \gcd(k+(p-1)n,n)\cos \frac{2 \pi (k+(p-1)n)}{np} \\ = \sum^{n}_{k=1} \gcd(k,n)\left(\cos \frac{2 \pi k}{np} +\cos (\frac{2 \pi k}{np}+\frac{2\pi}{p}) + \cos (\frac{2 \pi k}{np}+\frac{2\pi2}{p}) + ... + \cos (\frac{2 \pi k}{np}+\frac{2\pi(p-1)}{p}) \right)</tex>.
But for each <tex>k</tex> between <tex>1</tex> and <tex>n</tex>, we have <tex>\cos \frac{2 \pi k}{np} +\cos (\frac{2 \pi k}{np}+\frac{2\pi}{p}) + \cos (\frac{2 \pi k}{np}+\frac{2\pi2}{p}) + ... + \cos (\frac{2 \pi k}{np}+\frac{2\pi(p-1)}{p}) = \Re(e^{ i\frac{2 \pi k}{np}} +e^{i (\frac{2 \pi k}{np}+\frac{2\pi}{p})} + e^{i (\frac{2 \pi k}{np}+\frac{2\pi2}{p})} + ... + e^{i(\frac{2 \pi k}{np}+\frac{2\pi(p-1)}{p})}) \\ = \Re(e^{ i\frac{2 \pi k}{np}}(1+e^{i \frac{2\pi}{p}} + e^{i\frac{2\pi2}{p}} + ... + e^{i\frac{2\pi(p-1)}{p})}) = 0</tex>.
Thus we conclude that <tex>f(na_{s+1})=(a_{s+1}-1)f(n)=(a_1-1)...(a_s-1)(a_{s+1}-1)</tex>, and we are done.
Now, <tex>2010 = 2 \times 3 \times 5 \times 67</tex> is a product of distinct prime factors, so <tex>\sum^{2010}_{k=1} \gcd(k,2010)\cos \frac{2 \pi k}{2010} = f(2010) = (2-1)(3-1)(5-1)(67-1)=528</tex>.
