Liar Numbers - Numberphile

Fermat's "Little" Theorem is great - but beware of Fermat Liars and tricky Carmichael Numbers.
More links & stuff in full description below ↓↓↓
Continues at: • Fool-Proof Test for Pr...
Featuring Dr James Grime - / jamesgrime
Support us on Patreon: / numberphile
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
Videos by Brady Haran
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9
Numberphile T-Shirts: teespring.com/stores/numberphile
Other merchandise: store.dftba.com/collections/n...

[@anisometropie]

“…is called a fermat liar. Ooooh, it's not really prime, it's lying. It tells me it's prime and it's not. Naughty!” James talks are my favorites :)

[@RiccardoBello98]

I wonder what CGPGrey would say about the "Naughty!" part :'D

[@PebsBeans]

He said that right as I read that

[@RyanLynch1]

LOL same

[@shoaibmohammed3707]

2:50

[@lucastsui5415]

This is a lesson. If you are a number reading this, don’t lie.

[@shotguntornado]

I love how cheeky James got about the $620. "Think of what you could do with all that money!" He's my favorite face on this channel.

[@polsp5812]

shotguntornado uhuhuhhhh you could buy yourself a chocolaqte iceream every day

[@Ricardordz11]

Pol SP Twice on sundays!

[@dgeri98]

+shotguntornado I think he's the favourite of most subsribers

[@brrrd5303]

That completely depends on if it is £ or $.

[@DanDart]

+MelodyFluff it's $ check it out

[@crazydrummer4827]

This is so Parker Square test.

[@rawovunlapin8201]

Matt "Carmichael" Parker primes

[@milossantrac3096]

Didnt street

[@debjit811]

Woah u have 341 likes 👀

[@asdasdasdasd714]

We need to pay more salary to mathematicians. He almost lost his mind over 620$ :D

[@schadenfreudebuddha]

there's probably just something mathematically amazing about the number 620.

[@00bean00]

schadenfreudebuddha yes, it's the number that allows you to buy ice cream X days a week, twice on Sundays...

[@GermanRumm]

Any Nobel man knows that the opposite is true ;)

[@GermanRumm]

Every nobel man thinks the opposite ;)

[@phs125]

Depends on where you live. I'm a doctor in India and I need to work 2.5 months to earn 620$

[@colinmusik]

Quickly becoming my favorite youtube channel.

[@numberphile]

wow, thanks

[@colinmusik]

Numberphile Don't be so surprised. For someone like me who doesn't have a lot of experience in mathematics, these are absolutely amazing videos. Very inspiring and skillfully made to reveal the awesomeness of mathematics. I think just about any discipline can be presented an a boring manner if you're not particularly clever. Needless to say, you guys are indeed very clever. Thanks so much for doing what you do!

[@Romeo-qk8tk]

+Numberphile i love math. im in 4th grade and everyone asks me about math but when i dont know,i come to you

[@adamledger6836]

+Colin Huggins yep same learnt so much new stuff from this one over the last few weeks

[@miurkahidalgo4028]

It's everybody's favorite channel!

[@Borednesss]

$630 wouldn't even cover the cost of electricity to compute a counter example I bet haha

[@jakthesmack]

I've spent the majority of my weekend watching Numberphile videos. Call me insane, you guys make numbers way more interesting than school ever did. I feel excited to learn again.

[@irenekay7934]

so true!

[@isaacheaton1805]

+Logan Fehr That's because the brain loves learning. It addicted it learning and it's amazing how school can manage to make it boring for people

[@irenekay7934]

***** why would it be?

[@isaacheaton1805]

+Leen B No I don't blame the school for not being able to teach. I would blame the parents that can't punish there children. And I understand that it's difficult to make a lesson interesting when you have people like that.

[@rick19471]

+isaac heaton It has been my experience the problem is parents who live to punish their children. and other people's also.

[@captainpalegg2860]

It’s 2:43 am, I have class in the morning, I'm a freaking *geography* major…and here I am bingeing Numberphile.

[@armoredp]

620 dollars, I'm regretting not becoming a mathematician already. It seems to be a life of pure decadence and unequaled wealth.

[@SnackMuay]

James is great. I love all the people you have on this channel, Brady, keep up the good work.

[@numberphile]

thanks. will do.

[@thihal123]

James is really great.

[@drinkingthatkool-aid3193]

+thihal123 Yeah I love his enthusiasm and passion. Many professors in college lack that.

[@thihal123]

Moaiz Shahzad A lot of professors in college are not too interested in the pedagogical side of being a professor. The tendency is to prefer the research and writing parts of professorship.

