Tag Archives: totient

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

Finding the repetend length of a decimal expansion

We’re still trying to find the prefix length and repetend length of the decimal expansion of a fraction , that is, the length of the part before it starts repeating, and the length of the repeating part. In my previous … Continue reading

Posted in computation, group theory, modular arithmetic, number theory, pattern | 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

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

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