Author Archives: Brent

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

Computing the Euler totient function, part 3: proving phi is multiplicative

We are trying to show that the Euler totient function , which counts how many numbers from to share no common factors with , is multiplicative, that is, whenever and share no common factors. In my previous post, we looked … Continue reading

Posted in arithmetic, computation, counting | Tagged , , , | 1 Comment

Computing the Euler totient function, part 2: seeing phi is multiplicative

In my last post, I claimed that whenever and are relatively prime. (Recall that counts how many numbers from to share no factors in common with .) Let’s get some intuition for this by looking at some Chinese remainder theorem … Continue reading

Posted in arithmetic, computation, counting | Tagged , , | 2 Comments

Computing the Euler totient function, part 1

Recall that Euler’s totient function counts how many of the integers from to are relatively prime to , that is, share no factors in common with . For example, , since only , , , and share no factors with … Continue reading

Posted in arithmetic, computation, counting | Tagged , , | 1 Comment

Post without words #26

Image | Posted on | Tagged , , | 2 Comments

Chinese Remainder Theorem proof

In my previous post I stated the Chinese Remainder Theorem, which says that if and are relatively prime, then the function is a bijection between the set and the set of pairs (remember that the notation means the set ). … Continue reading

Posted in modular arithmetic, number theory | Tagged , , , | 2 Comments

More words about PWW #25: The Chinese Remainder Theorem

In a previous post I made images like this: And then in the next post I explained how I made the images: starting in the upper left corner of a grid, put consecutive numbers along a diagonal line, wrapping around … Continue reading

Posted in modular arithmetic, number theory, posts without words | Tagged , , , , | 3 Comments

33 is the sum of three cubes

I’m a bit late to the party, but I find this fascinating: we now know (thanks to a discovery of Andrew R. Booker) that the number 33 can be written as the sum of three cubes. This may sound unremarkable, … Continue reading

Posted in number theory | Tagged , ,