<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="nb">
	<id>https://matematikk.net/w/index.php?action=history&amp;feed=atom&amp;title=Bruker%3AKarl_Erik%2FProblem10</id>
	<title>Bruker:Karl Erik/Problem10 - Sideversjonshistorikk</title>
	<link rel="self" type="application/atom+xml" href="https://matematikk.net/w/index.php?action=history&amp;feed=atom&amp;title=Bruker%3AKarl_Erik%2FProblem10"/>
	<link rel="alternate" type="text/html" href="https://matematikk.net/w/index.php?title=Bruker:Karl_Erik/Problem10&amp;action=history"/>
	<updated>2026-04-09T04:13:31Z</updated>
	<subtitle>Versjonshistorikk for denne siden på wikien</subtitle>
	<generator>MediaWiki 1.42.3</generator>
	<entry>
		<id>https://matematikk.net/w/index.php?title=Bruker:Karl_Erik/Problem10&amp;diff=3649&amp;oldid=prev</id>
		<title>Jarle: Tømmer siden</title>
		<link rel="alternate" type="text/html" href="https://matematikk.net/w/index.php?title=Bruker:Karl_Erik/Problem10&amp;diff=3649&amp;oldid=prev"/>
		<updated>2011-02-04T18:48:36Z</updated>

		<summary type="html">&lt;p&gt;Tømmer siden&lt;/p&gt;
&lt;table style=&quot;background-color: #fff; color: #202122;&quot; data-mw=&quot;interface&quot;&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;tr class=&quot;diff-title&quot; lang=&quot;nb&quot;&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;← Eldre sideversjon&lt;/td&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;Sideversjonen fra 4. feb. 2011 kl. 18:48&lt;/td&gt;
				&lt;/tr&gt;&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l1&quot;&gt;Linje 1:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Linje 1:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Problem10&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;----&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Define &amp;lt;tex&amp;gt;f(n) = \sum^n_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{n}&amp;lt;/tex&amp;gt;. We will be using that &amp;lt;tex&amp;gt;\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&amp;lt;/tex&amp;gt;.&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;br&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Consider a prime p. Then &amp;lt;tex&amp;gt;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&amp;lt;/tex&amp;gt;. We will show that if &amp;lt;tex&amp;gt;a_1,a_2,...,a_r&amp;lt;/tex&amp;gt; are distinct prime factors, then &amp;lt;tex&amp;gt;f(a_1...a_r) = (a_1-1)...(a_r-1)&amp;lt;/tex&amp;gt; by induction on &amp;lt;tex&amp;gt;r&amp;lt;/tex&amp;gt;. We have already shown this for &amp;lt;tex&amp;gt;r = 1&amp;lt;/tex&amp;gt;, so suppose it is true for &amp;lt;tex&amp;gt;s \leq r&amp;lt;/tex&amp;gt;. &lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Let &amp;lt;tex&amp;gt;n = a_1...a_s&amp;lt;/tex&amp;gt;, and let &amp;lt;tex&amp;gt;a_{s+1}&amp;lt;/tex&amp;gt; be a prime not among the prime factors of &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt;. &amp;lt;tex&amp;gt;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)&amp;lt;/tex&amp;gt;. &lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;So it remains to show that &amp;lt;tex&amp;gt;\sum^{np}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} = 0&amp;lt;/tex&amp;gt; whenever &amp;lt;tex&amp;gt;p&amp;lt;/tex&amp;gt; is a prime not among the distinct prime factors of &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt;. Now, &amp;lt;tex&amp;gt;\sum^{np}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} = &lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;\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)&amp;lt;/tex&amp;gt;.&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;But for each &amp;lt;tex&amp;gt;k&amp;lt;/tex&amp;gt; between &amp;lt;tex&amp;gt;1&amp;lt;/tex&amp;gt; and &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt;, we have &amp;lt;tex&amp;gt;\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&amp;lt;/tex&amp;gt;.&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Thus we conclude that &amp;lt;tex&amp;gt;f(na_{s+1})=(a_{s+1}-1)f(n)=(a_1-1)...(a_s-1)(a_{s+1}-1)&amp;lt;/tex&amp;gt;, and we are done.&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;−&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;del style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Now, &amp;lt;tex&amp;gt;2010 = 2 \times 3 \times 5 \times 67&amp;lt;/tex&amp;gt; is a product of distinct prime factors, so &amp;lt;tex&amp;gt;\sum^{2010}_{k=1} \gcd(k,2010)\cos \frac{2 \pi k}{2010} = f(2010) = (2-1)(3-1)(5-1)(67-1)=528&amp;lt;/tex&amp;gt;.&lt;/del&gt;&lt;/div&gt;&lt;/td&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-added&quot;&gt;&lt;/td&gt;&lt;/tr&gt;

&lt;!-- diff cache key mattewiki_db:diff:1.41:old-3618:rev-3649:php=table --&gt;
&lt;/table&gt;</summary>
		<author><name>Jarle</name></author>
	</entry>
	<entry>
		<id>https://matematikk.net/w/index.php?title=Bruker:Karl_Erik/Problem10&amp;diff=3618&amp;oldid=prev</id>
		<title>Jarle på 4. feb. 2011 kl. 02:29</title>
		<link rel="alternate" type="text/html" href="https://matematikk.net/w/index.php?title=Bruker:Karl_Erik/Problem10&amp;diff=3618&amp;oldid=prev"/>
		<updated>2011-02-04T02:29:11Z</updated>

		<summary type="html">&lt;p&gt;&lt;/p&gt;
