NTIC Three Questions for Euler phi

Section 18.1 Three Questions for Euler phi

It's easier to say useful things about some functions than others! To begin, let's go back and remind ourselves of some of the nice properties of one particular function we did study in some detail. In the next chapter, we'll start exploring some functions that we have not yet encountered.

🔗

That function is, naturally, the Euler

$\phi$ function. Recall that

$\phi(n)$ gives the size of the set

$\begin{equation*} \{k\mid 0<k\leq n,\; \gcd(k,n)= 1\} \end{equation*}$

🔗

of residues modulo

$n$ which are coprime to

$n\text{.}$ Also don't forget we can use Sage to calculate it.

xxxxxxxxxx
 
euler_phi(25)

🔗

Subsection 18.1.1 Formulas

🔗

Of course, such small values can be calculated by hand. But what about larger ones? Surely we don't want to have to check every number up to

$n$ just to compute

$\phi(n)\text{.}$

🔗

And indeed, in Exercise 9.6.11 you should have gotten a formula. Do you remember it? The following Sage cell is a hint.

xxxxxxxxxx
 
print(factor(275))
print(euler_phi(275))
print(275*(1-1/5)*(1-1/11))

🔗

Fact 18.1.1.

If $n$ is the product of prime powers $n=\prod_{i=1}^k p_i^{e_i}$ then we have the formula

$\begin{equation*} \phi(n)=n\prod_{i=1}^k \left(1-\frac{1}{p_i}\right) \end{equation*}$

🔗

Proof.

Do Exercise 9.6.11!

🔗

If you are in a classroom setting, you may want to discuss whether it seems likely that arbitrary arithmetic functions have formulas.

🔗

Subsection 18.1.2 Relations

🔗

One piece of getting a formula for

$\phi$ is the rather interesting property

$\phi$ has (Fact 9.5.2) that if

$m,n$ are coprime then

$\phi(m)\phi(n)=\phi(mn)\text{.}$ This is an important general property an arithmetic function may have.

🔗

Definition 18.1.2.

We say that $f(n)$ is multiplicative if

$\begin{equation*} f(m)f(n)=f(mn)\text{ when }m,n\text{ are coprime.} \end{equation*}$

🔗

The terminology is kind of bad, because of course the function only ‘multiplies’ for coprime integer inputs, but since relative primality is such a fundamental concept this seems okay nonetheless. We can test this property in the following Sage cell.

xxxxxxxxxx
 
@interact
def _(a=25,b=11):
    pretty_print(html(r"$\phi(%s)=%s\text{ and }\phi(%s)=%s$"%(a, euler_phi(a), b, euler_phi(b))))
    if gcd(a,b)==1:
        pretty_print(html(r"And $\phi(%s\cdot %s)=%s\cdot %s=%s$, their product!"%(a, b, euler_phi(a), euler_phi(b), euler_phi(a*b))))
    else:
        pretty_print(html(r"But $%s$ and $%s$ aren't coprime, so $\phi(%s\cdot %s)=%s\neq %s\cdot %s$"%(a, b, a, b, euler_phi(a*b), euler_phi(a), euler_phi(b))))

🔗

$\phi$ is multiplicative. Do you think this is an unusual property to have?

🔗

Again, in a class setting you may wish to discuss whether it seems likely that arithmetic functions might have some property along these lines.

🔗

Subsection 18.1.3 Summation (and limits)

🔗

One thing that might be useful to look at in a function is its behavior in the long term. In calculus, we certainly talk a lot about things like asymptotes, even asymptotes other than horizontal and vertical ones. Unfortunately, arithmetic functions don't often look that great in this way.

🔗

For instance, let's look at the plot of

$\phi\text{.}$

Figure 18.1.3. The Euler phi function from 1 to 100 (`plot(euler_phi,1,100)`)

🔗

This doesn't look like it's “going” anywhere.

🔗

That said, there is some regularity; we could look at the highest or lowest points, at least. Certainly prime numbers

$p$ will always have the formula

$\phi(p) = p-1\text{,}$ and that is a nice graph; the lower limit seems reasonably regular as well. Try to think about how one might encapsulate such observations in terms of limits.

🔗

One strategy that is sometimes used to “smooth” such behavior in places like analyzing stock prices is trying to calculate “averages” – that is, sum it up and divide. We are not ready for this with

$\phi$ (see Section 20.5).

🔗

However, there was a different interesting property about summation of

$\phi(n)\text{,}$ namely Fact 9.5.4. To recall, what was the sum of

$\phi(d)$ over the set of divisors

$d$ of

$n\text{?}$

xxxxxxxxxx
 
@interact
def _(n=275):
    pretty_print(html("$%s$ factors as $%s$"%(n,latex(factor(n)))))
    pretty_print(html("Its divisors are $%s$"%latex(divisors(n))))
    pretty_print(html(r"The sum of $\phi$ of the divisors is $%s$"%sum([euler_phi(d) for d in divisors(n)])))

🔗

Ah yes, it was just that

$\sum_{d\mid n} \phi(d)=n\text{.}$ Even if we can't say something about limiting behavior yet, this kind of summation must be getting us closer!

🔗

As a final classroom discussion point, what kind of behavior do you think could happen when summation of arithmetic functions is considered? What about limits? Could you get anything you can get in calculus, or should some things not be possible?