Category Archives: arithmetic

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

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

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

The wizard’s rational puzzle (solutions, part 2)

At long last, here is the solution I had in mind for the Wizard’s rational puzzle. Recall that the goal is to figure out the numerator and denominator of a secret rational number, if all we are allowed to do … Continue reading

Posted in arithmetic, challenges, logic, programming, puzzles, solutions | Tagged , , , , , , , , , ,

The wizard’s rational puzzle (solutions, part 1)

About two and a half months ago I posted a challenge involving a sadistic math wizard, metal cubes containing rational numbers, and a room full of strange machines. I’ve been remiss in following up with some solutions. (Go read the … Continue reading

Posted in arithmetic, challenges, logic, programming, puzzles, solutions | Tagged , , , , , , , , | 3 Comments

Quickly recognizing primes less than 1000: memorizing exceptional composites

In my previous post I wrote about a procedure for testing the primality of any number less than : Test for divisibility by all primes up to , and also . (In practice I test for 2 and 5 first, … Continue reading

Posted in arithmetic, computation, primes | Tagged , , , , , , ,