Prime factorization of 1007021035035021007001

[@Risu0chan]

Before watching the video: «That's impossible» After the video: «That was surprisingly easy!»

[@nebunudesalam8191]

not that ez

[@novesh7111]

Imagine they just gave a really big prime number and while students worked hard to factorize it, the answer would be right infront of their eyes

[@WilliamWizer]

if you give them a 21 digits prime number and ask to factorize it, they are doomed to fail. not even computers can factorize that kind of number in any reasonable amount of time.

[@BigDBrian]

@@WilliamWizer some may give up and just guess the number itself as a last resort ;)

[@janzwendelaar907]

Given it's competitive maths, I reckon a lot of students would very quickly guess the trick. I recognized the pattern in the number, I knew something was up, although I didn't know what it was. People who actually know these kinds of competitions, probably see very quickly that a number does not follow any pattern at all and must therefore be prime itself

[@sirmonke8946]

@@WilliamWizer A computer could probably solve that within 2 minutes

[@WilliamWizer]

@@sirmonke8946 surprisingly enough... no. there's no known method to factorize a number other than using brute force. to factorize a 21 digits number you would need to test divisiblity of that number against all numbers between 2 and 10^11 if we assume a milisecond for each division (and that's a fantasy) that would mean it would take over four months. I admit it's still doable but, as you can see, it's far from a couple minutes.

[@LordBlee]

I just found your channel and wanted to let you know that I absolutely love it. It has been over 30 years since I studied electrical engineering, so I am a math geek. And while I use math regularly, I don't deal with anything particularly complex. Your channel has been a wonderful reminder of how fun math can be. Thank you so much for sharing.

[@artsmith1347]

01:15 "If you like it, like it at the end." Many others *_start_* their videos by asking for a 'like,' which is backwards if I have never seen their channel before. Your videos never disappoint, so a 'like' at the start would be confirmed at the end anyway. But your approach was respectful of the viewers in a way that I have not seen before -- in the watching of many videos.

[@lornacy]

I also liked "share it with your enemies, they might need it" 😆

[@girishjain5288]

how do you find such problems

[@kinshuksinghania4289]

They can be found under a rock on a rainy day

[@thegiganerd395]

He said he found it in a competition

[@shailchitra9811]

Some students or subscribers also e-mail him questions

[@FadkinsDiet]

There are we bsites that keep track of these math competitions and provide links. It's a hobby to keep up with them and find interesting problems

[@Nzargnalphabet]

He’s trying to hack into the governments online security and it’s working

[@oyvindroth]

Beautiful example of experience-based intuitive mathematics. How come there are people that do not see the esthetics of maths? I think that even without particulat maths skills and relieved from the intimidating myths of how terribly difficult maths is, one should be able to meditate to e.g. this example just to cherish the pure beauty of numbers. Creds again to you!

[@jimbrooks2944]

I learned something today. I did not know you could use Pascal's Triangle in the way you did.

[@rogerkearns8094]

It's a neat trick that the result of any 3-digit number being multiplied, successively, by 13, 11 and 7 is a 6-digit number presenting the original 3 digits repeated. The reason why this happens is fairly obvious, given this video.

[@xinpingdonohoe3978]

This is smart. All along, I found that magnitude checks can help things make sense. For example, 101³≈100³=(10²)³=10⁶, so it should have 6 numbers tailing the 1. 7×11×13≈7×12×12=7×144≈7×140=7²×2×10 =49×2×10=980≈1001, so even if we're just guessing prime factorisations, it's a reasonable start.

[@kinshuksinghania4289]

1, 7, 21, 35, 35, 21, 7, 1 → binomial coefficients of (a+b)⁷ So if we expanded (1+1000)⁷ we would get the exact same number

[@zanti4132]

That is exactly what I noticed. Then knowing from experience that 1001 = 7 × 11 × 13, the prime factorization comes out as 7⁷ × 11⁷ × 13⁷. The whole process took less than a minute.

[@kinshuksinghania4289]

@@zanti4132 exactly

[@Planetyyyy]

Woah

[@tassiedevil2200]

@kinshuksinghania4289 Very nice. It's also helpful to note that the number is just a bit over 10^21 or 1000^7. Lastly, with your way of using Pascal's Triangle the origin of the of three sets of double zeros is obvious.

