What Comes Next: 1, 2, 4, 8, 16, … hint it’s not 32

A Kick in the Discovery

, , ,

Newbie at Number Theory (Part 9): Euler’s Little Theorem

Published by

Valt

on

As you might have guessed, we’re going learn about Euler’s generalization of Fermat’s Little Theorem, that I’ve dubbed Euler’s Little Theorem. Note this is only what I call the theorem, unfortunately no one else seems to call it this! But, maybe if you start to refer to it as Euler’s Little Theorem then it’ll catch on! Any who, before we get to Euler’s Little Theorem, we must recall Euler’s Totient function from last time.

Euler’s Totient function

This is a review of Newbie at Number Theory (Part 7): Euler’s Totient function.

Ok, so what is this strange sounding function? It’s simply a function that, when given an integer n, spits out how many positive integers less than n are relatively prime to n.

\phi(n) =|\{m\in \mathbb{Z}\;:\;\gcd{(n,m)} = 1\;\mathrm{and}\;0<m\leq n\}|

This needs an example.

Let’s let n = 12. We want to know how many integers between 1 and 12 are relatively prime to 12.

1,\;2,\;3,\;4,\;5,\;6,\;7,\;8,\;9,\;10,\;11,\;12

We’ll 2, 4, 6, 8, 10 12, all share 2 as a factor with 12. So let’s get rid of those.

1,\;3,\;5,\;7,\;9,\;11

And 3 and 9 share 3 as a factor with 12. This leaves,

1,\;5,\;7,\;11

Thus, \phi(12) = 4. Likewise, you can check that \phi(15)= 8 and \phi(19)=18 .

Euler’s totient function has many wonderful and beautiful properties. Here are a few that we proved here:

\phi(p) = p-1 if p is prime,

\phi(nm) = \phi(n)\phi(m) if \gcd{(n,m)}=1 ,

\phi(n) = n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_k}\right) if p_i \mid n for all 1\leq i\leq k.

Connection to Fermat’s Little Theorem

Recall Fermat’s Little Theorem,

Fermat’s Little Theorem (Standard): Let p be prime and let m \not\equiv 0 \pmod{p}, then

m^{p-1} \equiv 1 \pmod{p}.

Let’s rewrite Fermat’s Little theorem using Euler’s totient function. Since p is prime \phi(p) = p-1 and hence we could have stated it in the following way:

Fermat’s Little Theorem (Using Euler’s Totient): Let p be prime and let m \not\equiv 0 \pmod{p}, then

m^{\phi(p)} \equiv 1 \pmod{p}.

This might hint at what Euler discovered. But I want to give you a chance to discover it for yourself. So, choose some integers n and m and see if you can find a connection between n,\;m , and \phi(n) that’s similar to Fermat’s Little Theorem. But don’t assume that either n or m are prime.

Keep thinking…

You got it…

Give it one more minute…

Euler found that for all n and m where \gcd{(n,m)} =1, then

m^{\phi(n)} \equiv 1 \pmod{n}.

For example, let n=12 and m=5 , we have,

5^{\phi(12)}=5^4 = 625 \equiv 1 \pmod{12}.

Since both \gcd{(12,5)} =1, and 624 = 12 \cdot 52. How amazing! Does this work for every relatively prime integers????? Yes, yes it does.

Let’s see why!

Euler’s Little Theorem

Euler’s Little Theorem: Let n and m be a positive integers such that \gcd{(n,m)} =1, then

m^{\phi(n)} \equiv 1 \pmod{n}.

Proof:

Let n and m be a positive integers such that \gcd{(n,m)} =1.

How might we go about proving this statement? Well, since we are considering m such that \gcd{(n,m)} =1, let’s consider a set of positive integers relatively prime to n and are less than n. We’ll denote this set by G,

G =\{a\in \mathbb{Z}\;:\;\gcd{(n,a)} = 1\;\mathrm{and}\;0<a\leq n\}.

From the definition of \phi(n), we know that G has \phi(n) elements. So we can instead write G as,

