Hello everyone. In this video, we're going to talk about the last problem of
the Fall 2000 exam.
Very, very cute problem and leads into
a very interesting and
difficult - well not difficult concept, but there's some cool stuff here,
and I'll mention that at the end.
Show that for every integer a, we have that a to the power of 561
is congruent to a mod 561,
even though 561 is not prime.
So this is sort of a counter example
to the converse of FLT. So even though
a to the p is congruent to a
for all values of a, it's not true that 561 is…
is prime. So a to the power of 561 is congruent to a mod 561 doesn't imply -
for all integers a, doesn't imply that 561 is prime.
So how do we prove this? Well
again I have a little bit of insight to this problem so I knew what to do when I saw it.
So I'm not going to be able to give you great insight as to how to approach this, but
if you want to show that something is true mod 561,
again that one option that we've talked about a couple of times now
is try to use some sort of Splitting the Modulus type argument
and then recollecting it using
Chinese Remainder Theorem.
So I'm going to use that same sort of trick again here.
So notice that 561 is 3 times 11 times 17,
and the idea now is to compute a to the 561 modulo these three primes
and use the Chinese Remainder Theorem to stitch them together at the end, okay?
So notice that…
so I'm going to break - everything's going to be broken up into two cases,
if the gcd is 1 and the gcd isn't 1.
If the gcd is 1, I can use FLT, and the gcd is not 1 then,
I mean, clearly a to the 561 is congruent to a mod the prime, okay?
So let's do it in the first time, so if the gcd is 1, notice that
a to the 561, well turns out that…
so 3 minus 1 is 2 and
561 is not divisible by 2, but 560 is.
So 560 is 2 times 280, and there's that extra power of a.
a squared is congruent to 1 modulo 3,
that's by the Fermat's Little Theorem,
and 1 to the power of 280 is 1, so it’s congruent to a.
And then again if 3 divides a, then a to the 561 is congruent to 0,
which is congruent to a mod 3, okay?
So let's do the same trick instead of with 3, let's do it with 11.
Then using FLT gives us what? So a to the 561 that's congruent to…
again so 11 minus 1 is 10, 10 doesn't divide 561,
but it does divide 560.
So we can write this as a to the 10 to the power of 560. a to the 10 is congruent to 1 by FLT,
and 1 to the 56 is 1, so that’s congruent to a,
and again if 11 divides a, then a to the 561 is congruent to 0
is congruent to a mod 11. So in all cases,
a the 561 is congruent to a mod 11.
Lastly if the gcd of a and 17 is congruent to - is equal to 1,
then again using FLT gives that a to the 561 will again…
so 17 minus 1 is 16, and 16 doesn't divide 561, but it does divide 560.
16 - so 560 divided by 16 turns out to be 16 times 35.
a to the 16 is 1, 1 to the 35 is 1, that's congruent to a,
and then again if 17 divides a, then a to the 561 is 0
mod 17, which is the same as a.
So in all cases for every single value of a,
we have the following simultaneous congruences:
a to the 561 is congruent to a mod 3, a to the 561 is congruent to a mod 11,
a to the 561 is congruent to a mod 17.
Look at these three equations, these three numbers are co-prime, we know a solution -
so if I instead of writing a to the 561 I - well…
I mean, if you think about this like a Chinese Remainder Theorem type thing,
then you know that I can combine these three statements.
The generalized Chinese Remainder Theorem says that well if a to the
561 is congruent to a mod 3, 11, and 17,
then a to the 561 is congruent to a mod the product.
So let me maybe put this on a new line just to
make it a bit clearer.
This is what the Chinese Remainder says, if x is congruent to a mod
p 1, x is congruent to a mod p 2, and x is congruent to a mod p 3,
then x is congruent to a mod the products,
right, I guess this is actually more like - this is even like a Splitting the Modulus
sort of thing. I can even write down Splitting the Modulus because all the numbers...
are co-prime.
So either way is fine, and by generalized, Splitting the Modulus, I mean either way is fine,
but again since I have these three simultaneous congruences, that's exactly
what the generalized Chinese Remainder Theorem or Splitting the Modulus tells us,
that I can combine them and get that a to the 561 is congruent to a mod
3 times 11 times 17,
and as we said before 3 times 11 times 17 is 561.
Crazy, crazy proof. The main thing that works is that
560 is a very special number.
It happens to be divisible by p minus 1, q minus 1, and r minus 1,
where p, q, and r happen to be the three factors.
So how did I know to do this? Well okay, so again I'm
privy to a little bit of knowledge here. I know that this 561 is something called a
Carmichael number. A fantastic
fun topic, so if you're bored studying,
I would suggest taking the five to ten minutes reading up on it on Wikipedia.
Carmichael numbers, that's the topic.
Pretty cool stuff. These numbers are pretending to be primes, but they're
not even close to be - they’re not even close to prime.
There's a bunch of these, you can see these numbers. I think 561 is the smallest such number,
at least it's the most often used if it's not the smallest,
and it's really, really cool stuff. Again this is a
number theoretic thing, but I think it's neat and…
I don't know, like I said, I think it's worth a five minute read if you have the chance.
So a fun problem for problem number 9. I think it's kind of…
it’s kind of cool, has some soul,
which is weird to say about a math problem, but some problems
are a little trickier and
they have some nice solutions like this.
Alright, so I hope you enjoyed the final exam review,
and good luck on your
final exam or whatever you're studying for. Best of luck.