Section18.2Three questions, again
Of course, it's easier to say useful things about some functions than others! So now 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 \[\{k\mid 0<k\leq n,\; gcd(k,n)= 1\}\] of residues modulo \(n\) which are coprime to \(n\).
This function is another example of an arithmetic function – a function with the natural numbers as its domain, usually going to integer, real, or complex values. (We pronounce it with the stress on the third syllable in number theory.)
Of course, such small values can be calculated by hand.
Subsection18.2.1Formulas
We had a formula. Do you remember it?
If \(n\) is the product of prime powers \[n=\prod_{i=1}^k p_i^{e_i}\; ,\] then the formula was \[\phi(n)=n\prod_{i=1}^k \left(1-\frac{1}{p_i}\right)\; .\]
If you are in a classroom setting, you may want to discuss whether it seems likely that arbitrary arithmetic functions have formulas.
Subsection18.2.2Relations
As mentioned above, \(\phi\) has the rather interesting property that if \(m,n\) are coprime then \(\phi(m)\phi(n)=\phi(mn)\) (which it turned out was not quite true for \(r(n)\)). This is a general property.
The terminology is kind of bad, because of course it 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 and \(r\) is not, though we haven't determined if some modification of \(r\) might be.
Again, you may wish to discuss whether it seems likely that arithmetic functions might have some property along these lines.
Subsection18.2.3Summation
The third property we looked at for \(r\) was about its long-term, average behavior. We aren't ready to address that for other functions yet.
Still, there was and interesting property that \(\phi(n)\) had related to this. What was the sum of \(\phi(d)\) over the set of divisors \(d\) of \(n\)?
As a final discussion point, what kind of behavior do you think could happen when summation of arithmetic functions is considered?