[@SatinFoxx]

Twice on sundays!? *sets to work*

[@patjohbra]

One day I hope to find someone that makes as happy as primes make Dr. Grimes

[@PoweDiePie]

He should change his name to Dr. James Prime

[@Vezur-MathPuzzles]

@@PoweDiePie Grime is fine. He can make a show called "Grime Prime Time".

[@acorn1014]

Maybe this test is actually for Carmaecal composites, and every prime number is a liar.

[@imveryangryitsnotbutter]

That's just a conspiracy theorem.

[@Zwijger]

No because the primes are what define the Carmichael numbers. A number that passes this test, but isn't prime, is a Carmichael number. You can't define that without primes.

[@harryboynton7800]

CrazyOrc Someone missed the joke

[@lonestarr1490]

@@Zwijger Actually, you can. A Carmichael number is a number _n_ that is divisible by some _m < n_ and for all integers _b_ with _(n,b)=1_ satisfies _b^(n-1) = 1 (mod n) ._ See, no primes here.

[@rushunnhfernandes]

@@lonestarr1490 saying that n is divisible by some m

[@sbrunner69]

How wonderful of a person is Dr Grime! What a fantastic likable human. I wish I could always be around people like him.

[@nerdbot4446]

$30 at the beginning and now $620? Why they´ve picked such random values? Why not $561? Or $1105? Or $1729?

[@sieevansetiawan4792]

Why they pick composite numbers?

[@josebobadilla-ortiz7405]

They should offer the $ value of the counterexample.

[@Korpionix]

@@josebobadilla-ortiz7405 A 7 hour-old reply to a 7 year-old comment with two replies, interesting...

[@goutamboppana961]

@@Korpionix with 2 replies?

[@Firefly256]

@@josebobadilla-ortiz7405 that’ll probably be the whole earth

[@merlinmagnus873]

How do you get a mathematician to solve a difficult problem? Offer a years supply of Klondike bars! That will get it solved fast.

[@stevenxu5747]

Clearly superior than offering $1M. We would have proven the RH by now, damn it! :)

[@unpaintedcanvas]

What would you do for a Klondike bar?

[@zanti4132]

It's a little known fact that the guy who proved Poincare's Conjecture didn't actually refuse the million dollar prize, he just asked to be paid in Klondike bars.

[@elvicash]

How many Klondikes bars in a years supply?

[@Friedeggonheadchan]

I want Mr. Grimes to call me naughty, over and over again.

[@hanel6662]

Change your name to 2

[@wonderwoman2949]

@@hanel6662 lol😁

[@surrog]

Thank you brady for adding subtitles to your videos, I have shown your channel to several hearing-impaired friends and they absolutely love it =)

[@nowneothanielverse]

Sometimes i wonder after watching a numberphile video i ask my self. Am i a prime?

[@LazaroCarvalhaes]

"Prime" in portuguese is translated as "cousin", so if you aren't, just start a family in Brazil.

[@3003DaRkNeSs1998]

Lázaro Carvalhaes not only in portuguese but also in spanish.

[@JonWonders]

I was born in 1999, which is a prime number. I guess I'm a prime.

[@jauume]

Luis Espinoza Cousin in spanish is primo. Close enoguh I guess

[@Sunspot1225.]

*ItsAMb * if you have to ask your not.

[@miakablan8792]

i am in love with this guy

[@gohan12991]

mia kablan lol i read your name as mia khalifa

[@aidanivesdavis]

James is hilariousxD

[@47571660]

Running time: 7:09 709 is a prime I see what you did there.

[@myrus5722]

Waxwing Slain Its 7:08 after the update...

[@panda4247]

it's a Parker prime then (sorry, I could not resist)

[@sadchicken5282]

Insert Channel Name o

[@DevonBernard]

Great video guys! I always love hearing your new math facts. Keep up the great work!

[@Devilyaki]

I have the number, just holding out for more icecream treats :3

[@addeyyry]

The thumbnail is brilliant...

[@VickyBro]

I love this guy....always brings a smile to my face. And thanks to Brady.

[@morganabbotts]

I love this channel so fascinating, helps with our in class debates for my A-level.

[@YouTodayKing]

Yes! Dr. James Grime should do a lot more of these vids!

[@velocity173]

I love your videos and cool prime tests, keep making great videos! Also do a video on the number 73 the best number

[@NeutronicBusch]

KEEP DOING YOUR GREAT WORK!

[@westforduk]

Thank you for bringing closed captions back, i've missed Numberphile!

[@TheReaverOfDarkness]