&lt;table style=&quot;background-color: #fff; color: #202122;&quot; data-mw=&quot;interface&quot;&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;col class=&quot;diff-marker&quot; /&gt;
				&lt;col class=&quot;diff-content&quot; /&gt;
				&lt;tr class=&quot;diff-title&quot; lang=&quot;nb&quot;&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;← Eldre sideversjon&lt;/td&gt;
				&lt;td colspan=&quot;2&quot; style=&quot;background-color: #fff; color: #202122; text-align: center;&quot;&gt;Sideversjonen fra 4. feb. 2011 kl. 02:29&lt;/td&gt;
				&lt;/tr&gt;&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot; id=&quot;mw-diff-left-l1&quot;&gt;Linje 1:&lt;/td&gt;
&lt;td colspan=&quot;2&quot; class=&quot;diff-lineno&quot;&gt;Linje 1:&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;Problem10&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;Problem10&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;----&lt;/div&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot;&gt;&lt;/td&gt;&lt;td style=&quot;background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;----&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Define &amp;lt;tex&amp;gt;f(n) = \sum^n_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{n}&amp;lt;/tex&amp;gt;. We will be using that &amp;lt;tex&amp;gt;\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&amp;lt;/tex&amp;gt;.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Consider a prime p. Then &amp;lt;tex&amp;gt;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&amp;lt;/tex&amp;gt;. We will show that if &amp;lt;tex&amp;gt;a_1,a_2,...,a_r&amp;lt;/tex&amp;gt; are distinct prime factors, then &amp;lt;tex&amp;gt;f(a_1...a_r) = (a_1-1)...(a_r-1)&amp;lt;/tex&amp;gt; by induction on &amp;lt;tex&amp;gt;r&amp;lt;/tex&amp;gt;. We have already shown this for &amp;lt;tex&amp;gt;r = 1&amp;lt;/tex&amp;gt;, so suppose it is true for &amp;lt;tex&amp;gt;s \leq r&amp;lt;/tex&amp;gt;. &lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Let &amp;lt;tex&amp;gt;n = a_1...a_s&amp;lt;/tex&amp;gt;, and let &amp;lt;tex&amp;gt;a_{s+1}&amp;lt;/tex&amp;gt; be a prime not among the prime factors of &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt;. &amp;lt;tex&amp;gt;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)&amp;lt;/tex&amp;gt;. &lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;So it remains to show that &amp;lt;tex&amp;gt;\sum^{np}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} = 0&amp;lt;/tex&amp;gt; whenever &amp;lt;tex&amp;gt;p&amp;lt;/tex&amp;gt; is a prime not among the distinct prime factors of &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt;. Now, &amp;lt;tex&amp;gt;\sum^{np}_{k=1} \gcd(k,n)\cos \frac{2 \pi k}{np} = &lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;\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)&amp;lt;/tex&amp;gt;.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;But for each &amp;lt;tex&amp;gt;k&amp;lt;/tex&amp;gt; between &amp;lt;tex&amp;gt;1&amp;lt;/tex&amp;gt; and &amp;lt;tex&amp;gt;n&amp;lt;/tex&amp;gt;, we have &amp;lt;tex&amp;gt;\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&amp;lt;/tex&amp;gt;.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Thus we conclude that &amp;lt;tex&amp;gt;f(na_{s+1})=(a_{s+1}-1)f(n)=(a_1-1)...(a_s-1)(a_{s+1}-1)&amp;lt;/tex&amp;gt;, and we are done.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;
&lt;tr&gt;&lt;td colspan=&quot;2&quot; class=&quot;diff-side-deleted&quot;&gt;&lt;/td&gt;&lt;td class=&quot;diff-marker&quot; data-marker=&quot;+&quot;&gt;&lt;/td&gt;&lt;td style=&quot;color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;&quot;&gt;&lt;div&gt;&lt;ins style=&quot;font-weight: bold; text-decoration: none;&quot;&gt;Now, &amp;lt;tex&amp;gt;2010 = 2 \times 3 \times 5 \times 67&amp;lt;/tex&amp;gt; is a product of distinct prime factors, so &amp;lt;tex&amp;gt;\sum^{2010}_{k=1} \gcd(k,2010)\cos \frac{2 \pi k}{2010} = f(2010) = (2-1)(3-1)(5-1)(67-1)=528&amp;lt;/tex&amp;gt;.&lt;/ins&gt;&lt;/div&gt;&lt;/td&gt;&lt;/tr&gt;

&lt;!-- diff cache key mattewiki_db:diff:1.41:old-3610:rev-3618:php=table --&gt;
&lt;/table&gt;</summary>
		<author><name>Jarle</name></author>
	</entry>
	<entry>
		<id>https://matematikk.net/w/index.php?title=Bruker:Karl_Erik/Problem10&amp;diff=3610&amp;oldid=prev</id>
		<title>Karl Erik: Ny side: Problem10 ----</title>
		<link rel="alternate" type="text/html" href="https://matematikk.net/w/index.php?title=Bruker:Karl_Erik/Problem10&amp;diff=3610&amp;oldid=prev"/>
		<updated>2011-02-03T22:18:53Z</updated>

		<summary type="html">&lt;p&gt;Ny side: Problem10 ----&lt;/p&gt;
&lt;p&gt;&lt;b&gt;Ny side&lt;/b&gt;&lt;/p&gt;&lt;div&gt;Problem10&lt;br /&gt;
----&lt;/div&gt;</summary>
		<author><name>Karl Erik</name></author>
	</entry>
</feed>