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

A Kick in the Discovery

, , ,

Newbie at Number Theory (Part 7): Euler’s Totient function

Published by

Valt

on

Ok, so what is this strange sounding function? (We know it must be important since it has Euler’s name attached to it.) 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.

Euler’s Totient Function: Let n be a positive integer. Then, \phi is Euler’s Totient Function and is defined by,

ϕ(n)={m∈ℤ:gcd⁡(n,m)=1and0<m≤n}.\phi(n) =\{m \in \mathbb{Z}\;:\;\gcd{(n,m)} = 1\;and \;0\lt m \leq n\}.

This needs an example, doesn’t it?

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 . Also note when n=1, then \phi(1)=1.

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

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

\phi(p^k) = p^{k-1}(p-1) if p is prime and k is a positive integer,

If \gcd{(n,m)}=1 then, \phi(nm) = \phi(n)\phi(m) .

If n = p_a^{k_a}p_b^{k_b}\cdots p_m^{k_m}, then \phi(n) = n\left(1-\frac{1}{p_a}\right)\left(1-\frac{1}{p_b}\right)\cdots\left(1-\frac{1}{p_m}\right).

Here we go!

The first one:

Proposition: \phi(p) = p-1 if and only if p is prime.

Proof: (Click in the Discovery)

Proof: This is an if and only if statement, so we have to do each direction separately

Forward: If \phi(p) = p-1 then, p is prime.

This can be seen from the facts that (i) there are p-1 integers less than p and (ii) \phi(p) = p-1 . Thus, we deduce that every integer less than p shares no factors with p. Hence, it’s prime.

Backward: If p is prime then, \phi(p) = p-1.

Well, if p is prime, then every number less than it is relatively prime to it! Since there are p-1 integers in the set 1, 2, 3, … , p-1 we have, \phi(p) = p-1 .

\square

Second One:

Proposition: \phi(p^k) = p^{k-1}(p-1) if p is prime and k is a positive integer.

Proof: We are going to count the number of multiples of p less than or equal to p^k. From there, we subtract this off the total number of positive integers less than p^k .

Step 1: How may multiples of p are in the set of integers 1, 2, 3, … p^k?

Well, \{1p, 2p, \cdots, pp, \cdots ,p^2p,\cdots, p^{k-1}p\} are the multiples we want. So there are p^{k-1} of them.

Step 2: How many positive integers are less than or equal to p^k?

There are p^k integers.

Step 3: Subtract step 2 and step 1.

We get: p^k - p^{k-1} = p^{k-1}(1-p) as desired.

\square

*Note we could have done this formally with induction on k.

Third One

Proposition: If \gcd{(n,m)}=1 then, \phi(nm) = \phi(n)\phi(m) .

Vocabulary alert: When an integer function has the property that f(nm) = f(n)f(m) when \gcd{(n,m)}=1 , we call it multiplicative. Hence, Euler’s Totient function is multiplicative.

Proof: (Click in the Discovery)

Proof: Let \gcd{(n,m)}=1 . First, right off the back we know that there are \phi(m) integers less than m and relatively prime to m. Let’s denote these by b_1, b_2, \cdots, b_{\phi(m)}.

Consider, some number of the form m + b in the set of positive integers less than nm,

\{1, 2, 3, \cdots, m, \cdots, nm\}.

Observe that\gcd{(am+b,m)}=\gcd{(b,m)} , (I challenge you to prove this, however, I will put a short proof in this footnote1). So, if \gcd{(b,m)}=1 , then \gcd{(am+b,m)}=1. This motivates breaking up the above set into different subsets using the different b_1, b_2, \cdots, b_{\phi(m)} from earlier.

B_1:=\{m+b_1, 2m+b_1, 3m+b_1, \cdots, (n-1)m+b_1\}

B_2:=\{m+b_2, 2m+b_2, 3m+b_2, \cdots, (n-1)m+b_2\}

\vdots

B_{\phi(m)}:=\{m+b_{\phi(m)}, 2m+b_{\phi(m)}, 3m+b_{\phi(m)}, \cdots, (n-1)m+b_{\phi(m)}\}

And since every b_i is relatively prime to m we deduced that every integer in the sets above is relatively prime to m . TAKEAWAY: \gcd{(am+b_i,m)}=1, for every integer 1\leq a\leq (n-1) and b_i for 1\leq i\leq \phi(m).