G =\{a_1 ,a_2, a_3, \cdots ,a_{\phi(n)} \}.

Observe that since \gcd{(n,m)} =1 we know that m is in one of the a_i in G.

In a spur of inspiration, let’s take the product of all the elements in G with m. Denote this set by mG,

mG = \{ma_1 ,ma_2, ma_3, \cdots ,ma_{\phi(n)} \}.

We claim that every ma_i in mG is congruent (mod n) to an a_j in G. Likewise, that every a_s in G is congruent (mod n) to a ma_t in m. Ie,

(1) For any ma_i in the set mG there is an a_j in the set G such that ma_i\equiv a_j\pmod{n}.

(2) And for any a_s in the set G there is an ma_t in the set mG such that a_s\equiv ma_t\pmod{n}.

We will do this in four steps. First, we’ll show that \gcd{(ma_i,n)} = 1. Next, we will show that any integer congruent to ma_i \pmod{n} will also be relatively prime to n. This step establishes that ma_i \pmod{n} is congruent to some a_j in G. From there, we will show that no two elements in mG are congruent to one another (mod n). We deduce that every element in mG is unique modulo n. Lastly, in order to conclude that there must be a one-to-one correspondence using modular arithmetic (mod n) between the elements of G and mG we will recall that G and mG have the same number of elements as well as step 3’s result.

Step 1: \gcd{(ma_i,n)} = 1.

Let \gcd{(ma_i,n)} = d so that d\mid ma_i and d\mid n. Now consider some prime divisor p of d. By Euler’s Lemma (see here), p\mid ma_i implies that p\mid a_i and/or p\mid m. In either case we have a contradiction since d\mid n implies p\mid n and thus either \gcd{(a_i,n)}\geq p and/or \gcd{(m,n)}\geq p contradicting that \gcd{(a_i,n)} = 1 and \gcd{(m,n)} = 1. Conclusion: \gcd{(ma_i,n)} = 1.

Step 2: \gcd{(ma_i + nk,n)} = 1.

You will show that any integer that is congruent to ma_i\pmod{n} will also be relatively prime to n. But let me get you started. Observe that any integer congruent to will be of the form ma_i+nk for some integer k. I challenge you to prove the following statement:

If \gcd{(c+nk,n)} = d, then \gcd{(c+nk,n)} = d for all integers k.

I put a proof in the following footnote if you want to check how you did!1

By letting c=ma_i , d=1, and 0<ma_i + nk \leq n, what you just proved implies ma_i \equiv a_j\pmod{n} for some element a_j in G. But, are we guaranteed to find an integer that is congruent to ma_i\pmod{n} in the range 0<ma_i + nk \leq n? Yes, by the division algorithm. Can you work out why?

Step 3: ma_i\not\equiv ma_j\pmod{n} for all ma_i and ma_j in mG where i\neq j.

We’re almost done! We now show that every element in mG is distinct (mod n). Equivalently, if ma_i\equiv ma_j\pmod{n}, then a_i=a_j. Begin by letting 0< a_j\leq a_i \leq n. Rearranging the congruence ma_i\equiv ma_j\pmod{n} we deduce,

m(a_i-a_j) \equiv 0\pmod{n}.

And since \gcd{(m,n)}=1, we can safely divide by m to get a_i-a_j \equiv 0\pmod{n} or,

a_i-a_j = nt

for some integer t. Recall 0< a_j\leq a_i \leq n and hence their difference is bounded in a similar way 0\leq a_i -a_j \leq n-1 so that

0\leq a_i-a_j = nt < n,

implying t=0 because t is an integer. Altogether a_i=a_j.

Step 4: One-to-one Correspondence

Recall that G and mG have the same number of elements and that all of their elements are unique up to congruence (mod n). More than this, by Step 2, by using congruence (mod n) we have a one-to-one correspondence between the two sets. Can you see why?