[@Grecks75]

Thank you, sir! That makes it really clear what's going on here with this number. The whole video could be summarized in this one sentence. 👏

[@tessfra7695]

Really good to see you back with these great videos again, sir..God bless.

[@bvenable78]

So cool. The relationship between powers of 11, 101, 1001, etc., and Pascal's Triangle, was completely new for me! (And I've got a degree in math; lol.) Thank you so much for this awesome trick! :)

[@Grecks75]

Same for me. Degree in maths but never heard of this trick. 😂

[@shutupthatepic]

If I’m remembering correctly the guts round has 3 problems at a time, and you have to submit your 3 answers to get the next 3 problems. So it helps to go fast/use tricks so you can finish and get to more problems, but at the same time you can’t fix/correct any previous problems

[@Kris-hz1ns]

Unbelievable !! I learnt something so beautiful today !!! Trillions of Thanks to you !!

[@er63438]

Been binging your videos since YT decided to recommend them to me. You're an awesome teacher dude, and the videos are super well structured. Keep up the good work! PD: Would love to see more Number Theory / prime numbers content 😃

[@sonicwaveinfinitymiddwelle8555]

the 1007 and 7001 mirroring themselves already gives big enough of a hint for it to be something to the power of 7

[@agindo]

you are a pearl of a human being. bless you ❤. cheers from austria.

[@gautamkrishna295]

Dropping a comment here for another video I saw of yours so you see it, you really explained the video of finding inverse of a matrix really well, it was a topic I found really hard and could not understand much. Thank you so much for your efforts and will surely recommend your channel to others. Much love from India.❤❤

[@PrimeNewtons]

I appreciate the feedback

[@kobethebeefinmathworld953]

A good hint of factoring such a kind of number is thinking about the binomial expansion

[@guidichris]

Nice!!! Saw the number pattern immediately, but tying it to Pascal's triangle was beautiful!!

[@Neo-u3h56]

Excellent intuitional solution. You are superb teacher.

[@pietergeerkens6324]

Very nice problem find! Took me a minute or two to recognize the number wasn't palindromic - but then the binomial expansion only took a few seconds to identify and verify. Spotting 11 as a divisor of 1001 was trivial as 11 divides (10 + 01 = 11); and the rest was easy. Now to check out the video, and how you solved it. P.S. Welcome back.

[@pietergeerkens6324]

I'm going to disagree about memorizing (with intent) random facts such as 1001 = 7*11*13. One inevitably collects a few of these over time spent solving puzzles, but the deliberate memorizing not so very useful. More valuable, IMHO, is to learn a wide variety of divisibility tests - or, even better, how to construct the divisibility test for any (smallish) prime in just seconds.

[@eduardoteixeira869]

I started thinking in the number and realize it has some kind of symmetry particularly in the center of the number we get 350350, thinking about I see that this is the result of 350 times 1001, then I tried to divide the entire number by 1001 which is not so difficult. Dividing by 1001 is easy and surprise this is an exact division and so decided to divide the quotient by 1001 and again this was an exact division and continuing the process I got 1001 to the power of 7. The rest is like you shown on the video it is not difficult to conclude that 1001 is 7*11*13. Thank you

[@shennyboi110]

The legend is back!

[@lukamiler5824]

The zeroes between the ones seem to be padding every number. If you take 101^5=10510100501, add a single zero before it and take every pair from it, you get 01, 05, 10, 10, 05, 01 which is exactly the fifth layer of the Pascal triangle without the carry from adding messing up the result. 11^5=161051

[@Grecks75]

How do you add links to KZbin comments? In your comment the term "Pascal triangle" is highlighted as a link. Edit: Nevermind, must be some automatic highlighting by the YT app.

[@donmoore7785]

Very nice explanation. One thing you did not mention early on was the observation of the pattern of the numbers in the middle - which was also easily seen. You held it under your belt until the key had already been found.

[@johnroberts7529]

You're such a good teacher. I do hope all's well re your absence.

[@mayo6009]

Your handwriting is incredible

[@TimothyLoftin-l1i]

Welcome back, I am a 76 year old physicist/engineer and have never seen one of your videos that was a waste of time. Gold in every vein!

[@nichls]

