Tag Archives: Euler

Computing the Euler totient function, part 4: totient of prime powers

Posted on July 2, 2019 by Brent

I’ve been on a bit of a hiatus as I’ve been travelling with my family for the past month. So here’s a recap. Our story so far Recall that the Euler totient function, , counts how many numbers from to … Continue reading →

Posted in arithmetic, computation, counting | Tagged , , | Comments Off on Computing the Euler totient function, part 4: totient of prime powers

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

Posted on May 27, 2019 by Brent

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

Posted on May 18, 2019 by Brent

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

Posted on May 9, 2019 by Brent

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

Posted on May 6, 2019 by Brent
Posted in modular arithmetic, number theory, posts without words | Tagged , , | 2 Comments

Euler’s Theorem: proof by modular arithmetic

Posted on November 30, 2017 by Brent

In my last post I explained the first proof of Fermat’s Little Theorem: in short, and hence . Today I want to show how to generalize this to prove Euler’s Totient Theorem, which is itself a generalization of Fermat’s Little … Continue reading →

Posted in number theory, primes, proof | Tagged , , , | Comments Off on Euler’s Theorem: proof by modular arithmetic

Four formats for Fermat: correction!

Posted on November 1, 2017 by Brent

In my previous post I explained three variants on Fermat’s Little Theorem, as well as a fourth, slightly more general variant, which it turns out is often called Euler’s Totient Theorem. Here’s what I said: If and is any integer, … Continue reading →

Posted in number theory, primes | Tagged , , , , , , | 4 Comments

Totient sums

Posted on October 7, 2016 by Brent

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 →

Posted in geometry, pattern, pictures, posts without words, proof | Tagged , , , , , | 4 Comments

Post without words #11

Posted on September 8, 2016 by Brent
Posted in geometry, pattern, pictures, posts without words, proof | Tagged , , , , , | 7 Comments

Hyperbinary conjecture seeking proof for a good time, long walks on the beach

Posted on October 12, 2009 by Brent

Here’s the latest progress on the hyperbinary sequence. We’re trying to figure out the inverse relation of the function : given a particular number , where does it occur in the hyperbinary sequence? That is, what are the values of … Continue reading →

Posted in challenges, pattern, people, proof, sequences | Tagged , , , | 4 Comments