One way to check if a number is prime is to try dividing it by everything up to its square root.

[@GeorgeDeLaRosa182]

i live in california and it is 5:22 right now and i just woke up. my mother walks in my room and yells YOU ARE STILL UP? HAVE YOU BEEN WATCHING PORN ALL NIGHT? and i reply with no mother im actually watching a video on fermat's 'little' theorem. now im punished for 2 weeks. thanks math

[@aidaneglin781]

yep that totally happened...

[@lyeahthatl6690]

George G what does it mean?

[@teekenny2965]

wait why did you get punished what does your mom have against maths videos

[@habibaghasafari2237]

an interesting test for primes. i didn't know this. thanks brady

[@Mattio_]

Damn, I want a choc-ice everyday for the next few years!

[@heoTheo]

Really this makes me so happy how joyful he is about math. Sometimes I get stuck on something, and then I get it. and then the best part comes I get to explain it in the same joyful manner. :D Great!

[@RobbieSherman]

Thumbs up for the choc ice

[@bucsredsoxredwings]

The biggest know prime +1 = passion of James talking about math.

[@Esloquees]

Grime, you make me laugh every time! Genius!

[@314rft]

$620. That obviously was raised from $30 due to inflation.

[@freshrockpapa-e7799]

Thank you captain obvious.

[@ItsTeezoUBZ]

Bradah you make Math hella fun and interesting. LEGIT!

[@FishKungfu]

Can't get enough of this! Love it!

[@TheMegaJaytee]

that's a great presentation!

[@aoshi1992]

No disrespect for the other people that show in this youtube channel, but james is the best (and I just found out he have another channel now I have hours of videos to see =D)

[@kdryden29]

I missed him! Nice to see him again!

[@dunx125]

aww, whose the cutest little theowum in the world; you are little theowum, you are!

[@valor36az]

Best explanation of Fermat's little theorem and application.

[@Zw1d]

He such an awesome guy! Great video.

[@Kapomafioso]

I lost it at 2:50 "Fermat Liar uuuuuuuu" :D

[@coyraig8332]

This theorem works like the scientific method: question (is this integer a prime number?) --> hypothesis (if it is, then it passes this test) --> experiment (plug it in) --> observation (did it work?) --> conclusion (it did(n't), so it is(n't) a prime). And like science, it isn't perfect. It's just the best we have.

[@xavierstanton8146]

Well Fermat's Little Theorem just says that if p is prime, then the test works. All this video shows really is that the converse isn't true, not the theorem itself. I get what you're saying though

[@Ruaille]

That darn three. Noone likes a snitch.

[@TremaineMcCants]

Perfect

[@kamrunnesa5769]

Watching numberphile videos and scrolling its comment box make my day.

[@metleon]

1 actually follows Fermat's Little Theorem perfectly (a^1 - a = 0) but also isn't a prime number. That means the theorem works perfectly for every number with 2 or less factors. Also, 5^4-5=620 and 2^5-2=30. Is that the significance of those amounts of money?

[@mindstormmaster]

561^561 - 561 is surely divisible by 561 too right?

[@jeffreylevyhe-him1959]

Thanks for another wonderful video! It raises a couple of questions for me that I'm hoping you or a commenter can answer. 1) Why does the test stop at p? For example, if you're testing whether 5 is prime, why isn't it of interest whether 6^5-6 is divisible by 5? I'm sure there's something simple I'm missing. 2) The Wikipedia article on Carmichael numbers uses a different formulation: a Carmichael number is a composite n such that b^n = b (mod n) for 1

[@andreasl3974]

And here I am the 1st person who liked your comment 7 years later.

[@filipheller]

@@andreasl3974 youre not alone😉

[@hybmnzz2658]

Oh wow nobody gave an answer in 8 years. Well I'm bored so: The triple equal sign is known as a "congruence". It is used to emphasize when things aren't quite equal but practically equal with respect to some condition (in this case having the same remainder). It is pretty redundant to use that symbol when it's clear we are working mod n but it is a matter of taste. As for why we can stop before checking 6^5 = 6 (mod 5) this is a beautiful thing about modular arithmetic, all that matters are the remainders when dividing by 5. Notice that 6^5 = (5+1)^5 = 5^5 + 5^4*1 + ... + 1. It might seem intimidating expanding a fifth power but the exact value is unimportant. Basically when expanding you get a lonely 1 from each 1 in the five brackets and everything else has to be a multiple of 5. Modulo 5 all multiples of 5 zero out and so we get 6^5 = (5+1)^5 = 1 = 1^5 (mod 5). In general it can be shown a=b (mod n) means a^k = b^k (mod n). So checking just 0,1,2,3,4 accounts for all numbers mod 5. Here's something fun if you've read this far: In practice mathematicians just know modular arithmetic is convenient and considering just remainders is sufficient. A more general notion is quotient spaces where we create mathematical structures that are determined by representatives (in this context remainders). All this proving that a=b implies a^k=b^k is abstracted away by just knowing "relationships between elements of a quotient space are independent of choice of representative".