Bro you are the GOAT (guy of all time)!! Amazing 👏👏👏

[@toddpytel4481]

Beautiful number sense and overall math awareness in this problem. As always, I appreciate how well you elucidate good mathematical thinking - here's some crazy problem... what do we notice and how does that lead us to a solution? I have several students who love your videos, so please keep doing what you're doing! --Chicago Teacher

[@wildfire_]

the furthest i got was that there's no even factors.

[@bpark10001]

It is easy to test for factor of 11 by alternately subtracting & adding digits. You will get number modulo 11. You can do the same for 7 by using the following "weights" in the calculation: (units) 1, (tens) 3, (hundreds) 2. The weights go 1, 3, 2, -1, -3, -2, 1,... Test for 3 is simply sum the digits. Test for 13 uses weights 1, -3, -4, -1, 3, 4, 1,.... These weights can be calculated using modulo math, starting with units weight = 1 & multiplying by 10 & applying modulo, repeating for each digit until looping occurs. But your number is too easy as all the prime factors are "small". In reality you need to test for all primes up to the square root of the number. & if none found, declare it a prime.

[@epsilonxyzt]

Greetings! Never Stop Teaching!

[@dirklutz2818]

Very, very beautiful!

[@Bernd_OK]

This is ridiculously clever! 💯

[@chuckadams842]

