Tuesday, July 9, 2013

Fermat's Little Theorem, Euler's Generalization and Artin Representations

I know I haven't been blogging for a while, but I'm happy to give a brief update here of why I haven't along with some fun number theory.

There's a well-known theorem, likely familiar to all the mathematicians who might read this blog, known as Fermat's Little Theorem. This theorem should not be confused with Fermat's Last Theorem which is much harder to prove and of much less general mathematical interest aside from the historical importance.

Fermat's Little Theorem says the following: Suppose you have a prime p and suppose you have a positive integer a that is not divisible by p. Then a^(p-1) leaves a remainder of 1 when divided by p (or as mathematicians like to say, a^(p-1) = 1 (mod p). Here the notation x=y (mod n) means that x and y have the same remainder when we divide by n.  So for example, 3^4=81 which leaves a remainder of 1 when I divide by 5.

Euler generalized this result so that p=n did not need to be prime. But to do that one needs to do a few things. First, one needs to strengthen the condition on a. So instead of n not dividing a, one wants that a and n have greatest common divisor 1. Second, instead of (n-1) in the exponent of a, one needs φ(n), where φ(n) is what is called the Euler phi function. This function counts how many positive integers are less than or equal to and relatively prime to n. For example, φ(6)=2 because the only such integers are 1 and 5. Then we have the theorem that if a and n are relatively prime then a^φ(n) = 1 (1 mod n).

Now, why am I thinking about this result? Well, one can for a fixed a and a given n, ask what the actual lowest power one needs to raise a to get something that is 1 mod n. So for example, for 7, φ(7)=6, but if one looks at 2, one will see that one can take 2^3=7+1, so 2 in this case didn't need as high a power as it might otherwise need. Let's write ord_a(n) to be this minimum power. There's been a lot of work in the last hundred years in trying to understand this function and related behavior.

One natural thing to do is to look at the average of value of phi(n)/ord_a(n) That is, for any x, look at G(x)= Σ  φ(n)/ord_a(n) where the sum is over all n that are relatively prime n and less than or equal to x. So what can we say about this function? Lower bounds were recently proven by Christopher Ambrose,  who showed that for any a, the G(x) grows slightly faster than x^1.7 (here the actual constant is an ugly irrational). There's also an easy upper bound, but until recently no non-trivial upper bound was known. I'm please to say that that is now known. In particular, for any α less than 3, it is now known that G(x)=O(x^2 / (log x)^α). A draft of that paper can be found here. So, now you know part of what I've been working on for a while now and why I haven't had as much time to blog.  The result in question is actually secondary to the main theorem about counting what are called Artin Represenations (or in the restricted case I care about, actually ray class characters), which I hope to discuss in a future blog entry.

8 comments:

Puzzled said...

>First, one needs to strengthen the condition on a. So instead of n|a, >one wants that a and n have greatest common divisor 1.

How is this a strengthening?

Joshua said...

Puzzled, it is called I made a typo. That should be n not dividing a in the first bit. Does that make sense?

Puzzled said...

Sorry, rereading my comment I don't like the tone. I meant to say that I was confused by it. In any case, I think I'm still a bit confused. In Fermat's theorem, we required that n not divide a. In Euler's, the requirement is that (n,a)=1 - do we call this a strengthening since, if n divided a, the gcd would be as large as possible, so gcd=1 is an extreme form of not dividing, so to speak? Not only does it not divide, but also they share nothing at all (dividing would mean, I guess, that they share all of n's prime factors?)

Joshua said...

Puzzled, the thing is that Fermat's theorem only applies to primes. If is prime, then n not dividing a is equivalent to (n,a)=1. But this isn't the same condition in the composite case, since for example, 4 doesn't divide 6 but (4,6)=2. So we need the stronger condition there. Does that make sense?

Puzzled said...

Yes, thanks.

Anonymous said...

I made some experiments (taking a = 7)
it appears that G(x) x^(-2)log^4 x still decreases.

With G(x) x^(-1.5) log^b x it appears to depend on b. decreasing
with b=0 but increasing for b=2.

These results are with modest values x = 100000.

Are there some conjectures about the
asymptotic behavior of G(x)?

(The statement of Euler Theorem has
a typo, p should be n).

Juan

Joshua said...

Juan, there's no conjectured asymptotic. Other work by Ambrose shows that the growth is at least x^(1.7) (actually an ugly constant a little above 1.7).

Hollis said...

This is gorgeous!