In real world crytography we would use much larger numbers that are harder to factor. Here we're using this property as a demonstration of Euler's theorem in action. Euler's theorem is a statement that exponents under a modulus cycle back to previously seen values after some number of iterations. The length of this cycle can be found if you can factor the modulus.

The above form is specifically a statement of when we can expect the exponent to return 1. We'll explain the above equation and $φ(n)$ in detail, but first let's learn the basic group theory we need to understand this.

Repeated addition under mod n

As a precursor for understanding the cycles that occur under repeated multiplication, we'll first look at a much simpler case, repeated addition. When operating under a modulus you can only produce numbers less than that modulus. This limit on the number of possible outputs means you'll quickly find yourself repeating previous results when performing repeated operations.

As a basic example, consider repeatedly adding 2 to a number under mod 3.

The results of repeated addition of 2 under mod 3 are three integers in a closed cycle that repeat in a specific order, {0,2,1}. What you see above is called the additive group of integers under modulo n.

Here every 3rd value is the same, which makes sense since every 3rd addition of 2 is a multiple of 3. Let's write out what we've just stated as a formula assuming $a$ is some initial value we're starting on.

$a + bn ≡ a \mod n$

Since $bn$ is always 0 mod n, you can guarantee that every nth iteration of adding b will return to the same point in the cycle.

Repeated multiplication under mod n

Now we'll look at a slightly more complicated example. The cycles that occur with repeated multiplication. We'll start by looking at repeated multiplication of 2 under mod 3.

This time we have results of just {1, 2} repeating.

Unlike addition, repeated multiplication by 2 will never produce a factor of 3. This should become clear if you think back to prime factorization; you can't produce a factor of 3 no matter how many times you multiply a number by 2. So we never see 0 in these results. This inability to produce factors of a modulus means we will cycle, at most, every 2 times when multiplying numbers repeatedly under modulo 3. In this particular example you can see that every second exponent of $2x$ would return the same value.

What you see above is known as the multiplicative group of integers modulo $n$.

The above two examples make for a very brief first introduction to Group Theory. We have two different operations, addition and multiplication, that when applied to a set of numbers, those modulo $n$, produce different behaviors. Repeated addition can potentially cycle through all numbers below $n$, while repeated multiplication can never hit factors of $n$. These two operations lead to very different resulting sets. One set considers all numbers below $n$ and the other set only those below $n$ that are co-prime to $n$. Group theory helps to categorize the different behaviors of sets when combined with specific types of operations and is very central in all modern mathematics.

Euler's totient function

The multiplicative group of integers modulo $n$ that we saw above gets more interesting when you consider a composite number such as 15 which has factors of 3 and 5. Repeated multiplication by 2 will never produce a multiple of 3 or 5 and this time there are only 8 numbers, {1,2,4,7,8,11,13,14} less than 15 that are not multiples of 3 or 5.

The count of numbers less than $n$ that are co-prime to $n$ is called the Euler totient and will be very important to understanding how Euler's theorem works. In the above example the Euler totient for 15 is 8 since there are 8 numbers below 15 that share no factors with 15.

We calculated $φ(n)$ above by simply listing out all the numbers co-prime to $n$ and counting them. Since this totient is going to be extremely vital to our understanding let's think about how we'd calculate it.

We'll use 15 as a numeric example.

To calculate $φ(15)$ lets break 15 down into its distinct prime factors, {3,5}. Then with those distinct prime factors we then want to;

• Rule out 1/3rd of the numbers below 15, the factors of 3. This leaves 2/3rds of the numbers remaining
• Rule out 1/5th of the numbers in the 2/3rds that remain. This leaves 4/5ths of those remaining 2/3rds

The formula for what we've just done should be clear. For each distinct prime factor $p$ we are taking the remaining fraction after ruling out $\frac{1}{p}$. The remaining fraction after ruling out $\frac{1}{p}$ is simply $(1-\frac{1}{p})$. So the formula for the probability of a number not being a multiple of $p_1, p_2, p_3...$ is $(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})$...

This gives a ratio of numbers below $n$ that are co-prime to $n$. To get the precise number of elements that are co-prime to $n$ simply multiply that ratio by $n$. This will always return an integer since $p_1, p_2, p_3...$, the denominators of the fractions, are the distinct prime factors of $n$.

In the case of 15 we get $φ(15)=15(\frac{2}{3}*\frac{4}{5})=15(\frac{8}{15})=8$

Here's some Python code to calculate Euler's totient. Note that to enable the calculation of Euler's totient for a very large number we would need to be able to factor that number. You may have heard that certain types of encryption such as RSA can be broken if you can factor large numbers. This is why.

Repeated multiplication of a composite number

Now lets look at the more complicated results of repeated multiplication by 2 under mod 15.

In this case we have results of {1,2,4,8} repeating. So this time we're cycling through a subset of those 8 numbers that make up the Euler totient instead of all of them.

Now you may well ask what happened to the other 4 co-primes to 15? In the case of mod 3 we cycled through all the co-primes, but here the numbers {7,11,13,14}, that are also co-prime to 15, are missing.

A numeric example of Lagrange's theorem¶

The above cycle was generated by $2^x$. If we considered another polynomial, $2^x × y$ we'd create something very similar to the above, but it could start at one of the missing numbers and go from there. By doing this we can demonstrate something called Lagrange's theorem.