I'm a retired prof and have a stupid question? What are you using to get the blackboard so clean? 🙂 I could never get one that clean. Of course, later we went to the white board with erasable markers and then to video projectors. Nice to see someone use chalk. I've just started (I'm always late to the party) working through all The Euler Project problems to prevent Alzheimers or at least put it off as long as I can. Spent all those hours learning applied mathematics, might as well use it. I also love to feed such problems to Wolfram Alpha to see if it will break.

[@akshat9282]

6:34 for anyone confused, just to clarify was for the statement it followed. Inception.

[@VeryGoodDeals]

nice i also recognizing the mirrored number thing and thought it might be divisible by 11 and confirmed using the divide by 11 trick. wasnt sure what to do after. never knew about the 11^x, 101^x, 1001^x,... thing representing pascal's triangle before. neat

[@sayedsefddine4209]

I like your presentation

[@asheep7797]

On first glance, it has 1, 7, 21, 35, 35, 21, 7, 1, so it obviously is of the form 1(x 0s)1^7. Gap of two zeros between the 1 and the 7, so it's 1001^7. 1001 is equal to 7*11*13 Ans: 7^7 * 11^7 * 13*7

[@JulioDavidAuster]

Absolutely wonderful!

[@DailyDoseOfTableTennis]

Hi I have a question,why the number start with 1007021 but end with 21007001? Between the 7 and 21 in the start there is 1 zero but in the end there are 2 zeros. And why this extra zero have to be in this specific position.

[@ZoonCrypticon]

Very interesting, thanky you! The question would be, if the mentioned long number wasn´t a "Pascal´s triangle number", what approach would you take to make a quick guess, on how big the lowest prime factorial must be and which of the frequently memorized prime numbers (1-100) would be most likely to start with?

[@ТимофейЧерников-щ2х]

"Those that stop learning, stop living" - that sounded like a Duolingo quote

[@maruthasalamoorthiviswanat153]

Excellent solution sir

[@shaozheang5528]

You also can do so for 202, 3003, 40004 etc.

[@dan-florinchereches4892]

I wonder if grouping factors would help 1*(10^0+10^21)+7*(10^3+10^18)+21*(10^6+10^15)+35*(10^9+10^12) 1(1+10^21)+7*10^3*(1+10^15)+ 21*10^6*(1+10^9)+35*10^9*(1+10^3) from this I observe 10^3+1 is a common factor because if we note 1000=A then the rest of the expressions are: 1+A^3=(1+A)(1-A+A^2) 1+A^5=(1+A)(1-A+A^2-A^3+A^4) 1+A^7=(1+A)(1-A+A^2-A^3+A^4...) Dividing by 1001=7*11*13 we get quotient 1006015020015006001 Dividing by 1001 again quotient 1005010010005001 Dividing by 1001 quotient 1004006004001 Dividing by 1001 quotient 1003003001 ........................................... 1002001 repeat 1001 so the original number is 1001^7=(7*11*13)^7

[@platypi_otbs]

that's amazing. I love it.

[@dougaugustine4075]

Welcome back. I liked the video so I left a like, just like you said.

[@sandeepsantoriya822]

Incredible ❤

[@TimoYlhainen]

Now that is a beautiful thing.

[@boumbastik]

This is really cool. Thank you so much.

[@RubyPiec]

Good video like always! Just some other question though: going to enter some math olympiad next year, any advice?

[@hurricane31415]

Blew my mind, in a good way.

[@shrikrishnagokhale3557]

Fantastic.Thank you very much.

[@AlletPhilippe]

Very impressive !

[@SmilingDiamondRing-jt5ps]

Nice approach

[@elunedssong8909]

Before: I quickly divided in my head up to 7 and got to 100000000000....1 through my division process. No way is that length of division going to occur mentally. I guessed this number must be divisible by 101, or 1001, or something similair like 10001, etc, just from looking. Since i also suspect it is divisible by 7 (and 11), 101 is not divisible by 7, so i was pretty sure it is some multiple of 1001, which is divisible by 7 (and 11) So I did 1001^2,3,4,5... (with a calculator, ie: cheating) and found the number in question. I guess I could have written out 1001^7 with a piece of paper and then its "fair"? Idk, but surely calculators wouldn't be allowed for this type of problem. I am so exicited to hear your approach!!! Edit: I am grinning as I hear your explanation. Wonderful!!!

[@trevjr]

Great. I love number theory but I don't know much. I wondered why there was no 4,6,or 8. I figured it wasnt divisible by 3. There are 3 double zeros, should be 4. My gut said something about 11, then I had to start the video. Old Pascal does it again!

[@claudiobruno3194]

Great Stuff and great Guy!

[@jurgenvogel3804]

This was GREAT ! WOW !

[@haackalexander]

Thank You for This Video. I hope you're well

[@drwho7545]

So the number has symmetry, in that the right side mirrors the left. But how’d that discount larger prime factors I didn’t glimpse. Whoave thought large numbers have structure like that.

[@TSR1942]

We were missing your session.

[@abezerianos1]

I HAVE AN INQUIRY. HOW THINK OF THIS METHODE

[@lornacy]

Welcome back!

[@bharatsambhare4162]

Superb!!!!!😊

[@shannonwalker6944]

OUTSTANDING!!!!

[@topquark22]

I haven't watched the full video yet. First thing I would try is, find the digital root of this number. If it's divisible by 3 or 9, or some power of 3, then the number is divisible by that power of 3. Ok, that didn't work. The next thing I would try is, the alternating digital root (taking each digit with an alternating +/- sign). That will tell me if the number is a multiple of 11. And, lo and behold, by repeating this process 7 times, I found that this number has a factor of 11^7. This is a good start to beeak it down. Using modular arithmetic, there are other easy ways (similar to digital roots) to check for divisors of other small primes, Since this is like an Olympiad problem, it is probably going to be divisible by some small primes. Not 2 or 3 or 5, but maybe 7, 13 or something. I did figure it out, but I won't spoil it for you.

[@topquark22]

PS: I did not notice that this number is a palindrome in base 10, until I actually watched the video. Not sure how I missed that, but, your solution is very clever.

[@JobBouwman]

I first saw a kind of palindrome. Then I recognized Pascal's triangle within a triplet pattern. Then I made the connection with convolution, so 1001 autoconvolved seven times. Then I realized that it was 1001^7.

[@crsmtl76]

Pascal’s triangle and binomial expansion jump on me what I saw the title. I intuitively said that number is (1000 + 1)^7. Got stuck there for a while…

[@tombratcher6938]

Me, for once, not needing the video and just seeing the answer in 30 seconds: A surprise, but a welcome one

[@Jono4174]

There is a divisibility test for 7,11,and/or 13 which would have quickly said the number was divisible by all members of the trio

[@PrimeNewtons]

Quickly?

[@dujas2]

Yeah, I think I saw another video on a divisibility test for 1001. It's similar to the divisibility test for 11 since 1000 is equivalent to -1 (mod 1001). The repetition is what would quickly show this is equivalent to 0. And the divisibility test might even make sense after testing 3 since, while 11 is easy to test for, 7 and 13 are not.

[@robertpearce8394]

​@PrimeNewtons I saw a video on checking for divisibility by 7. I think it was Matt Parker on Standup Maths (but it could have been Numberphile). It was not straightforward, and I can't remember how it worked. I really enjoyed your video, and I learnt something that I think I will remember.

[@Jono4174]

@@PrimeNewtons not that quick😀. Imagine the number is written with commas 1,007,021,035,035,021,007,001 Now sum all the odd trios 001+021+035+007=64 Sum all the even trios 007+035+021+1=64 Take the difference of these results 64-64=0 If this number is divisible by 7 then the original number is divisible by 7 If this number is divisible by 11 then the original number is divisible by 11 If this number is divisible by 13 then the original number is divisible by 13

[@FadkinsDiet]

​@@robertpearce8394based on powers of 10 mod 7. It's doable but not intuitive.

[@k_piyushm]

This is really amazing.

[@holyshit922]

My factorization program written in C# factored this number quite fast Factorization has seven 7 , seven 11 , seven 13 We could observe that this number equals 1001^7 (Binomial expansion and Pascal's triangle for coefficients of this expansion can be useful)

[@rafapardo5461]

I came for the math but I stayed for the smile

[@dthez4768]

You can also solve it with the palindromic method. You would have to divide out 10^10.5. Adding everything up you would end up with 10^10.5 * (10^1.5 + 10^-1.5)^7 = 1000 + 1. This is easier to see with the substitution of x=10^1.5.

[@DelPhoxe]

Extremely Good Question...!!!

[@StuartSimon]

You might have proved your point about the number of zeros needed between the ones if you continued down Pascal’s triangle and computed 11^5 = 100,000 + 50,000 + 10,000 + 1000 + 50 + 1 = 161,051. The need to carry makes the relationship between the powers of 11 and Pascal’s triangle break down at 11^5.

[@AyyojJi]

Thank you mster😊

[@mathcanbeeasy]

Is not necessary to know a relation between triangle of Pascal and 11, or 101, or 1001.... Is anough to know the relation between triangle of Pascal and binomial expanding. If we expend that number, we get: 1*(10^3)^7+7*(10^3)^6+21*(10^3)^5+...+7*(10^3)^1+1, which is (10^3+1)^7. Nice video. 🙂

[@SamuelDonald-pr2uu]

Hello Prime Newtons! I’m one of your subscribers and a big fan. Please I need your help with a Mathematical problem. How do I reach you sir?

[@shailchitra9811]

I guess, he provides his email in the video

[@lorenzovillani3102]

The number of zeroes correct? I think there's an extra 0 between 21 and 7 at the end, otherwise the rule of the number of zeroes doesn't apply regularly(?)

[@yurenchu]

Don't look at the number of zeroes, look at the number of digits after each binomial coefficient number/Pascal's triangle number: the number of digits after each binomial coefficient number (or Pascal's triangle number) must be a multiple of three (because 1000 equals 10^3 ). By binomial expansion, (1000 + 1)^7 = = Sum B(7,k)*(1000^k) , from k=0 to k=7 where the binomial coefficient B(7,k) = (7 choose k) = 7!/[ k! * (7-k)! ] is the k'th entry in the 7th line of Pascal's triangle. (Note: Pascal's triangle has a 0'th line, which contains just a single 1, and in each line the first entry is the 0'th entry, which equals 1. The n'th line in Pascal's triangle contains (n+1) non-zero entries.) As you can see, in the expansion each binomial coefficient B(7,k) is multiplied by a different power of 1000 .

[@dneary]

I noticed the pattern when you cut the number into 3 digit chunks, then noticed 7 = 7C1 = 7C6, 21 = 7C2 = 7C5, 35 = 7C3 = 7C4 - so you get (10^3 + 1)^7 and then 1001 = 11 * 7 * 13 finishes it off.

[@vishalmishra3046]

This is a 22 digit number - large enough to scare people from trying to get started. Last digit indicates that it is not a multiple of 2 or 5. Sum of the digits indicates that it is not a multiple of 3. Alternate digits add to 19, so 11 has to be a factor of this number. On dividing by 11, the same rule works on the quotient. So, the number (or at least some factor) is some power of 11. This worked 7 times, so 11^7 is a factor but 11^8 is not. 7th power indicates, that lets try prime roots at least for single digit primes. Square root, cube root and 5th root are not integers but 7th root is 1001 which is multiple of 11 (same alternate digit sum equal rule). 1001 / 11 = 91 = 7 x 13. So, the 22 digit number = (7 x 11 x 13)^7. This number represents a very bad RSA public key modulus that banks should never use for encryption of high value transactions 😁

[@vishalmishra3046]

Any good prime factorization problem MUST avoid multiples of small primes like 2, 3, 5 and 11 due to easy divisibility rules that expose the solution a bit too easily, as in this example.

[@Nothingx303]

Dear sir I have a very interesting puzzle for you I am Surya from India here is the puzzle The problem involves finding an even number:- Joh has an even number and asks his friend to guess the number using the following (clues 1) the sum of the reciprocal of the number of possibilities of writing the number as the sum of two different integers and the actual number is 13 /2 (clue 2) the repetition of the number is not allowed and the order of the pair doesn't matter. What is Joh's number?? Si r I hope you see my message Thank you 😊

[@yurenchu]

Your description isn't entirely clear, but let X = Joh's even number, Y = the number of possibilities of writing X as the sum of two different _positive_ integers, Z = (1/Y) + X then determine X such that Z = 13/2 = 6.5 Well, the solution must be that Joh's number equals 6 . (If X = 6 , then X is the sum of either {1, 5}, {2, 4}, or {3, 3}. Since {3,3} is discounted because the terms in the sum must be different, there are only 2 possibilities left; hence Y = 2 . The reciprocal of Y is then 1/Y = 1/2 , and the sum Z then becomes Z = (1/Y) + X = (1/2) + 6 = 6.5 = 13/2 . This is also the only solution, because for non-zero Y, the value of 1/Y must be between 0 and 1, hence X = Z-(1/Y) = (6.5 - (1/Y)) must be between 5.5 and 6.5 , so integer X must equal 6.)

[@Nothingx303]

@@yurenchu good but if you know this formula n-2/2 for writing it as the sum of two different integers and repetition is not allowed for n>2

[@yurenchu]

@@Nothingx303 What do you mean by the formula n-2/2 ? Don't you mean Y = (n-2)/2 where Y is defined as in my previous reply, and n is the same as X from my previous reply? Please, properly use parentheses when necessary. The expression n-2/2 equals (n-1) , which is probably not what you actually meant to say.

[@Nothingx303]

@@yurenchu yes I mean y =(n-2)/2 Actually you can solve the equation like this n+2/(n-2) =13/2 simplify So 2n²-17n + 30 =0 solve it to get 6

[@mevg6378]

At first glance it is easy to notice that 1,7,21,35,35,21,7,1 are binomial coefficients in a polynom of power 7. So, the initial number is just (1000+1)^7 =(7•11•13)^7

[@jenshagelstein7695]

if solving these problems is level „genius“ , what level is „creating“ such problems?

[@TheCondoInRedondo]

This was a fun one!

[@wolffang21burgers]

Could probably be more rigourous when ignoring zeroes... Otherwise could make a mistake with 10070021003500350021007001 or 100702103503502107001. Probably best to just expand out (1+x)^7, and then match to determine x = 1000.

[@aryahan4976]

this is superb

[@khiemngo1098]

(1001)^7 would require two zeros between each number in the seventh row of the Pascal triangle !

[@user0xff]

I solved by applying divisibility rule by 11. But this solution is way more cool

[@piloser.studio]

mas amba lagi ngajarin para suki cik 😂😂

[@Elcio_Leal]

Maths is not a science: it is a kind of art

[@londonalicante]

I didn't know the factorization of 1001, but it's a fairly easy check that it 1001 = 990+11 hence 91*11 and I did know the factorization of 91.

[@kevinduffy7383]

No! Im going to like the video at the beginning!

[@assiya3023]

صباح الخير أستاذ الاحظ أن العدد ليس مماثلا من اليمين واليسار فكيف يمكن أن نطبق الفرضية التي استعملت 10072 0 21035 0 35021 00 21001 هنا صفر واحد عل الشمال وصفرين على اليمين ، أتمنى أن ترد علي وشكرا

[@Newgodlove]

Ah yes. The question of life itself