For the rest of the semester we will be focusing on functions. Up to this point we have not used many functions specific to integers themselves, or only referred to them obliquely.
Of course, it's easier to say useful things about some functions than others! So we'll start by reminding ourselves of some of the nice properties of one particular function we did study a fair amount, and then spend the rest of today 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 an 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.)
20 20 
Of course, such small values can be calculated by hand.
Just like with the function $r(n)$ from last time (the number of ways to represent a number as a sum of two squares), we can say three things about $\phi$.
First:
We had a formula. Do you remember it?
5^2 * 11 200 200 5^2 * 11 200 200 
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)\; .$$
Second:
Also, $\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)$). We say that $f(n)$ is multiplicative if it has this property. The terminology is kind of bad, because of course it only multiplies for coprime integer inputs, but since relatively primality is such a fundamental concept this seems okay nonetheless. We test this here.
Click to the left again to hide and once more to show the dynamic interactive window 
200 200 
So $\phi$ is multiplicative and $r$ is not, though we haven't determined if some modification of $r$ might be.
The third property we looked at for $r$ was about its longterm, average behavior. We aren't ready to address that for other functions yet, so instead we'll look at a different, but related, property.
Third:
There was one other unusual property that $\phi(n)$ had, if you recall. What was the sum of $\phi(d)$ over the set of divisors $d$ of $n$?
Click to the left again to hide and once more to show the dynamic interactive window 
So all this leads us to define some new functions, and ask some questions about them!
Let $\sigma_k(n)$ be defined as the sum of the $k$th power of the (positive) divisors of $n$, thus: $$\sigma_k(n)=\sum_{d\mid n}d^k\, .$$ This has the very nice property that $\sigma_1$ and $\sigma_0$ encode some special information  what?
28 6 28 28 6 28 
Incidentally, very (very) often one will see $\sigma_0(n)$ written as $\tau(n)$, sometimes also as $d(n)$. Usually $\sigma_1(n)$ is written simply $\sigma(n)$, though Euler apparently used $\int n$ in his writings.
Okay, now let's explore! Try to figure out as much as you can. You can certainly save time by dividing up the initial computations among yourselves, then sharing that information so you have a bigger data set to look at.
Naturally, you might want to search for:
You might also want to look at questions like these:
Homework:
