So we've left the Linear Congruence Theorem stuff a little bit.
We'd like to go to sort of what I would consider
two foundational theorems in the course:
Fermat's Little Theorem and the Chinese Remainder Theorem.
So Fermat's Little Theorem, the proof of this,
that we did in our class, is actually a little bit tricky.
It's difficult to understand. I think it's a really nice proof, it's very clever,
at least the one that we present. There are slightly…
maybe I should say not less clever, but I would say differently clever proofs.
This one's very easy to understand though, which is why I like it.
It's not the easiest to do, I would say the easiest to do is using induction
and the Binomial Theorem if you want to check that out, that'll be I think on Wikipedia actually.
But anyways, Fermat's Little Theorem, let's talk about the theorem.
If p is a prime and p doesn't divide a,
then a to the p minus 1 is congruent to 1 mod p,
or you could reword this again in Z mod p,
a to the p minus 1 is equal to
the equivalence class of a to the p minus 1, is equal to 1 in Z mod p.
Now the proof’s not going to fit on the slide and I don't think there's
much value in doing it on 3 slides again,
but maybe…let me just give you a recap of what the proof entailed.
As long as you have
the major elements, you can actually reconstruct this proof
fairly easily.
There's two key sort of elements here, and the one key is this lemma
and this is really important for this proof.
So I'm going to define the sets S and T.
So T is going to be the numbers from 1 to p minus 1,
and S is going to be the a multiples of the numbers from 1 to p minus 1. So
a, 2a, all the way up to p minus 1 times a.
And here of course we're assuming that a and p are co-prime.
Then the elements of S are unique modulo p, and for all
elements of S, there exists a unique element
t inside T such that S is congruent to t mod p.
What's really happening here? What's really happening here is that
the element a is invertible. So one way to look at this
is you can set up a map from S to T
and you look at S and T as subsets of Z mod p,
and you can set up a map from S to T defined by
sending an element s to the element
s times a inverse, for example,
and that sets up a bijection between S and T.
That’s one way to look at this.
Another way is just to go through it. All the elements of S are non-zero mod p,
and all of them are distinct mod p, so therefore they must be equal to t mod p,
in some rearrangement.
Why is this important? Why is this S and T important? Well if I take a
product of the elements of S and a product of the elements of T,
I know that they must be congruent mod p.
And why is that? Let's think about that.
If you take the product of the elements of S and the product of the elements of T,
well we said before that these two sets are equal mod p, up to a rearrangement.
So if I multiply them together, because of commutativity, it doesn't matter.
What do I mean by, “it doesn't matter”? Well I mean that the product
of these elements must be the same as the product of the elements of T.
Right? Because, again, S and T are the same mod p up to a rearrangement.
So what does this mean? What do the elements of S look like? Well they look like
multiples of a, so let's write down multiples of a.
And what do the elements of T look like? Well they look like the integers
from 1 to p minus 1, so let's write that down.
Now if I'm doing this product here, the product of k times a, well
a is getting multiplied p minus 1 times,
so it's the same as multiplying by a to the p minus 1
times the product from 1 to p minus 1 of k.
And the same thing with a product of j, I didn't touch this side.
Note though that these products, these are actually just
a clever notation for p minus 1 factorial,
and p minus 1 factorial, well we know that p is prime,
and so p minus 1 factorial and p don't share any common factor.
So because p is prime, its only divisors are 1 and p,
so no number less than p, other than 1, divides
p and p minus 1 factorial is the product of all numbers less than p,
so therefore the gcd of p and p minus 1 factorial is 1.
Because of that, I can cancel, they're invertible, that was a previous theorem,
and so we have a to the p minus 1 is congruent to 1 mod p.
And that's it.
A clever, clever statement, so now the proof is one thing. The proof…
is clever but it’s…clever.
So you have to - I mean, do we really expect you to know all these things.
I'll let you decide based on that reaction.
But what's really important about Fermat’s Little Theorem is the ability to apply it,
and we're going to see an application right now.
So find the remainder when 7 to 92 is [divided] by 11.
So again, a good point, at this point, to pause the video and actually
try this problem.
It's not - you should try it.
Now hopefully you're back,
and when you're looking at 7 to the 92,
well okay 11 is a prime,
and we know that 11 doesn't divide 7.
Why is that important? If 11 divided 7, the answer would be really easy.
If 11 divides 7 then 11 clearly divides 7 to the 92
and so we get that this is congruent to 0 mod 11.
So when finding the remainder,
again remember by CISR, Congruent If and Only If Same Remainder,
we can look at this mod 11, reduce it to the least non-negative
residue
and then argue by CISR that since those two numbers have the same remainder
when divided by 11, the original…
since those two numbers are congruent mod 11,
then the original number and the last number must
have the same remainder when divided by 11,
and the least non-negative residue mod 11 is actually just the remainder.
When this number is divided by 11. Okay.
So again what do I know by Fermat’s Little Theorem?
I know that because 11 is co-prime to 7,
7 to the 11 minus 1, which is 10,
so 7 to the 10 is congruent to 1 mod 11.
So what am I going to try to do with 7 to the 92? I'm going to try to get
7 to the 10 to appear.
And the way I like to do this - so there's lots of ways.
You actually start with 7 to the 10, and then take it to the power of 9,
and then multiply by 7 squared, that's one way to do it.
The way I like to start though is because usually when you're solving these problems,
there's multiple - like you have a sum of these numbers
and you're dealing with multiple things, so I like using this method a little bit more.
Personal preference of course.
So here though I'm going to write
7 to the 92 as 7 to the power of 9 times 10 plus 2.
This is actually an equality, but I'll leave it as a congruence.
Flip the symbols around, 7 to the 10 to the power of 9 times 7 squared.
That's 1 to the 9 times 7 squared.
7 squared is 49, 49 mod 11 that's 5
mod 11.
By CISR, the remainder when I divide 5 by 11 is 5,
so therefore the remainder when I divide 7 to 92 by 11 is 5,
since 7 to the 92 is congruent to 5 mod 11.
And that's it.
So a fun little example. These questions are actually fun once you get use of them,
but they do take a little bit of time.
So don't be discouraged if at first you don't see all these patterns and stuff, but
do practice, do take a couple of examples.
Create your own examples, there are lots of computer programs that can compute
this very quickly.
so the chances of you writing a small example and not being able to
verify it on a computer are very small.
This is worth doing for your first attempt.
Corollaries to FLT, so some of these I like to use a lot.
So that's why I've put them all on the board. There actually -
I've put them all on one slide. They're not too hard to prove,
I didn't prove any in this talk, but you can check them out in the notes
online.
So some corollaries: if p is a prime and a is an integer, then a to the p is congruent to a mod p.
So how does this one work? So when
p doesn't divide a, this is just FLT and then multiplied by a,
and when p does divide a, well a is the same as 0 mod p.
So a to the p is congruent to 0 mod p, and so these two numbers must be equal.
If p is a prime number and a is not 0
in Z mod p, so the equivalence class of a is not equal to the equivalence class of 0,
then there exists an element b inside Z mod p
such that a times b is equal to 1.
What element can we take? Well we can actually take b to be a to the p minus 2.
Again so what things does this use? So p minus 2 is at least 0,
because p is a prime number, so this actually makes sense.
And what do we know here? So if I take a times a to the p minus 2,
that's just a to the p minus 1, and that's 1 by FLT.
We know that a is not the same as 0 in Z mod p.
Another corollary: if r is equal to s plus k p, then
a to the r is congruent to a to the s plus k
so no p up here, mod p.
And again, this just uses the first corollary.
Oh I should mention here, this is a typo here that I didn't fix.
So where p is a prime and a is an integer and r, s, and k…
they should be positive
and the reasons why they should be positive,
or at least non-negative, is that
you get some weird situations. So if r was negative, let's say,
then I have a to the r,
r is negative, so this is like saying a to the inverse to some rth power,
but I don't know that a is invertible.
So I need to be a little bit careful here, I apologize for this typo.
But r, s, and k should be natural numbers here not integers.
But again the proof is actually just identical to the corollary above -
well the proof just uses the corollary above, it's not identical
but it uses that corollary. And this corollary, the last corollary,
is basically the same as the third corollary except we allow for the fact that a [can] be invertible.
So prove that if p does not divide a
and r is congruent to s mod p minus 1,
then a to the r is congruent to a to the s mod p.
So here we allow r and s to be negative, which is not a problem
because a is invertible mod p.
So something - that's a slight subtlety, something to think about,
maybe on the bus. Why can't we really do this
over the integers, in general.