MAT 338 Day 31 2011

2417 days ago by kcrisman

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.)

euler_phi(25) 
       
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?

factor(275);euler_phi(275);275*(1-1/5)*(1-1/11) 
       
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.

@interact def _(a=25,b=11): html("$\phi(%s)=%s\\text{ and }\phi(%s)=%s$"%(a,euler_phi(a),b,euler_phi(b))) if gcd(a,b)==1: html("And $\phi(%s\cdot %s)=%s\cdot %s=%s$, their product!"%(a,b,euler_phi(a),euler_phi(b),euler_phi(a*b))) else: html("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))) 
       

Click to the left again to hide and once more to show the dynamic interactive window

275*(1-1/5)*(1-1/11) 
       
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 long-term, 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$?

@interact def _(n=275): html("$%s$ factors as $%s$"%(n,latex(factor(n)))) html("Its divisors are $%s$"%latex(divisors(n))) html("The sum of $\phi$ of the divisors is $%s$"%sum([euler_phi(d) for d in divisors(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?

sigma(12,1);sigma(12,0);sigma(12) 
       
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:

  • A formula, at least for some input types.
  • See if at least a limited form of multiplicativity holds.

You might also want to look at questions like these:

  • Can two different $n$ yield the same $\sigma_k$ (for a given $k$)?  If so, when - or when not?  Can they be consecutive?
  • Is it possible to say anything about when one of these functions yields even results - or ones divisible by three, four, ... ?
  • Clearly the size of these functions somehow is related to the size of $n$ - for instance, it is obvious that $\sigma_0(n)=\tau(n)$ can't possible be bigger than $n$ itself!  So how big can these functions get, relative to $n$?   How small?
  • Can anything be said about congruence values of these functions?  (This is a little harder.)

Homework:

  1. Read the awesome direct proof that $\sigma$ and $\sigma_0$ are multiplicative in Jones and Jones (pages 145-146); as part of this, please show that $\sigma_k$ is also multiplicative.
  2. Jones and Jones comment at the bottom of page 144 that the number of solutions of a (fixed) polynomial congruence modulo $n$ is a multiplicative function.  This is closely related to the question on a previous homework about for which $n$ it is true that $-1$ has a square root.   Write out the details of this comment, and connect it to whether $-1\in Q_n$.
  3. A perfect number is an $n$ such that $\sigma(n)=2n$.  Read Euclid's proof that certain even numbers are perfect and write it down in modern notation.
  4. It turns out the converse of Euclid's statement is also true.  Who proved this?  Why are these numbers called perfect, anyway?  What does this all have to do with GIMPS?
  5. Can you find a number such that $\sigma(n)=3n$?
  6. Do Exercise 8.21 in Jones and Jones.