Tag Archives: Euler

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 , , | Leave a comment

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 , , | Leave a comment

Post without words #26

Image | Posted on by | Tagged , , | 2 Comments

Euler’s Theorem: proof by modular arithmetic

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 , , ,

Four formats for Fermat: correction!

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

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 in geometry, pattern, pictures, posts without words, proof | Tagged , , , , , | 7 Comments