[@timchorle]

So can you do a video explaining why Fermat's little theorem should work? I'm sure their are various proofs of course, but I'm trying to wrap my mind around why this should logically work in the first place.. it seems a bit strange and amazing! Love the show keep up the great work!

[@1KevinsFamousChili1]

Whenever I hear Fermat I always picture Andrew Wiles, It threw me off when the painting of Fermat came up :P

[@TemporalOnline]

So cool!

[@mattlm64]

I vaguely remember Fermat's little theorem being used to re-arrange some equations for RSA cryptography. A video on that would be nice as it's quite interesting, but might be quite difficult to follow for some people.

[@sachsenschnitzel6552]

at the beginning he said, that 1

[@NeutronicBusch]

AWESOME!

[@jimpikles]

that's a lot of choc ices, mmmmm. here's my pen and paper?

[@venkateshbabu1504]

If G gravitational constant is a derived entity of frequency division. When you divide frequencies you get gravity. But when you multiply you get energy. Any number raised to prime minus one can be a multiple of that number. G is the multiplier numbers of prime powers. If you have prime powers they always tend to create frequencies. Example 2 power 2 is four and you can always balance them.

[@FlyingTurtleLP]

620$? ... why not 561, 1105 or 1729$?

[@rangedfighter]

maybe after taxes it's 561$ :P

[@sreedevip4330]

Thanks a lot, ❤❤❤

[@josuegordillorivera4647]

i love this guy.

[@michaelempeigne3519]

if a number , n , can be factored into a * b * c * ........ then it is a carmichael number if ( a - 1 ), ( b - 1 ), ( c - 1 ), etc. divides ( n - 1 ) so for 561 = 3 * 11 * 17 ( 3 - 1 ) divides ( 561 - 1 ) ( 11 - 1 ) divides ( 561 - 1 ) and ( 17 - 1 ) divides ( 561 - 1 )

[@Carvin0]

I'm afraid James has made an error. Carmichael numbers pass the Fermat Little Theorem (FLT) for all integers less than the Carmichael number that are RELATIVELY PRIME to the Carmichael number, NOT ALL INTEGERS as indicated at 4:00. For example, 406 ^ 560 = 1 mod 561, but 407 ^ 560 = 154 mod 561. Notice that 561 = 3 x 11 x 17, 406 = 2 x 7 x 29, and 407 = 11 x 37. Notice that 406 has no factor in common with 561, that is, 407 is relatively prime to 561. There are 240 integers (none have 3, 11, or 17 as a factor) less than 561 that correctly "witness" 561 as a composite, and 319 "liars" that falsely suggest that 561 is prime. If EVERY integer a < p satisfies a ^(p-1) = 1 mod p, then p is truly a prime. But of course is is highly compute intensive to check that, so it isn't a practical test.

[@enceladus32]

James is my favourite person on this channel

[@coelloello]

I dunno why but the choc ice bit completely slayed me, my jaw hurts

[@RexGanymede]

james's sense of Irony/Satire enraptures me, substantially. *Ssss, **_oooooooo_* - indeed, Mr. Grime; *Ssss, **_oooooooo_* - indeed.

[@metleon]

First bagels now ice cream. This channel's making me hungry.

[@utkarshjetly668]

0:11 “Fermaaaaaaaaahs”

[@igesio]

I love Dr Grime

[@DiscreteLivingDeath]

For 561 this extensive procedure isn't necessary, since its dividers are obvious: 5 + 6 + 1 = 12, it's divisible by 3. 5 - 6 + 1 = 0, it's divisible by 11. So it's unfair to call it a liar! ;-) Also work with 11 (but not 3): 341: 3 - 4 + 1 = 0 41041: 4 - 1 + 0 - 4 + 1 = 0 75361: 7 - 5 + 3 - 6 + 1 = 0 101101: 1 + 1 - 1 - 1 = 0 1729 works with 7: 29 (the last 2 digits) + 2 * 17 (2 * the rest) = 63, which is divisible by 7. And with 19: 2 * 9 (2 * last digit) + 172 (the rest) = 190 Also for computers, wouldn't it be the easiest way to check divisibility using the perfect reliability of the cross sums? Amazing videos by the way, you have a new subscriber. :-)

