Example18.1.1
We can use Sage to calculate.
Section18.1Three Questions for Euler phi¶ permalink
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 a fair amount. In the next chapter, we'll start exploring some 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\).
Subsection18.1.1Formulas
Of course, such small values can be calculated by hand. But what about more general ones? Surely we don't want to have to check every number up to \(n\) just to compute this.
And indeed, in Exercise 9.6.9 you should have gotten a formula. Do you remember it? The following Sage cell is a hint.
Fact18.1.2
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*}
If you are in a classroom setting, you may want to discuss whether it seems likely that arbitrary arithmetic functions have formulas.
Subsection18.1.2Relations
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)\). This is a general property an arithmetic function can have.
Definition18.1.3
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 here.
So \(\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.
Subsection18.1.3Summation (and limits)¶ permalink
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.
Example18.1.4
For instance, let's look at the plot of \(\phi\).
This doesn't look like it's “going” anywhere.
That said, we could look at the highest or lowest points, at least. Certainly prime numbers \(p\) will always have the formula \(\phi(p) = p-1\), 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)\), namely Fact 9.5.4. To recall, what was the sum of \(\phi(d)\) over the set of divisors \(d\) of \(n\)?
Ah yes, it was just that \(\sum_{d\mid n} \phi(d)=n\). 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?