### Meta

### Categories

- algebra (47)
- arithmetic (86)
- books (35)
- calculus (7)
- challenges (57)
- combinatorics (29)
- complex numbers (6)
- computation (82)
- convergence (9)
- counting (38)
- famous numbers (48)
- fibonacci (18)
- fractals (13)
- games (34)
- geometry (72)
- golden ratio (8)
- group theory (28)
- humor (8)
- induction (8)
- infinity (19)
- iteration (24)
- links (76)
- logic (12)
- meta (43)
- modular arithmetic (30)
- number theory (108)
- open problems (11)
- paradox (1)
- pascal's triangle (8)
- pattern (106)
- people (23)
- pictures (74)
- posts without words (41)
- primes (57)
- probability (9)
- programming (20)
- proof (92)
- puzzles (18)
- recursion (16)
- review (25)
- sequences (28)
- solutions (31)
- teaching (16)
- trig (3)
- Uncategorized (6)
- video (19)

### Archives

- March 2020 (4)
- February 2020 (1)
- January 2020 (7)
- December 2019 (4)
- November 2019 (2)
- October 2019 (5)
- September 2019 (7)
- August 2019 (3)
- July 2019 (5)
- May 2019 (4)
- April 2019 (2)
- March 2019 (3)
- February 2019 (3)
- January 2019 (4)
- November 2018 (3)
- October 2018 (4)
- September 2018 (4)
- August 2018 (6)
- July 2018 (2)
- June 2018 (5)
- May 2018 (3)
- April 2018 (5)
- March 2018 (4)
- February 2018 (3)
- January 2018 (4)
- December 2017 (3)
- November 2017 (3)
- October 2017 (1)
- September 2017 (1)
- July 2017 (4)
- June 2017 (4)
- May 2017 (9)
- April 2017 (7)
- March 2017 (5)
- February 2017 (4)
- January 2017 (3)
- December 2016 (4)
- November 2016 (6)
- October 2016 (6)
- September 2016 (2)
- August 2016 (5)
- July 2016 (2)
- June 2016 (4)
- May 2016 (4)
- April 2016 (2)
- March 2016 (3)
- February 2016 (9)
- January 2016 (8)
- December 2015 (5)
- November 2015 (29)
- August 2015 (3)
- June 2015 (2)
- April 2015 (1)
- May 2014 (1)
- December 2013 (1)
- October 2013 (1)
- July 2013 (1)
- June 2013 (1)
- May 2013 (1)
- April 2013 (3)
- March 2013 (3)
- February 2013 (2)
- January 2013 (5)
- December 2012 (3)
- November 2012 (4)
- October 2012 (5)
- September 2012 (1)
- August 2012 (4)
- July 2012 (1)
- June 2012 (6)
- May 2012 (2)
- April 2012 (3)
- March 2012 (1)
- February 2012 (4)
- January 2012 (5)
- December 2011 (1)
- November 2011 (7)
- October 2011 (4)
- September 2011 (6)
- July 2011 (2)
- June 2011 (4)
- May 2011 (5)
- April 2011 (2)
- March 2011 (4)
- February 2011 (1)
- January 2011 (1)
- December 2010 (1)
- November 2010 (4)
- October 2010 (2)
- September 2010 (1)
- August 2010 (1)
- July 2010 (1)
- June 2010 (2)
- May 2010 (3)
- April 2010 (1)
- February 2010 (6)
- January 2010 (3)
- December 2009 (8)
- November 2009 (7)
- October 2009 (3)
- September 2009 (3)
- August 2009 (1)
- June 2009 (4)
- May 2009 (5)
- April 2009 (4)
- March 2009 (2)
- February 2009 (1)
- January 2009 (7)
- December 2008 (1)
- October 2008 (2)
- September 2008 (7)
- August 2008 (1)
- July 2008 (1)
- June 2008 (1)
- April 2008 (5)
- February 2008 (4)
- January 2008 (4)
- December 2007 (3)
- November 2007 (12)
- October 2007 (2)
- September 2007 (4)
- August 2007 (3)
- July 2007 (1)
- June 2007 (3)
- May 2007 (1)
- April 2007 (4)
- March 2007 (3)
- February 2007 (7)
- January 2007 (1)
- December 2006 (2)
- October 2006 (2)
- September 2006 (6)
- July 2006 (4)
- June 2006 (2)
- May 2006 (6)
- April 2006 (3)
- March 2006 (6)

# Tag Archives: roots

## From primitive roots to Euclid’s orchard

Commenter Snowball pointed out the similarity between Euclid’s Orchard… …and this picture of primitive roots I made a year ago: At first I didn’t see the connection, but Snowball was absolutely right. Once I understood it, I made this little … Continue reading

## The Möbius function proof, part 2 (the subset parity lemma)

Continuing from my previous post, we are in the middle of proving that satisfies the same equation as , that is, and that therefore for all , that is, is the sum of all the th primitive roots of unity. … Continue reading

Posted in arithmetic, combinatorics, complex numbers, primes, proof
Tagged circle, complex, moebius, mu, primitive, proof, roots, sum, unit, unity
3 Comments

## The Möbius function proof, part 1

In my last post, I introduced the Möbius function , which is defined in terms of the prime factorization of : if has any repeated prime factors, that is, if is divisible by a perfect square. Otherwise, if has distinct … Continue reading

## The Möbius function

Time to pull back the curtain a bit! My recent series of posts on complex roots of unity may seem somewhat random and unmotivated so far, but the fact is that I definitely have a destination in mind—we are slowly … Continue reading

## Computing sums of primitive roots

Remember this picture? It, and other pictures like it, express the fact that for a given , if we take the primitive roots for each of the divisors of , together they make up exactly the set of all th … Continue reading

## Sums of primitive roots

In my previous post, we saw that adding up all the complex th roots of unity always yields zero (unless , in which case the sum is ). Intuitively, this is because the roots are symmetrically distributed around the unit … Continue reading

## Sums and symmetry

Let’s continue our exploration of roots of unity. Recall that for any positive integer , there are complex numbers, evenly spaced around the unit circle, whose th power is equal to . These are called the th roots of unity. … Continue reading

## Primitive roots of unity

So we have now seen that there are always different complex th roots of unity, that is, complex numbers whose th power is equal to , equally spaced around the circumference of the unit circle. Consider the first th root … Continue reading

## Complex multiplication and roots of unity

If played around with the question from my previous post, you probably found something like the following: That is, as the powers of we get , , and with all possible sign combinations. Of course, since , if we continue … Continue reading

## Totient sums

I took a bit of a break to travel to Japan for a conference, but I’m back now to continue the series I started with Post Without Words #10, a follow-up post, and Post Without Words #11. Recall that we … Continue reading