[@NoNameAtAll2]

561 is not a liar 2 is

[@andrewbloom7694]

When you've watched so many math videos on youtube you already know what Liar numbers are lol

[@inthefade]

101101 is such a cool Carmichael number.

[@gooser41]

Factual error: There are 21853 Fermat pseudoprimes for base 2. The number quoted in the video is missing the digit 5 and thus underestimating by one order of magnitude (and just for reference, there are 2163 Carmichaels below 25*10^9).

[@Dr.HazharGhaderi]

Nice!

[@shugaroony]

Ooooooooh, naughty! James went very Kenneth Williams there! :D

[@slomotrainwreck]

I, and many other "geeks" use Prime95 to stress-test the CPU & RAM in new computer builds. Very interesting video! Thumbs up!

[@JacksMacintosh]

Hey Brady! I was just wondering a couple things First of all, do you have a video on this bailie-psw test? second, is any pattern or formula or way to determine Carmichael numbers? or do they kind of just exist when they want to?

[@ghk128]

this is A+ James material

[@smergthedargon8974]

The Russian guy (bad with names, can't remember) is my favorite professor on the channel, but Primes Grimes is an extremely close second.

[@benoitst-jean7295]

Are there any stats on number n > k telling us statistically indicating the "efficiency" of this method?

[@Neueregel]

good one

[@PaulDve]

If you like this guy James he also has his own channel (singingbanana) that's just as interesting.

[@PinkChucky15]

Very cool

[@arkanon8661]

"the first carmichael number 561" 1 is carmichael, right? i mean, its not prime (which im pretty sure is the meaning of composite), and it passes 1^1-1=0 (which is divisible by 1) and it passed all tests up to its value there look

[@alexandterfst6532]

Brilliant

[@videotrash]

I always wondered how you arrive at such theorems- just playing around with the numbers for long enough?

[@gabriel-et3gy]

Just in case someone is wondering: 2^341 - 2 = 4479489484355608421114884561136888556243290994469299069799978201927583742360321890761754986543214231550 and thats equal to 13136332798696798888899954724741608669335164206654835981818117894215788100763407304286671514789484550 * 341

[@David-ud9ju]

I love how he was contemplating spending the prize money on choc ices.

[@jontorstrm8714]

never been a math nerd but i´m starting to like this.

[@malcolmclarke621]

Slow but flawless way to test for primes: talk the mod of all the numbers greater than 1 and less than n, which is the number you're testing to be prime. If any of the numbers >1

[@NuisanceMan]

+Malcolm-Lyndon Clarke Actually, you can make it shorter than that. You only need to use divisors that are prime themselves, and you only need to go up to the square root of n. So, for example, 97 is prime because it doesn't divide evenly by 2, 3, 5, or 7, and the next prime, 11, is already more than the square root of 97.

[@nubSawace]

the most elaborate promotion for choc ice I've ever seen.

[@relike868p]

Why do you have to impose the restriction 1p as each a is congruent to some a' mod p where a' is between 1 and p inclusive...

[@vasilivanich3842]

If it works for all a < p (and obviously for p), then it works for all numbers, as any number 'c' can then be represented as c = (p + b), where b < p (or if c is big enough you just take some integer amount of p instead: c = (kp +b) - it doesn't really matter). What you then have to check is whether (p + b)^p - (p + b) is divisible by p, but all the summands in (p + b)^p when you multiply it by itself p times will contain p to some power exept for one, which is b^p. So you will have a bunch of numbers that are (p to some power)*(b to some power), but these are naturally divisible by p, and the only questionable thing left is b^p, but b is less than p and by assumption any number less than p satisfies the desired property, that is: b^p - b can be divided by p.

[@Djorgal]

Yes that's exactly that. Doing the test with a is the same thing as doing the test with a' its class mod p. If a number passes the test for all a between 1 and p then it passes it for all a.

[@DiaStarvy]

You don't obtain more information. Let's say a^p - a ≡ 0 (mod p), where 0

[@PiotrBaczek87]

Can you do a follow-up on how Carmicheal numbers affect RSA Cryptography and what primality test is used in RSA?

[@carmacksanderson3937]

To my understanding the $620 offer applies to something referred to as the PSW conjecture (as stated on John Selfridge's Wikipedia page) If a p mod 10 = ±3 And 2^(p-1) mod p = 1 And f_(p+1) mod p = 0, where f_n refers to the nth Fibonacci number Then p is prime (or so the conjecture goes). I myself have check every such number below 30 billion and found no counterexamples