First, let's look at the result generated by $2^x × 7$ mod 15 where 7 was a number missing from the set above.

We've now produced 2 distinct sets of the same size all with different elements. One set is $2^x × 1$ mod 15 and the other is $2^x × 7$ mod 15.

Observe the following from what we've just done;

• Any new set created this way, by multiplying the previous set, will be exactly the same size as the previous set since it's simply all the elements of the previous set multiplied by some constant, in this case 7.
• Since we intentionally started from a value not seen in the previous set we'll have an entirely new set of elements since we know the previous set was a closed cycle. You can't jump between these sets by repeated multiplication of 2 and since we explicitly started from a number we know didn't appear in the previous set, we'll have an entirely unique new set.
• We can repeat the above process as many times as needed to have complete coverage of the set $φ(n)$ counts. Here it only took 2 sets to completely cover the set $φ(n)$ counts but it's fine if it takes more.

So functions of the form $a^x × b$ mod $n$ can split the set that $φ(n)$ counts into equal-sized sets, each containing distinct values with complete coverage of the values $φ(n)$ counts. The sizes of these sets must therefore all be factors of $φ(n)$. There could be one of these sets, or there could be many, but the point is that the sizes of these sets that cycle will all cycle on factors of $φ(n)$.

The implication of this is that even though a cycle formed by increasing powers of $a^x$ mod $n$ can cycle earlier than every $φ(n)$ elements we can also guarantee that $a^{φ(n)}$ itself will be some perfect $k$th iteration of the smaller cycle since any smaller cycle is a factor of $φ(n)$ in size. This is the secret to the magical cycling powers above. They actually often cycle earlier, but at the very least we can assume that the totient is some $k$th multiple of a loop of powers which means we can guarantee a known point where the values will cycle.

For those curious, the above is a numeric example of Lagrange's theorem. Essentially, for certain types of groups, like the multiplicative group, we can multiply any resulting set to produce other distinct sets of the same size. Since these groups are all the same size they all divide $φ(n)$.

With the above established for co-primes let's also dive into bases that aren't co-primes to $n$, eg. $3^x$ mod 15. They actually work similarly, and all form sets that themselves are factors of $φ(n)$ in size and thus also cycle on a factor of $φ(n)$ too!

For example 3 has 4 values under 15 that aren't also a multiple 5 (we can never make a multiple of 5 by repeated multiplication of 3 so we don't need to consider 15 itself). These values are {3,6,9,12}. So if you raise a power of $3^x$ mod 15 you'll cycle through some set containing values from those 4 numbers, and that set will be factor of 4 in size by the same logic we described above. This count being a factor of $φ(15)$ isn't a co-incidence. As a numerical example, let's think about how we might calculate the count of factors of 3 under mod 15 that share no other factors of 15.

To calculate the factors of 3 that share no factors with 5 under mod 15 we want to;

• Rule out 2/3rds of the factors. Leaving 1/3rd remaining.
• Rule out 1/5th of the factors remaining. Leaving 4/5th of 1/3rd remaining.

To write this out fully, in this case we get $15(\frac{1}{3}*\frac{4}{5})=15(\frac{4}{15})=4$

The formula for this is almost the same as the formula for calculating $φ(15)$ above. In fact, there's only one part that's different, we multiply by $\frac{1}{3}$ instead of $\frac{2}{3}$. That means it's exactly half the totient, and we know this number will produce an integer since as above in the calculation of the totient we'll multiply by $n$, and since the denominators used are all factors of $n$ we are guaranteed an integer result.

The same will be true for any other factor. You are substituting an instance of $(1-\frac{1}{p})$ in the calculation of $φ(n)$ with $(\frac{1}{p})$ for that particular prime factor. This leads to the counts of specific prime factors of $n$, excluding $n$ itself, as being factors of $φ(n)$.

So both co-primes and prime factors cycle on factors of $φ(n)$ and we can now state a generalized form of Euler's theorem;

That is every time the power is increased by a factor of $φ(n)$ we get the same value under mod $n$.

This holds true for all $a$, $x$ and $k$ with only two specific exceptions. When $a$ is a factor of $n$ and the exponent is 0, then we get a once off value of 1 which won't repeat, even in $φ(n)$ powers time, since a non-zero exponent of a factor of $n$ will return a multiple of that factor in every other case. The other exception is when $a$ contains all factors of $n$ (eg. $n$ is a square), in this case we'll eventually reach 0 mod $n$ once powers of $a$ fully factor $n$.

Euler's theorem and Fermat's little theorem

If we set $x=0$ and $k=1$ in the above, noting the need to be co-prime due to the above-mentioned exceptions, we get the less generalized formula which is commonly known as Euler's theorem.

One last thing before we completely wrap up, if $n$ is a prime $p$ then by the calculation of Euler's totient above $φ(p) = p-1$.

This gives us Fermat's little theorem. $a^{p-1} ≡ 1 \mod p$ for all primes. We usually multiply both sides by $a$ to get the more common form;

And that's it for today! Hopefully, this gives a more intuitive understanding of Euler's theorem. Along the way we introduced some early group theory and also a very high-level overview of RSA cryptography.

For further reading and perhaps a future lesson:

• The Carmichael totient, which is a totient that's often smaller than Euler's totient but has the same properties.
• RSA Cryptography