NTIC Exploring Euler's Function

Section 9.4 Exploring Euler's Function

One of the neatest things about

ϕ (n),

beyond it being quite useful for things we are familiar with (congruences), is that it is a prototype for the many functions there are in number theory. So we will look at it in a bit more depth.

🔗

Let's get some more conjectures about values of

ϕ (n) .

Finding patterns is fun!

🔗

One pattern we saw is Theorem 9.2.5, that if

gcd (a, n) = 1,

then

a^{ϕ (n)} \equiv 1

(mod

n

). But there are some other places one might look for patterns, now that one has done some number theory. These are questions the Fundamental Theorem of Arithmetic just begs us to ask, regarding a possible formula.

🔗

Question 9.4.1.

One can ask:

Given a prime $p,$ is there a formula for $ϕ (p^{e}) ?$
If $m$ and $n$ are coprime, is there a relation between $ϕ (m n)$ and $ϕ (m)$ and $ϕ (n) ?$

🔗

What happens in the latter case for

n = 15

and

m = 16 ?

Can you do it by hand?

🔗

There are a lot of other interesting questions one can ask about this function which aren't directly related to a formula.

🔗

Question 9.4.2.

For instance, one can ask:

When does $ϕ (n) ∣ n ?$
When (if ever) does $ϕ (m) ∣ ϕ (n) ?$ (See Exercise 9.6.18.)
Given $m,$ for how many integers $n$ it is true that $ϕ (n) = m ?$
Are there infinitely many $n$ for which $ϕ (n)$ ends in zero? (See Exercise 9.6.17.)

🔗

One can also ask questions about new, related functions. For instance, let

f (n) = ϕ (n) / n .

Can you find a formula? Where is this function equal to certain values, such as

f (n) = 1 / 2 ?

(See Exercise Group 9.6.14–16.)

🔗

Quite surprisingly, there is an additive result as well – try adding up

\sum_{d ∣ n} ϕ (d)

🔗

for small values of

n

to seek a pattern! (Try it interactively below.)

xxxxxxxxxx
 
@interact
def _(n=range_slider(2,150,1,(2,20))):
    top = n[1]
    bottom = n[0]
    cols = ((top-bottom)//10)+1
    T = [cols*['$n$',r'$\phi(n)$']]
    list = [[i,euler_phi(i)] for i in range(n[0],n[1])]
    list.extend((10-(len(list)%10))*['',''])
    for k in range(10):
        t = [item for j in range(cols) for item in list[k+10*j] ]
        T.append(t)
    pretty_print(html(table(T,header_row = True, frame = True)))

🔗

Remark 9.4.3.

Before moving on to some proofs in the next section, we highly encourage all readers to explore many questions – perhaps using the interact above. It's simply not the same to just prove, and even less so to read a someone else's proof. To really understand these (or other) things in mathematics, one must get a feel for them “by hand”.