1 00:00:00,366 --> 00:00:04,133 Hello everyone. In this video, we're 
going to talk about the last problem of 2 00:00:04,133 --> 00:00:06,200 the Fall 2000 exam. 3 00:00:06,200 --> 00:00:08,666 Very, very cute problem and leads into 4 00:00:08,666 --> 00:00:12,000 a very interesting and 5 00:00:12,000 --> 00:00:15,500 difficult - well not difficult concept, 
but there's some cool stuff here, 6 00:00:15,500 --> 00:00:18,000 and I'll mention that at the end. 7 00:00:18,000 --> 00:00:21,000 Show that for every integer a, we 
have that a to the power of 561 8 00:00:21,000 --> 00:00:22,900 is congruent to a mod 561, 9 00:00:22,900 --> 00:00:26,400 even though 561 is not prime. 10 00:00:26,400 --> 00:00:29,700 So this is sort of a counter example 11 00:00:29,700 --> 00:00:33,633 to the converse of FLT. So even though 12 00:00:33,633 --> 00:00:35,733 a to the p is congruent to a 13 00:00:35,733 --> 00:00:40,366 for all values of a, it's not true that 561 is… 14 00:00:40,366 --> 00:00:42,233 15 00:00:42,233 --> 00:00:47,066 is prime. So a to the power of 561 is 
congruent to a mod 561 doesn't imply - 16 00:00:47,066 --> 00:00:50,200 for all integers a, doesn't 
imply that 561 is prime. 17 00:00:50,200 --> 00:00:51,566 18 00:00:51,566 --> 00:00:53,633 So how do we prove this? Well 19 00:00:53,633 --> 00:00:55,000 20 00:00:55,000 --> 00:00:58,700 again I have a little bit of insight to this 
problem so I knew what to do when I saw it. 21 00:00:58,700 --> 00:01:02,233 So I'm not going to be able to give you great 
insight as to how to approach this, but 22 00:01:02,233 --> 00:01:05,633 if you want to show that 
something is true mod 561, 23 00:01:05,633 --> 00:01:08,700 again that one option that we've 
talked about a couple of times now 24 00:01:08,700 --> 00:01:11,933 is try to use some sort of Splitting 
the Modulus type argument 25 00:01:11,933 --> 00:01:15,266 and then recollecting it using 26 00:01:15,266 --> 00:01:16,866 Chinese Remainder Theorem. 27 00:01:16,866 --> 00:01:18,866 So I'm going to use that 
same sort of trick again here. 28 00:01:18,866 --> 00:01:22,266 So notice that 561 is 
3 times 11 times 17, 29 00:01:22,266 --> 00:01:26,366 and the idea now is to compute a to the 561 modulo these three primes 30 00:01:26,366 --> 00:01:30,733 and use the Chinese Remainder Theorem 
to stitch them together at the end, okay? 31 00:01:30,733 --> 00:01:32,400 So notice that… 32 00:01:32,400 --> 00:01:34,800 so I'm going to break - everything's 
going to be broken up into two cases, 33 00:01:34,800 --> 00:01:37,000 if the gcd is 1 and the gcd isn't 1. 34 00:01:37,000 --> 00:01:41,000 If the gcd is 1, I can use FLT, 
and the gcd is not 1 then, 35 00:01:41,000 --> 00:01:45,300 I mean, clearly a to the 561 is 
congruent to a mod the prime, okay? 36 00:01:45,300 --> 00:01:46,400 37 00:01:46,400 --> 00:01:49,066 So let's do it in the first time, 
so if the gcd is 1, notice that 38 00:01:49,066 --> 00:01:52,066 a to the 561, well turns out that… 39 00:01:52,066 --> 00:01:54,166 40 00:01:54,166 --> 00:01:57,066 so 3 minus 1 is 2 and 41 00:01:57,066 --> 00:02:00,566 561 is not divisible by 2, but 560 is. 42 00:02:00,566 --> 00:02:04,866 So 560 is 2 times 280, and 
there's that extra power of a. 43 00:02:04,866 --> 00:02:07,900 a squared is congruent to 1 modulo 3, 44 00:02:07,900 --> 00:02:11,200 that's by the Fermat's Little Theorem, 45 00:02:11,200 --> 00:02:13,966 and 1 to the power of 280 
is 1, so it’s congruent to a. 46 00:02:13,966 --> 00:02:14,900 47 00:02:14,900 --> 00:02:18,100 And then again if 3 divides a, then 
a to the 561 is congruent to 0, 48 00:02:18,100 --> 00:02:21,100 which is congruent to a mod 3, okay? 49 00:02:21,100 --> 00:02:24,100 So let's do the same trick instead of with 3, let's do it with 11. 50 00:02:24,100 --> 00:02:28,433 Then using FLT gives us what? So 
a to the 561 that's congruent to… 51 00:02:28,433 --> 00:02:31,966 again so 11 minus 1 is 
10, 10 doesn't divide 561, 52 00:02:31,966 --> 00:02:33,833 but it does divide 560. 53 00:02:33,833 --> 00:02:38,833 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, 54 00:02:38,833 --> 00:02:41,833 and 1 to the 56 is 1, so 
that’s congruent to a, 55 00:02:41,833 --> 00:02:44,666 and again if 11 divides a, then 
a to the 561 is congruent to 0 56 00:02:44,666 --> 00:02:48,000 is congruent to a mod 11. So in all cases, 57 00:02:48,000 --> 00:02:51,000 a the 561 is congruent to a mod 11. 58 00:02:51,000 --> 00:02:55,433 Lastly if the gcd of a and 17 is congruent to - is equal to 1, 59 00:02:55,433 --> 00:02:59,100 then again using FLT gives 
that a to the 561 will again… 60 00:02:59,100 --> 00:03:05,166 so 17 minus 1 is 16, and 16 doesn't 
divide 561, but it does divide 560. 61 00:03:05,166 --> 00:03:09,366 16 - so 560 divided by 16 
turns out to be 16 times 35. 62 00:03:09,366 --> 00:03:13,400 a to the 16 is 1, 1 to the 35 
is 1, that's congruent to a, 63 00:03:13,400 --> 00:03:17,266 and then again if 17 divides 
a, then a to the 561 is 0 64 00:03:17,266 --> 00:03:20,000 mod 17, which is the same as a. 65 00:03:20,000 --> 00:03:23,433 So in all cases for every single value of a, 66 00:03:23,433 --> 00:03:25,733 we have the following 
simultaneous congruences: 67 00:03:25,733 --> 00:03:29,800 a to the 561 is congruent to a mod 3, 
a to the 561 is congruent to a mod 11, 68 00:03:29,800 --> 00:03:32,833 a to the 561 is congruent to a mod 17. 69 00:03:32,833 --> 00:03:33,800 70 00:03:33,800 --> 00:03:38,166 Look at these three equations, these three numbers are co-prime, we know a solution - 71 00:03:38,166 --> 00:03:41,933 so if I instead of writing a to the 561 I - well… 72 00:03:41,933 --> 00:03:44,866 I mean, if you think about this like a 
Chinese Remainder Theorem type thing, 73 00:03:44,866 --> 00:03:49,000 then you know that I can 
combine these three statements. 74 00:03:49,000 --> 00:03:51,766 The generalized Chinese Remainder 
Theorem says that well if a to the 75 00:03:51,766 --> 00:03:54,666 561 is congruent to a mod 3, 11, and 17, 76 00:03:54,666 --> 00:03:58,766 then a to the 561 is congruent 
to a mod the product. 77 00:03:58,766 --> 00:04:01,533 So let me maybe put this on a new line just to 78 00:04:01,533 --> 00:04:02,500 79 00:04:02,500 --> 00:04:04,666 make it a bit clearer. 80 00:04:04,666 --> 00:04:05,833 81 00:04:05,833 --> 00:04:09,333 This is what the Chinese Remainder 
says, if x is congruent to a mod 82 00:04:09,333 --> 00:04:13,566 p 1, x is congruent to a mod p 2, 
and x is congruent to a mod p 3, 83 00:04:13,566 --> 00:04:16,633 then x is congruent to a mod the products, 84 00:04:16,633 --> 00:04:20,000 right, I guess this is actually more like - 
this is even like a Splitting the Modulus 85 00:04:20,000 --> 00:04:23,633 sort of thing. I can even write down Splitting 
the Modulus because all the numbers... 86 00:04:23,633 --> 00:04:25,266 87 00:04:25,266 --> 00:04:27,200 are co-prime. 88 00:04:27,200 --> 00:04:31,466 So either way is fine, and by generalized,
Splitting the Modulus, I mean either way is fine, 89 00:04:31,466 --> 00:04:34,266 but again since I have these three 
simultaneous congruences, that's exactly 90 00:04:34,266 --> 00:04:37,733 what the generalized Chinese Remainder 
Theorem or Splitting the Modulus tells us, 91 00:04:37,733 --> 00:04:41,433 that I can combine them and get that 
a to the 561 is congruent to a mod 92 00:04:41,433 --> 00:04:43,433 3 times 11 times 17, 93 00:04:43,433 --> 00:04:47,333 and as we said before 3 
times 11 times 17 is 561. 94 00:04:47,333 --> 00:04:50,566 Crazy, crazy proof. The 
main thing that works is that 95 00:04:50,566 --> 00:04:52,666 560 is a very special number. 96 00:04:52,666 --> 00:04:56,600 It happens to be divisible by p minus 1, q minus 1, and r minus 1, 97 00:04:56,600 --> 00:04:59,533 where p, q, and r happen 
to be the three factors. 98 00:04:59,533 --> 00:05:02,066 So how did I know to do 
this? Well okay, so again I'm 99 00:05:02,066 --> 00:05:05,466 privy to a little bit of knowledge here. I 
know that this 561 is something called a 100 00:05:05,466 --> 00:05:08,466 Carmichael number. A fantastic 101 00:05:08,466 --> 00:05:10,866 fun topic, so if you're bored studying, 102 00:05:10,866 --> 00:05:14,366 I would suggest taking the five to ten 
minutes reading up on it on Wikipedia. 103 00:05:14,366 --> 00:05:17,433 Carmichael numbers, that's the topic. 104 00:05:17,433 --> 00:05:21,933 Pretty cool stuff. These numbers are 
pretending to be primes, but they're 105 00:05:21,933 --> 00:05:25,500 not even close to be - they’re 
not even close to prime. 106 00:05:25,500 --> 00:05:30,000 There's a bunch of these, you can see these 
numbers. I think 561 is the smallest such number, 107 00:05:30,000 --> 00:05:33,466 at least it's the most often 
used if it's not the smallest, 108 00:05:33,466 --> 00:05:36,533 and it's really, really cool stuff. Again this is a 109 00:05:36,533 --> 00:05:40,400 number theoretic thing, 
but I think it's neat and… 110 00:05:40,400 --> 00:05:44,133 I don't know, like I said, I think it's worth a 
five minute read if you have the chance. 111 00:05:44,133 --> 00:05:48,233 So a fun problem for problem 
number 9. I think it's kind of… 112 00:05:48,233 --> 00:05:50,033 it’s kind of cool, has some soul, 113 00:05:50,033 --> 00:05:50,633 114 00:05:50,633 --> 00:05:53,266 which is weird to say about a math 
problem, but some problems 115 00:05:53,266 --> 00:05:55,500 are a little trickier and 116 00:05:55,500 --> 00:05:57,500 they have some nice solutions like this. 117 00:05:57,500 --> 00:05:58,366 118 00:05:58,366 --> 00:06:00,433 Alright, so I hope you 
enjoyed the final exam review, 119 00:06:00,433 --> 00:06:02,566 and good luck on your 120 00:06:02,566 --> 00:06:05,432 final exam or whatever you're 
studying for. Best of luck.