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 concept. There's some cool stuff here, and I'll mention that at the end.
Question: Show that for every integer $a$, we have that $a^{561}\equiv a\pmod{561}$ even though $561$ is not prime.
So this is sort of a counter example to the converse of FLT. So $a^{561}\equiv a \pmod{561}$ 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 $\bmod {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=3\cdot 11\cdot 17$, and the idea now is to compute $a^{561}$ modulo these three primes and use the Chinese Remainder Theorem to stitch them together at the end.
Everything's going to be broken up into two cases, if $\gcd=1$ and $\gcd\neq 1$. If $\gcd=1$, I can use FLT, and if $\gcd\neq 1$ then, I mean, clearly $a^{561}\equiv a \bmod$ the prime.
So let's do it for the first one, so if $\gcd(a,3)=1$, so $3-1=2$ and $2\nmid 561$ but $2\mid 560$. So using FLT gives
$$a^{561}\equiv(a^2)^{280}a\equiv a\pmod 3$$Then again if $3\mid a$, then $a^{561}\equiv 0\equiv a\pmod 3$.
So let's do the same trick instead of with $3$, let's do it with $11$. Then using FLT gives us what?
$$a^{561}\equiv(a^{10})^{56}a\equiv a\pmod {11}$$Again so $11-1=10$, $10\nmid 561$, but $1\mid 560$. Again if $11\mid a$, then $a^{561}\equiv 0\equiv a\pmod{11}$. So in all cases, $a^{561}\equiv a\pmod{11}$.
Lastly if $\gcd(a,17)=1$, then again using FLT gives that
$$a^{561}\equiv(a^{16})^{35}a\equiv a\pmod {17}$$So $17-1=16$, and $16\nmid 561$, but $16\mid 560$. Then again if $17\mid a$, then $a^{561}\equiv 0\equiv a\pmod{17}$. So in all cases for every single value of $a$, we have the following simultaneous congruences:
$$\begin{align*} a^{561}&\equiv a\pmod 3\\ a^{561}&\equiv a\pmod {11}\\ a^{561}&\equiv a\pmod {17} \end{align*}$$Look at these three equations, these three numbers are co-prime, so 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^{561}\equiv a \pmod {3,11,17}$, then
$$a^{561}\equiv a \pmod{3\cdot 11\cdot 17}$$This is what the Chinese Remainder says, if $x\equiv a \pmod{p_1},x\equiv a \pmod{p_2}, x\equiv a \pmod{p_3}$, then $x\equiv a \pmod{p_1p_2p_3}$.
I guess this is even like a Splitting the Modulus sort of thing. I can even write down Splitting the Modulus because all those 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^{561}\equiv a\pmod{3\cdot 11\cdot 17}$, and as we said before $3\cdot 11\cdot 17=561$.
Crazy, crazy proof. The main thing that works is that $560$ is a very special number. It happens to be divisible by $p-1$, $q-1$, and $r-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 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, 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 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.