Category Archives: proof

Fermat’s Little Theorem: proof by modular arithmetic

In a previous post I explained four (mostly) equivalent statements of Fermat’s Little Theorem (which I will abbreviate “FlT”—not “FLT” since that usually refers to Fermat’s Last Theorem, whose proof I am definitely not qualified to write about!). Today I … Continue reading

Posted in number theory, primes, proof | Tagged , , | 7 Comments

Four formats for Fermat

In my previous post I mentioned Fermat’s Little Theorem, a beautiful, fundamental result in number theory that underlies lots of things like public-key cryptography and primality testing. (It’s called “little” to distinguish it from his (in)famous Last Theorem.) There are … Continue reading

Posted in number theory, primes, proof | Tagged , , | 1 Comment

Now on mathstodon.xyz

Christian Lawson-Perfect and Colin Wright have set up an instance of Mastodon—a decentralized, open-source Twitter clone—as a place for mathy folks to be social. It’s appropriately named mathstodon.xyz, and because it’s open-source they were able to easily hack in support. … Continue reading

Posted in meta, proof | Tagged , , , , , , | 3 Comments

Another greedy coins game update

Another update on the analysis of the greedy coins game (previous posts here, here, and here). I will make another post very soon explaining how to compute optimal play. In my previous post I reported that Thibault Vroonhove had conjectured … Continue reading

Posted in games, proof | Tagged , , , , , ,

Greedy coins game update

I plan to write a longer post soon, but for the moment I just wanted to provide a quick update about the greedy coins game (previous posts here and here). It turns out that the game is a lot more … Continue reading

Posted in games, proof | Tagged , , , , , , | 18 Comments

Möbius inversion

In my last post we saw that , that is, the Möbius function is the inverse of with respect to Dirichlet convolution. This directly leads to an interesting principle called Möbius inversion. Möbius inversion. Suppose is defined for as the … Continue reading

Posted in combinatorics, proof | Tagged , , , , | 3 Comments

Dirichlet convolution and the Möbius function

Recall from last time that the Dirichlet convolution of two functions and is written and defined by: where the sum is taken over all possible factorizations of into a product of positive integers. Last time we saw that is commutative … Continue reading

Posted in combinatorics, proof | Tagged , , , | 1 Comment