We want integers relatively prime to both m and n. But, if we can show that every set B_i, like the ones above, have \phi(n) integers that are relatively prime to n, then we’d be done! Since we’d have \phi(n) integers in each of the \phi(m) sets and as a result we’d have \phi(n)\phi(m) integers relatively prime to both n and m.

To this end, focus on the set B (we’re going to drop the subscripts for now), where \gcd{(b,m)}=1 ,

B=\{m+b, 2m+b, 3m+b, \cdots, (n-1)m+b\}.

We want to find out how many integers in B are relatively prime to n, ie how many integers are such that \gcd{(am+b,n)}=1 .

First, observe that every one of the n-1 integers in B are different (mod n). To see this, consider,

a_1m+b \equiv a_2m+b \pmod{n}.

Where 1\leq a_1\leq a_2 \leq n-1. With some modular arithmetic we deduce,

a_1m \equiv a_2m \pmod{n}.

But recall that we have \gcd{(n,m)}=1 , so we know that we can safely divide by m and get,

a_1 \equiv a_2 \pmod{n}.

Together with the fact that a_1 and a_2 are less than n we deduce a_1 =a_2 we get what we wanted. (This follows from a_1 \equiv a_2 \pmod{n}\implies a_2 - a_1 = nk for some integer k. And since 1\leq a_1\leq a_2 \leq (n-1),it must be that: 0\leq a_2 - a_1 =nk<n. Thus k=0.)

Using that every number in B is different (mod n) and that there are (n-1) of them we deduce that if we reduced all the numbers in B (mod n) we’d end up with the set 1, 2, 3, …, (n-1) in some order. We will now show that there are \phi(n) integers in B that are relatively prime to n.

We know that there are \phi(n) positive integers less than n relatively prime to n. Let t be one of these integers and let a_tm+b \equiv t \pmod{n}. We claim this implies \gcd{(a_tm+b,n)}=1.

To see this, let \gcd{(a_tm+b,n)}=d. Since a_tm+b \equiv t \pmod{n}, we deduce,

a_tm+b -t =ns,

for some integer s. Solving t we see,

t=a_tm+b -ns,

which shows d\mid t since we already know that d\mid (a_tm+b) and d\mid n . But, d\mid t and d\mid n imply d=1 since it was assumed that \gcd{(n,t)}=1.

Therefore, there is \phi(n) integers relatively prime to n for every set like B. And since there are \phi(m) such sets, there are \phi(nm) = \phi(n)\phi(m) positive integers less than, relatively prime to nm.

\square

Fourth One:

Theorem: If n = p_a^{k_a}p_b^{k_b}\cdots p_m^{k_m} where k_i are non-negative integers, then \phi(n) = n\left(1-\frac{1}{p_a}\right)\left(1-\frac{1}{p_b}\right)\cdots\left(1-\frac{1}{p_m}\right).

Remark: This simply says that, given some prime factorization we can compute \phi(n) using the formula above. For example, \phi(20) . We know 20 = 2^2 \cdot 5^1. Thus, by the above formula:

\phi(20) = 20\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right) = 8.

Which you can check!

Proof: I challenge you to finish this one! As a hint, use what we have shown so far. For example,

\phi(n) = \phi(p_a^{k_a})\phi(p_b^{k_b})\cdots \phi(p_m^{k_m}).

By induction and continue from here.

\square

Concluding Remarks

Euler’s totient function is a wonderful and useful tool for much of number theory. We will see how we can use this tool to generalize Farmat’s Little Theorem! It’s so awesome! Until next time!

Footnote:

  1. I 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{(am+b,m)}=\gcd{(b,m)} assuming a,b are integers. We’ll do this by first focusing on d=\gcd{(b,m)} . Since d divides both m and b, we conclude d\mid am and thus, d\mid (am+b). This means that d\mid \gcd{(am+b,m)}. Therefore, d\leq \gcd{(am+b,m)} (why?).
    Turning our attention to D=\gcd{(am+b,m)}, we know D divides both m, am, and am+b, we conclude D\mid ((am+b)-am) or D\mid b. Thus, D\leq d and since d\leq D, it must be d=D. ↩︎

2 responses to “Newbie at Number Theory (Part 7): Euler’s Totient function”

  1. Newbie at Number Theory (Part 9): Euler’s Little Theorem – A Kick in the Discovery Avatar
    Newbie at Number Theory (Part 9): Euler’s Little Theorem – A Kick in the Discovery

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

    Like

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

    […] where is Euler’s totient function. […]

    Like

    Reply

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