QUICK RECAP: In the proof we showed that every element in mG is one of the elements in G up to congruence \pmod{n} and every element in G is one of the elements in mG up to congruence \pmod{n}.

Since we know that up to congruence \pmod{n} the two sets are the same, it must be that the following two products are also congruent \pmod{n},

a_1 \cdot a_2\cdot a_3 \cdots a_{\phi(n)} \equiv ma_1\cdot ma_2\cdot ma_3 \cdots ma_{\phi(n)}\pmod{n} .

Better yet,

a_1 \cdot a_2\cdot a_3 \cdots a_{\phi(n)} \equiv m^{\phi(n)}(a_1\cdot a_2\cdot a_3 \cdots a_{\phi(n)})\pmod{n} .

We now use that all of the a_is are relatively prime to n and divide by a_1 \cdot a_2\cdot a_3 \cdots a_{\phi(n)} . This gives our final result,

m^{\phi(n)} \equiv 1 \pmod{n}.

\square

An example

Let’s see what we can use Euler’s Little theorem for.

Consider the following puzzle. What are the last two digits (the ones and tens place value) of 123^{81}?

Give this a go! As a hint, don’t multiply this out and you’ll need Euler’s Little theorem!

Solution: Consider that if you only wanted to know the ones digit of some integer n, you only need to compute n\pmod{10}. Likewise, to find the ones digit and the tens digit of n you only need to n\pmod{100}. This is where Euler’s Little theorem comes into play.

To use the theorem, we must first find \phi(100). We make use of our results from Newbie at Number Theory (Part 7): Euler’s Totient function as well as the factorization n=100=2^2 \cdot 5^2,

\phi(100) = 100\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right) = 40.

Employing some exponent rules we conclude that the last two digits of 123^{81} are:

123^{81} = 123^{40+40+1} \\ \text{ }\;\;\;\;\;\;\;= 123^{40}\cdot 123^{40} \cdot123^{1}\\ \text{ }\;\;\;\;\;\;\; \equiv 1\cdot 1\cdot123 \\ \text{ }\;\;\;\;\;\;\;\equiv 23 \pmod{100}.

How much easier was this compared to having to multiply 123 by 123 eighty-one times!

Concluding Remarks

Euler’s Little theorem is a beautiful generalization of Fermat’s Little theorem. This might be enough for you, the reader, to be interested in the result. However, for those with a more pragmatic interest in mathematics, you’ll be happy to know that modern cryptography utilizes Euler’s Little theorem! How wonderfully surprising! Check out this article about RSA encryption to learn more, RSA Encryption | Brilliant Math & Science Wiki.

As always, leave any questions you have in the comments! I hope you had a kick in the discovery today!

Footnote:

  1. hope you gave it a go! Even if you couldn’t prove it it’s great that you tried!
    So our goal is to show: \gcd{(c+nk,n)}=\gcd{(c,n)}. We’ll do this by first focusing on d=\gcd{(c,n)} . Since d divides both n and c, we conclude d\mid nk and thus, d\mid (c+nk). This means that d\mid \gcd{(c+nk,n)}. Therefore, d\leq \gcd{(c+nk,n)} and thus d\leq D. (why?)
    Turning our attention to D=\gcd{(c+nk,n)}, we know D divides both n, nk, and c+nk, we conclude D\mid ((c+nk)-nk) or D\mid c. Therefore, D\mid \gcd{(c,n)} or D\leq d and since d\leq D, it must be d=D. ↩︎

One response to “Newbie at Number Theory (Part 9): Euler’s Little Theorem”

  1. Euler’s Little Theorem (Bonus Proof) – A Kick in the Discovery Avatar
    Euler’s Little Theorem (Bonus Proof) – A Kick in the Discovery

    […] those who followed the Newbie as Number Theory series, you would have already seen both Fermat’s Little Theorem and what I dubbed Euler’s Little Theorem. In the proof for Euler’s little theorem, we […]

    Like

    Reply

Leave a reply to Euler’s Little Theorem (Bonus Proof) – A Kick in the Discovery Cancel reply