Interestingly this also applies to rows that are powers of primes as well. every power of 2 row consists only of even numbers, every power of 3 row consists only of multiples of 3, and so on for all primes.
Modification of the same proof applies. Only factors of p^n are powers of p. This time, however, p is not greater than k. However, notice that you can’t cancel out ALL the instances of p in the numerator, at least one must remain, ergo, p is a divisor of all the other numbers in that row, excluding the 1s.
Holy crap, i got the biggest fright of my life when he said, 'by the way Sean, Your camera is still on...' i replayed the video so many times to check if i was hearing my name properly
then , if you know newton's binomial theorem, the sum of all the elements of a row is 2^n where n is the row you are looking. So, if p is prime, if we sustract the 1+1, then p divides 2^p - 2 = 2(2^(p-1)-1), if p not 2 you can have some fermat's little theorem experience jajaja.
(I may but be missing something here, please correct me if I'm wrong). It seems to me that, if p is prime, Fermat‘s little theorem will help us prove that the *sum* of terms is a multiple of p. Don't we need to prove *each term in that sum* is a multiple of p? Perhaps some more steps are required here?
Just do the binomial expansion. For row n, n will be in every term and since n is prime it can't be divided out by the components of the factorial terms underneath (until you get to the last term which has n! on the bottom, but this term is 1, so obviously it divides out at that point). So every term has n as a factor. Job done.
I will admit to being a math moron, my degree is in History and Political Science. This has fascinated me, thank you. You have a new follower and sparked an interest in math in a 54 year old grandfather.
for those that wish to find why the diagonals are also multiple of the primes "with exceptions" I would advice to choose any prime (for example 7) and replace all numbers on the triangle by their value mod the prime you had choosen. the pattern that appears is quite simple, simetric and beautiful (like everything made with proper maths) note: you may need to make quite a triangle to notice the pattern. about the prime you choose squared.
Disclaimer! I'm no mathematician, but: I'm guessing it is related to the fact that -- given we already proved that the rows of primes are all multiples of that prime -- the (inverted) triangle underneath that row will always be a multiple of that row's prime (assuming we understand Pascals Triangle comes from the addition to the to numbers above it), and any addition of two multiples of a number will always be a multiple of that number. The second part is harder for me to explain, but I can guess it is also related to the same proof in this video. Each row that is a multiple of a prime will contain a set of multiples of that prime -- I don't know how to prove it, but I'm guessing has to be related to that proof because it's just that same proof but it's just a multiple of that proof (?) -- that multiple comes from multiplying by "a" (e.g. p=7, a=2... so the new row 2p, or 14). I suppose we actually expand the proof, so that 0
There is a one-line combinatorial proof: (p choose n)(n choose 1) = (p choose 1)(p-1 choose n-1). This also proves a more general result that any two numbers from the same row are always not co-prime excluding the 1s.
@@anshumanagrawal346 No offense here but I am not saying it is trivial but just giving an elegant alternative proof. If you mean the proof of the more general result is not trivial, you need to replace the 1 with any number r < n and compare (p choose n) and (p choose r).
I found that the fact that previous row consists just 1 and (-1) mod(prime) for any row prime in natural power is cool too. I mean it can be easily shown, like by using C(n+1, k+1) =C(n, k) +C(n, k+1) and 1 on every C(n, 0). 0=1+-1, 0=-1+1... Also by (-1) mod prime I mean prime-1, but using -1 is easier sometimes, and for 2 it obviously same thing +1 and -1, they'll give 0 in sum in any pair
Second question. *Claim:* Not just the diagonals have this property, but every triangle for which the segment of such a diagonal forms the left edge. *Proof:* Let n = m*p, and 0 < k < p (we're mirroring stuff here). Then the quotient q := n!/(n-k)! has a factor n=m*p, and since k
As for the diagonal part, we started with the row of multiples of p (including the prime itself). Due to the construction of the triangle, we're just adding a bunch of multiples of p together to make a sub-triangle (that's upside-down) composed of the prime row + the diagonal twice, which obviously gives more multiples of p. The gap appears because we've introduced a 1 from the right side of the triangle in p's row. This carries down the triangle, by construction, to give a diagonal with values of (a multiple of p) + 1, a "gap" diagonal. Immediately after the "gap" though, we have another diagonal composed of another 1. Similarly, this 1 will be carried down the triangle to the term in question in the p diagonal. However, there's p - 2 values between this term and the 1's diagonal which is composed of the "gap" 1 being over counted. So, the term will contain two 1's (from the "gap" and this term's diagonal) and p - 2 1's (over counting the "gap" 1, the distance between the p diagonal and 1 diagonal), which add to a p amount of 1's, giving a multiple of p! From there, the pattern continues. I think I may have skipped to the conclusion in the end there, but you mentioned the fractal that can be made with the multiples of 3. After looking at the multiples of 5 and 7 when thinking about this diagonal problem, I think all of the primes will result in this type of fractal as well. Rows 9 (3^2), 25 (5^2), 27 (3^3), and 49 (7^2) all contain values that are multiples of the prime. So, they will make a sub-triangle that's also composed of only multiples of the prime. I'm sure these sub-triangles vary in size if you expand Pascal's Triangle out far enough, but I stopped at 49 because I don't have a program ready to list out the values of row 121 (I remember doing one as an assignment in C programming though).
Pattern for the excercise: 2: Every second number is not multiple of 2 3: Every third number is not multiple of 3 5: Every fifth number is not multiple of 5 7: Every seventh number is not multiple of 7 13: Every thirteenth number is not multiple of 13 ....... And so on
@@simonmultiverse6349 Are you okay? @123DJ321 is correct, the above is an observation and not a proof. They clearly do know what they are talking about. Do you have an issue with this?
Another interesting fact is that n and (n k) are never relatively prime. E.g. in row 15, all the terms (other than the beginning and ending 1s) are multiples of either 3 or 5.
That fact proves the original hypotheses, since if n is prime then the only way (n k) and n are not relatively prime is if (n k) = i*n, with i being a positive integer. It also proves another comment here which states that on rows that are powers of primes, all numbers on the row are also multiples of that prime (for example, on row 9 every number is a multiple of 3 since 9 = 3^2). The proof is similar, since n only has one prime factor then all (n k) must be multiples of that prime, otherwise (n k) would be relatively prime to n. Fun stuff.
Wish everyone can be as motivated and happy as this guy !!!! Also can someone pls tell me how to stay motivated ??? I am currently loosing my mind in here.
It's a pretty easy proof by contradiction (although it's more like a direct proof that it cannot be composite) by the fact that the factors of a composite must be smaller than the number itself
I think he gave the gist of a proof of "necessary" when he discussed row 8. Essentially, if p is not prime, then at least one of k! or (p-k)! must have a factor that is also a factor of p.
It not clear to me that the previous replies in this subthread really answered the actual question that Carvin0 was asking, but maybe I didn't understand them. I think Carvin0's question still stands. He's asking if the property can still hold for a row even when the second number in the row (that is, the next number after the initial 1) isn't prime. Assume throughout that 1
Some of my favorite facts about binomial coefficients the sinc function is sin(pi*x)/(pi*x) x ~= 0 1 when x == 0 The analytic continuation of 0 choose x is a sinc function you can construct the analytic continuation of any row on pascal's triangle with 1. the sum of n sinc functions 2. the product of n sinc functions 3. sin(pix) divided by a rising factorial polynomial (you have to l'hopital for all the integer values) There are lots of more. The actual formulas are a little more complicated There's some other really cools stuff about newton polynomials Binomial coefficients are used directly to find the divided differences, but they aren't the coefficients themselves but when you evaluate x choose n, you actually get the corresponding polynomial without even calculating the coefficients Also, inverse of a matrix of binomial coefficients is the same coefficients but with alternating signs. It's really the ultimate swiss army knife function. It's almost weird how much you can do with it.
This also means that (2^n - 2)/n will be a integer for prime numbers as every row in Pascal's triangle totals to 2^n and apart from the 1's, all other numbers are multiples of the prime number, so 2^n - 2 will be a multiple of prime number and (2^n-2)/n will be a integer I wrote a small code using this (numbers where (2^n-2)/n is integer) to find prime numbers from 1-1000 and also noticed some numbers 341, 561, 645 also came up which were not primes. Are there any other numbers for which all the numbers in the n'th row will be multiples of n which are not prime numbers. Heard that such numbers 341, 561, 645, etc are also called as Carmichael numbers
Respectfully, just a correction to why the green part is an integer. Mr. Woo did not provide enough proof for why n has to be an integer, nor did any of the comments here. Lets recap: What Mr. Woo is saying is that pCk = pn. Since pCk is an integer (this part is obvious), and p is an integer too (okay thats true...) then n is integer too (nope, that doesnt have to be the case). So where is the mistake? The mistake is not mentioning this will always work for when p is prime and with the help of the FTA. In our example, obviously we had p prime, but if we tried proving that separately, then it wouldnt be obvious. Take 6C3, 6C3= 20 , 6 is an integer, both 20 and 6 are integers, but is 20/6 an integer? NO. In conclusion, the complete proof would be mentioning that p is prime, FORCING the factorization of pn (which is an integer because pCk is an integer) via Fundamental Theorem of Arithmatic (FTA) to include p, therefore n is just the product of leftover primes, which is obviously an integer.
Isn't that exactly how he started? Pascal's triangle is formed by adding integers together. Thus every element must be an integer. What was missing, if anything, is to prove that nCr is always an integer (comes by definition of what it represents, but what was missing is that n!/(r!(n-r)!) is an integer), and that it is the formula for the r-th element of the n-th row of the triangle - they are likely proven elsewhere and those proofs are assumed for this proof. If p is prime then pCk = np and that is what he went on to prove. He pointed out that for n not prime nCr does not always equal kn. The proof for this was a counter example, eg 6C3 = 20 which is not a multiple of 6. Every nCr is a multiple of n for r=1 and r=n-1. He mentioned in passing that if n was not prime then it was possible that factors of r! or (n-r)! could multiply together to get n.
@@cigmorfil4101 The problem with his proof is that it was a circular argument. To show pCk is a multiple of p, then n must be an integer in pCk = pn. He said that because p is prime, then obviously n is an integer. You see what i mean? His argument is circular which is invalid.
Even though I dont understand maths higher than a 8th grade level, I am so fascinated by math videos. I need to sit down and properly get into it... one day haha
In the diagonal case it looks like for each prime p there are sequences of p-1 multiples of p, followed by a single number not a multiple of p. Repeat ad-infinitum down the diagonal. I have no idea if this holds for all p or the entire infinite diagonal for a given p.
it does. it's easy to see it if you make a large enough triangle and write on each cell the result of making mod the prime you choose (for example. if you choose 7 then write the value mod 7) I'm sure you will see a beautiful, recursive, pattern.
sum of row n in Pascal's triangle is 2^n so one should check n|2^n-2. For the diagonal row let P_r be the r^th diagonal. The partials sums of the P_r diagonal i=0 to i=k are as follows: sum P_3= k(k+1)(k+2)/6 sum P_4=k(k+1)(k+2)(k+3)/24 sum P_5 = k(k+1)(k+2)(k+3)/120 so sum P_r =(k-0)...(k+(r-1))/r!=(n+(r-1))!/(n-1)!*r!. (this can be proved by induction and a identity),so now ask yourself for each r what values of this sum -1 are divisible by r?
I did the hardest maths I could when I was at school in the 90's. I got good results on my VCE for maths (nothing under a B+, definitely some A's). And yet I feel I would fail this class if I took the exam. I can't help wondering if I've just forgotten heaps of stuff, or if the expectations are now much higher.
Which is crazy to me, because there have been news stories about Australian students falling behind much of the world academically. Maybe our northern neighbours are just setting a breakneck pace? Looking at things like cram schools, social hierarchy and expectations, etc. As well as their incredible populations
For the p!/k!(p-k!): If k = p-1, this cancels to: p/1 (since in this instance p!= pxk!) therefore is an integer (1) x p If k = p-2 this cancels to p(p-1)/2. As p is prime, hence odd (for p>2), p-1 is even so (p-1)/2 is integer If k = p-3 this cancels to p(p-1)(p-2)/2x3. We have already shown that p-1 is even. Additionally, as p does not divide by 3 (as p is prime and k > 0), then either p-1 or p-2 divides by 3. So (p-1)(p-2)/2x3 is an integer. If k = p-4 then we have p(p-1)(p-2)(p-3)/2x3x4. We have already shown that p-1 is even and one of p-1 or p-2 divides by 3. Additionally p-3 is even and one or other of p-1 or p-3 divides by 4 (since if we have 2 consecutive even numbers, one of them divides by 4). Therefore (p-1)(p-2)(p-3)/2x3x4 is integer. In the general situation k = p-z, we have p(p-1)(p-2)....(p+1-z)/z!, the coefficient of p on the top must divide by all numbers
Great lecture! Interesting to see how you use Notability. Just a minor remark. At 4.30, I think the condition 0 < k < p should be in the "if" condition before the "then" statement.
Singletrack Gray Codes are optimal for a prime number of bits because of this property, specifically they can contain 2**Np - 2 values for a Np bits when Np is prime (the number of observation points on the single track is prime). For instance, the resulting binary code for 5 bits would be 5 groups of 6, as follows (00001, 00011, 00111, 01111, 01011, 01001), (01000, 11000, 11001, 11011, 11010, 01010), (00010, 00110, 01110, 11110, 10110, 10010), (10000, 10001, 10011, 10111, 10101, 10100), (00100, 01100, 11100, 11101, 01101, 00101). You'll notice that each group is a rotation of any other group and no number should be repeated (unless I made a typo). Working with the singletrack gray codes led me to the same question (why does it only work for prime number - number of bits?). Gray Codes are sequences of binary numbers which only differ by one bit from number to the next (and never repeat a number, and are cyclic). Singletrack Gray Codes are useful for sensing the rotational position of a machine tool for instance. A Singletrack Gray Code for N bits of precision is a single bit binary circular sequence which achieves N bits of precision by having N sensors distributed evenly around the circle with each sensor providing one of the N bits precision by what it reads from the sequence. You can discover the bit sequence from the resulting binary code, above by grabbing one bit from each number of the sequence. So for instance taking the 0 bit: 111111001100000000011110000111. Taking the leading (16 bit): 000000011110000111111111001100. Notice both have 30 bits. Remembering this is circular, if you wrap the 0 bit around, you'll notice that at the join point, it's in the middle of a 9 bit run of 1's. The 16 bit also has a 9 bit run of 1's. So starting with this 9 bit run, the singletrack sequence is 9 1's, 2 0's, 2 1's, 9 0's, 4 1's, and 4 0's.
You can see row 4, 1 4 6 4, all multiples of 2. So yes, they do exist. This does not prove there are _always_ non-prime rows that have this property, only that there is at least 1.
Ahhh!. I did number theory 101 and scraped through. Its so obvious when somebody shows you but my brain just cant think at this level to come up with these solutions. That's why Im not a mathematician even though I might have a math's degree. I still enjoy watching though :)
P will only appear in the denominator when k=0 that is only the case with the last step : p!/ 0!(p-0)! which is one of the two numbers you took out in the first place.
The proof that the numbers are all multiples of p is trivial. When k isn't zero and isn't p, k! and (p-k)! only contain prime factors less than p. Nothing in those factorials cancels the p. Here's something that I found helpful. Declare (n choose -1) = 0 -- after all, how many sets of (-1) elements can one create? -- and (n choose n+1) = 0. I have found that using those numbers helps with deriving things using (n + 1 choose k) = (n choose k-1) + (n choose k).
How can I solve this The functions f and g are defined by F: x ---- remainder when x2 is divided by 7 And g:x ---- remainder when x2 is divided by 5 Show f(5) = g(3)
Since we are analyzing the numbers in Pascal's triangle, we know n*p is a whole number and we know p is a whole number. Hence n must be a whole number as well.
@@blazeottozean469 you can try to develop that fraction, but since we are talking about the pascal triangle we know, by definition, that the result will be a integer. (All pascal triangle numbers are the result of the addition of two whole numbers.) So n has to be a integer as well.
Is the converse true? Ie. composite rows are never all 0 mod the row #? Then you could prove that p is a prime iff all the p-1 non-unitary entries in the p:th row are 0 mod p. Edit: Doesn't work because of powers of primes. Silly me.
Pascal's triangle row can be expressed as binomial coefficient nCr (n choose r). The formula is n!/[r!(n-r)!]. Notice that for prime number n, the denominator part of the formula will never divide the factor n itself, so the product is guaranteed to result in multiple of n.
Does that mean that, if we color all the position which are NOT a multiple of the 2nd in their row, we will find a pattern which is by definition of a prime indescribable ? Now i'm curious to see that...
Those which are not multiples of the 2nd in their row are exactly those k (in n choose k) where a primefactor of n also appears in a factorization of k.
@@deedit4666 But you used the word "prime" which is NP, you'd need to calculate the entire triangle to be able to predict the next. There would be no recognizable pattern.
Number Theory: Yang Hui's Triangle Algebra: Al-Karaji's Triangle Probability: Pascal's Triangle In terms of the non-prime rows, are all entries multiples of at least one of the factors of the composite? Is there a pattern amongst them?
91 is not a multiple of 14. Even if you don't know the 14 times table, in order to get an odd number in multiplication, you have to multiply an Odd number by an Odd number. So, 91 cannot be a multiple of 14, ever. All multiples of 14 are even. :)
They are not multple of 14, however they are all divisible by 7 Umm I just realize that 3432 is NOT divisible by 7 (the exact middle number), also true for row 1 6 15 20 15 6 1 that they have factor of 3 yet except the middle one is undivisible by 3 🤔
The exercise delighted me enough that I had to go and come up with the proof (side note, while I didn't see it until today, this video released on my birthday, so wonderful birthday present). Though I must say, this has proven harder than I expected. I have the spirit of the proof. I thought it was complete, but as I was typing it up here, I realized there was something I had failed to account for. And while I think I can wave my hand at the fix, it's not fully rigorous. Which, as a mathematician, bothers me. Let me start giving what I had without trying to rewrite the entire thing (excuse the formality in the first part. My inner mathematician made me do it): First, I had to figure out the proper statement of the problem. So I wrote down the coefficients in (n choose k) form to observe what is "good" (appropriately a factor of the prime) and what's "bad". I found For p=2: (2 choose 1) is good, (3 choose 2) is bad, (4 choose 3) is good, (5 choose 4) is bad,... For p=3 (3 choose 1) is good, (4 choose 2) is good, (5 choose 3) is bad At this point, it becomes clear that the "bad" ones are when the k in (n choose k) is a multiple of p. Playing around with a formulation of the problem I came up with: Let p be prime and let k be an non-zero natural number. Consider the binomial coefficient N=(p+k choose k+1). Then N is not a multiple of p if and only if k+1 is a multiple of p Proof: First, let's observe that (p+k choose k+1) = (p+k)!/((k+1)!(p+k-(k+1))!) Now p+k-(k+1) p-1. Because p-1 < p and p is prime, p is not a factor of (p-1)! Consider k. As k is an integer, we can write k as np+m where n is a natural number and m is a natural number between 0 and p-1 Now consider N_1=(p+k)!=(p+np+m)!=((n+1)p+m)!. Observe, p, 2p, 3p,...,(n+1)p are factors of N_1.However, because m < p, (n+2)p is not a factor of N_1 Thus, p^(n+1) is a factor of N_1. We now consider (k+1)!, but we have 2 cases. First consider the case that m=p-1. Note that if m=p-1, then k+1=np+(p-1)+1=np+p=(n+1)p. Thus, k+1 is a multiple of p. In particular, N_2=(k+1)!=((n+1)p)! has factors p, 2p, ..., (n+1)p. Thus, p^(n+1) is a factor of N_2. Because p^(n+1) is a factor of both the numerator and denominator of (p+k)!/((k+1)!(p-1)!) and there are no more factors of p remaining, N is not a multiple of p. In the case that m is not p-1, then note that because 0 < m < p-1, then np < k+1 < (n+1)p (k+1 > np because m >=0 and k+1 < (n+1)p because m < p-1). Thus, N_2= (k+1)! has factors p, 2p,...,np, but (n+1)p is not a factor of N_2. Thus p^n is a factor of N_2. Thus, when we consider (p+k)!/((k+1)!(p-1)!), we can extract a factor of p^(n+1) from the numerator, and a factor p^n from the denominator (recall: p is not a factor of (p-1)!, so p^n is all the p's we have in the denominator), we have that N is a multiple of p. ... However, I realized after typing all of that that what I did did not account for all of the "p" factors which occur. For example, what if n=p? Then np=p^2 and we get an additional factor of p that previously had not been accounted for. If n=2p, then np=2p^2. Then in our list of sources of factors of p, we'd have p^2 and 2p^2 which gives us 2 unaccounted for factors of p. We could try to account for these factors of p in the same way we kept track of the factors of p originally, but things get even more complicated. What if n=p^2? Then np = p^3, which gives yet another previously unaccounted for factors of p. All of this comes to say that beyond the factors of p that we initially accounted for, we cannot determine the exact number of factors of p in the numerator and denominator. However, what we should be able to do is show that when k+1 is a multiple of p, we have the same number of factors of p in the numerator and denominator, while when k+1 is not a multiple of p, we have strictly less. That's fairly easy to hand wave: when k+1 is a multiple of p, our proof already showed that the list of sources of p-factors are identical in the numerator and denominator, so the number of p-factors must also match. Meanwhile when k+1 is not a multiple of p, the set of sources of p-factors in the denominator is contained in the set of sources of p-factors in the numerator, so while we may not be able to determine exactly how many more p-factors the numerator has, we can guarantee that it has strictly more. ... I think this whole thing took me 2 hours to work out and write up. I definitely intended to get some grading done tonight, but I guess other things got in the way
really intrigued by the title. i came up with a solution on the exercise. show: (np-1)C([n-1]p) is not divisible by p, for any n>1, such that n is any integer and p is any prime. (np-1)C([n-1]p) is simply the combination notation for any term in the p diagonal that is not divisible by p. i tried it for p=2, 3, 5 and they all seem to obey the property. to justify, we need to prove that p does not appear in either the numerator (as a factor) or denominator (as a divisor) of the expanded combination notation. we expand the notation, (np-1)C([n-1]p) = (np-1)!/[(np-p)!·(p-1)!] = [(np-1)...(np-p+1)·(np-p)!]/[(np-p)!·(p-1)!] = (np-1)...(np-p+1)/(p-1)! p is not a factor in (p-1)! bc p>(p-1). likewise, none of the factors from (np-1)...(np-p+1) has the factor of p; the nearest factors to them are np and (n-1)p or np-p. that being said, p is neither a factor or divisor of the term (np-1)C([n-1]p). consequently, p does not divide (np-1)C([n-1]p) hence the pattern.
Welp, your formulation of the problem is much better than how I formulated it, and I think my formulation conned me into an inelegant proof that I had to wave my hands at times just to avoid some notational tedium. That said, my proof did also prove the other half (that the other numbers on the diagonal are multiples of p), so there's that
@@ALeafOnTheWind42 that's great. i also made a proof that generalizes the entire situation as well (including non-interest terms) and it follows just the same manner as the one i previously commented. we can represent any prime diagonal sequence dp using the notation a(n) = (p+n)C(n+1), or the nth term of the sequence with n=0 as the first term. with this, we can find any term in any prime diagonal. the term of interest is the (kp-1)th term of a diagonal in this situation, with kp the k multiple of p, or simply n= kp-1. the problem now is show: (p+n)C(n+1)|p is false when n= kp-1 in similar fashion as the proof i mentioned above, we also need to show that p is not in either the numerator or the denominator. we evaluate the notation at n= kp-1 (p+n)C(n+1) = (p+[kp-1])C([kp-1]+1) = (kp+p-1)C(kp) = (kp+p-1)!/[(kp)!·([kp+p-1]-[kp])! = (kp+p-1)!/[(kp)!·(p-1)!] = (kp+[p-1])...(kp+1)·(kp)!/[(kp)!·(p-1)!] = (kp+[p-1])...(kp+1)/(p-1)! in the last line, p is not a factor in (p-1)! since p>(p-1), and p is not a factor in (kp+[p-1])...(kp+1) either since the nearest multiple of p are kp and kp+p or (k+1)p. therefore p is neither in the numerator nor the denominator of the expansion. consequently, (p+n)C(n+1)|p is false when n= kp-1. to prove the other terms, we adjust n. if n>kp-1 then the numerator has kp-p or (k-1)p as a factor, if n
@@snsnni Yeah, that's how I formulated it as well (different variable names - I swapped n and k) but otherwise the same. My problem was instead of actually canceling the terms before determining the number of times p appears as a factor in the numerator and denominator, I tried to count them outright. At first it didn't seem so bad. The only numbers where we could get a factor of p (in your notation) would be p, 2p,...(k+1)p (in the numerator) and at first I was thinking that meant the numerator would have a factor of p^(k+1) and no higher power of p. In the case where n+1 is a multiple of p, the same holds in the denominator. In the case where n+1 is not a multiple of p, then the numbers that contribute a factor of p only go up to kp. It's a strict subset of factors of p, so there's not enough to cancel all of the factors of p in the numerator so we have to have a multiple of p. I was happy with this until I realized that I didn't actually account for all of the factors of p. After all, what if k is large enough that p² appears? That's a factor of p that I didn't account for previously. I eventually realized that it doesn't matter because at the heart of it, in the n+1 is a multiple of p case, the exact same numbers contribute p in the numerator and denominator, so they cancel out, while otherwise the denominator has a strict subset. But I was trying to make my proof formal, and was running into notational hell
Most practical application of mathematics came from mathematicians answering seemingly pointless yet intriguing questions, and another scientist/physicist/engineer/etc. discovered that the solution to some of these "seemingly pointless questions" are exactly the missing piece of the puzzle to their grand discovery. So no, we're not gonna give it a rest.
Another interesting thing is when you take the "middle" row (1-1-2-3-6-10-20 etc...): To get the next number, you will either have to multiply by 2 or by a fraction: To get from an odd row to an even row, the factor will always be 2 (1*2=2 ; 3*2=6 ; 10*2=20 etc...) and to get from an even row to an odd row the factors will always be fractions in a specific order: The first factor is 1/1, then 3/2, then 5/3, 7/4, etc... What I find interesting is that the fractions are getting closer to 2 over time, however they will never reach 2 I hope that you could understand what I'm saying and I apologize for any mistakes , I'm not a native speaker :-P
@@hiredfiredtired that is not a definition of k. That is just a consequence of the fact that he is using k in p choose k. He could have left that part out and the original expression would still be true since 5 choose 6 or 5 choose -3 is illogical. What he didn't explain is what k is or why he is choosing k from p in the first place.
All that was true, but painfully slow. So many words for something so intuitively true. You can literally write the formula for the binomial coefficent (p k) and to point the obvious fact that always will be divisible by p, when p is prime number. What is the big deal here?
Mathematics is nothing more than symbolic representation of measured values in some kind of quantitative event, applicable to any concept whether it is real or not. Two angels plus two angels equal four angels; the math works but does not prove angels exist. Mathematics is not some kind of secret language of the universe; it is just quantitation of values. There are only four quantitative operations: plus, minus, times, and division; well, only two really; plus, and minus. You can find all kinds of patterns such as prime numbers, but they have no actual meaning other than inadvertent patterns. Those who make more of mathematics than that, have conceptual delusions, the stuff that cults are made of…
"By the way, Sean, your camera's on."
Me: 😳
Hahahahaha
Bruh ngl i got terrified
that actually scared the hell out of me
Now I'm curious about what Shaun was doing.
lol me too
I like how youve given the students time to have a go, rather than answer it straight away
Interestingly this also applies to rows that are powers of primes as well. every power of 2 row consists only of even numbers, every power of 3 row consists only of multiples of 3, and so on for all primes.
Modification of the same proof applies. Only factors of p^n are powers of p. This time, however, p is not greater than k. However, notice that you can’t cancel out ALL the instances of p in the numerator, at least one must remain, ergo, p is a divisor of all the other numbers in that row, excluding the 1s.
Same goes for any row in the triangle actually. Every number on the nth row shares at least one common prime factor with n.
Holy crap, i got the biggest fright of my life when he said, 'by the way Sean, Your camera is still on...' i replayed the video so many times to check if i was hearing my name properly
then , if you know newton's binomial theorem, the sum of all the elements of a row is 2^n where n is the row you are looking. So, if p is prime, if we sustract the 1+1, then p divides 2^p - 2 = 2(2^(p-1)-1), if p not 2 you can have some fermat's little theorem experience jajaja.
Nice 👍
Came here to say this :) Nice!
(I may but be missing something here, please correct me if I'm wrong).
It seems to me that, if p is prime, Fermat‘s little theorem will help us prove that the *sum* of terms is a multiple of p. Don't we need to prove *each term in that sum* is a multiple of p? Perhaps some more steps are required here?
really important stuff, and way better explanations than any of the online classes ive had this year :3
I hardly follow the math stuff in here but his enthusiasm alone makes me want to listen to some more !
Great teacher ! Great triangle 00
Just do the binomial expansion. For row n, n will be in every term and since n is prime it can't be divided out by the components of the factorial terms underneath (until you get to the last term which has n! on the bottom, but this term is 1, so obviously it divides out at that point). So every term has n as a factor. Job done.
You captured my curiosity, and so I clicked!
Same
Welcome to the club
I will admit to being a math moron, my degree is in History and Political Science. This has fascinated me, thank you. You have a new follower and sparked an interest in math in a 54 year old grandfather.
for those that wish to find why the diagonals are also multiple of the primes "with exceptions" I would advice to choose any prime (for example 7) and replace all numbers on the triangle by their value mod the prime you had choosen. the pattern that appears is quite simple, simetric and beautiful (like everything made with proper maths)
note: you may need to make quite a triangle to notice the pattern. about the prime you choose squared.
Disclaimer! I'm no mathematician, but:
I'm guessing it is related to the fact that -- given we already proved that the rows of primes are all multiples of that prime -- the (inverted) triangle underneath that row will always be a multiple of that row's prime (assuming we understand Pascals Triangle comes from the addition to the to numbers above it), and any addition of two multiples of a number will always be a multiple of that number. The second part is harder for me to explain, but I can guess it is also related to the same proof in this video. Each row that is a multiple of a prime will contain a set of multiples of that prime -- I don't know how to prove it, but I'm guessing has to be related to that proof because it's just that same proof but it's just a multiple of that proof (?) -- that multiple comes from multiplying by "a" (e.g. p=7, a=2... so the new row 2p, or 14). I suppose we actually expand the proof, so that 0
Conceptually got it since the clue was a real tell and that's made it an excellent conceptual exercise for me. Thanks!
There is a one-line combinatorial proof: (p choose n)(n choose 1) = (p choose 1)(p-1 choose n-1). This also proves a more general result that any two numbers from the same row are always not co-prime excluding the 1s.
No one cares that you think this is trivial
@@anshumanagrawal346 No offense here but I am not saying it is trivial but just giving an elegant alternative proof. If you mean the proof of the more general result is not trivial, you need to replace the 1 with any number r < n and compare (p choose n) and (p choose r).
@@cr1216 oh ok, I'm sorry, I thought you were one of those arrogant fools who go around saying "this is too easy" on math videos
you mean this: (p choose n)(n choose 1)(1/n)=pN (N natural no.) if n and p do not have common factors
I found that the fact that previous row consists just 1 and (-1) mod(prime) for any row prime in natural power is cool too. I mean it can be easily shown, like by using C(n+1, k+1) =C(n, k) +C(n, k+1) and 1 on every C(n, 0). 0=1+-1, 0=-1+1... Also by (-1) mod prime I mean prime-1, but using -1 is easier sometimes, and for 2 it obviously same thing +1 and -1, they'll give 0 in sum in any pair
You're awesome! Great class!
Second question.
*Claim:* Not just the diagonals have this property, but every triangle for which the segment of such a diagonal forms the left edge.
*Proof:*
Let n = m*p, and 0 < k < p (we're mirroring stuff here). Then the quotient q := n!/(n-k)! has a factor n=m*p, and since k
As for the diagonal part, we started with the row of multiples of p (including the prime itself). Due to the construction of the triangle, we're just adding a bunch of multiples of p together to make a sub-triangle (that's upside-down) composed of the prime row + the diagonal twice, which obviously gives more multiples of p.
The gap appears because we've introduced a 1 from the right side of the triangle in p's row. This carries down the triangle, by construction, to give a diagonal with values of (a multiple of p) + 1, a "gap" diagonal.
Immediately after the "gap" though, we have another diagonal composed of another 1. Similarly, this 1 will be carried down the triangle to the term in question in the p diagonal. However, there's p - 2 values between this term and the 1's diagonal which is composed of the "gap" 1 being over counted. So, the term will contain two 1's (from the "gap" and this term's diagonal) and p - 2 1's (over counting the "gap" 1, the distance between the p diagonal and 1 diagonal), which add to a p amount of 1's, giving a multiple of p! From there, the pattern continues.
I think I may have skipped to the conclusion in the end there, but you mentioned the fractal that can be made with the multiples of 3. After looking at the multiples of 5 and 7 when thinking about this diagonal problem, I think all of the primes will result in this type of fractal as well. Rows 9 (3^2), 25 (5^2), 27 (3^3), and 49 (7^2) all contain values that are multiples of the prime. So, they will make a sub-triangle that's also composed of only multiples of the prime. I'm sure these sub-triangles vary in size if you expand Pascal's Triangle out far enough, but I stopped at 49 because I don't have a program ready to list out the values of row 121 (I remember doing one as an assignment in C programming though).
This is an excellent video!!! Well done sir!!!
This is an interesting and informative video, thank you :-)
Can't that result be even stated stronger (that is without really extending the proof)? I.e. all n over k with 0
Pattern for the excercise:
2: Every second number is not multiple of 2
3: Every third number is not multiple of 3
5: Every fifth number is not multiple of 5
7: Every seventh number is not multiple of 7
13: Every thirteenth number is not multiple of 13
.......
And so on
I can prove it by examining a row and looking at the ratio between one term and the adjacent term.
That's just an observation with no proof of it continuing forever.
@@DeJay7 Blah blah blah bl bl bl blaaaa hahaha hahaha hahaha haha haha hahah huuuaaarrrrrghghgh BLAH BLAH Do you know what you're talking about?
No. Clearly, you DON'T know what you're talking about.
@@simonmultiverse6349 Are you okay? @123DJ321 is correct, the above is an observation and not a proof. They clearly do know what they are talking about. Do you have an issue with this?
I like the 3rd diagonal being all triangle numbers... :)
The nth triangle number, the sum of all integers from 1 to n, = n(n+1)/2.
even when i am using artist pen to write and draw during online presentation i couldn't be so neat. Nice!
Very nice. Thaks Eddie
Another interesting fact is that n and (n k) are never relatively prime. E.g. in row 15, all the terms (other than the beginning and ending 1s) are multiples of either 3 or 5.
That fact proves the original hypotheses, since if n is prime then the only way (n k) and n are not relatively prime is if (n k) = i*n, with i being a positive integer.
It also proves another comment here which states that on rows that are powers of primes, all numbers on the row are also multiples of that prime (for example, on row 9 every number is a multiple of 3 since 9 = 3^2). The proof is similar, since n only has one prime factor then all (n k) must be multiples of that prime, otherwise (n k) would be relatively prime to n. Fun stuff.
Wish everyone can be as motivated and happy as this guy !!!! Also can someone pls tell me how to stay motivated ??? I am currently loosing my mind in here.
You proved "sufficient". I'd like to see "necessary" as well as sufficient.
What do you mean?
It's a pretty easy proof by contradiction (although it's more like a direct proof that it cannot be composite) by the fact that the factors of a composite must be smaller than the number itself
It has proven necessary too, what are you saying?
I think he gave the gist of a proof of "necessary" when he discussed row 8. Essentially, if p is not prime, then at least one of k! or (p-k)! must have a factor that is also a factor of p.
It not clear to me that the previous replies in this subthread really answered the actual question that Carvin0 was asking, but maybe I didn't understand them. I think Carvin0's question still stands. He's asking if the property can still hold for a row even when the second number in the row (that is, the next number after the initial 1) isn't prime.
Assume throughout that 1
The fundamental theorem of arithmetic strikes again, and with even more beautiful results.
Amazing!
Some of my favorite facts about binomial coefficients
the sinc function is
sin(pi*x)/(pi*x) x ~= 0
1 when x == 0
The analytic continuation of 0 choose x is a sinc function
you can construct the analytic continuation of any row on pascal's triangle with
1. the sum of n sinc functions
2. the product of n sinc functions
3. sin(pix) divided by a rising factorial polynomial (you have to l'hopital for all the integer values)
There are lots of more. The actual formulas are a little more complicated
There's some other really cools stuff about newton polynomials
Binomial coefficients are used directly to find the divided differences, but they aren't the coefficients themselves
but when you evaluate x choose n, you actually get the corresponding polynomial without even calculating the coefficients
Also, inverse of a matrix of binomial coefficients is the same coefficients but with alternating signs.
It's really the ultimate swiss army knife function. It's almost weird how much you can do with it.
This also means that (2^n - 2)/n will be a integer for prime numbers as every row in Pascal's triangle totals to 2^n and apart from the 1's, all other numbers are multiples of the prime number, so 2^n - 2 will be a multiple of prime number and (2^n-2)/n will be a integer
I wrote a small code using this (numbers where (2^n-2)/n is integer) to find prime numbers from 1-1000 and also noticed some numbers 341, 561, 645 also came up which were not primes. Are there any other numbers for which all the numbers in the n'th row will be multiples of n which are not prime numbers. Heard that such numbers 341, 561, 645, etc are also called as Carmichael numbers
Interesting and elegant.
Respectfully, just a correction to why the green part is an integer.
Mr. Woo did not provide enough proof for why n has to be an integer, nor did any of the comments here. Lets recap: What Mr. Woo is saying is that pCk = pn. Since pCk is an integer (this part is obvious), and p is an integer too (okay thats true...) then n is integer too (nope, that doesnt have to be the case). So where is the mistake? The mistake is not mentioning this will always work for when p is prime and with the help of the FTA. In our example, obviously we had p prime, but if we tried proving that separately, then it wouldnt be obvious.
Take 6C3, 6C3= 20 , 6 is an integer, both 20 and 6 are integers, but is 20/6 an integer? NO.
In conclusion, the complete proof would be mentioning that p is prime, FORCING the factorization of pn (which is an integer because pCk is an integer) via Fundamental Theorem of Arithmatic (FTA) to include p, therefore n is just the product of leftover primes, which is obviously an integer.
Isn't that exactly how he started?
Pascal's triangle is formed by adding integers together. Thus every element must be an integer. What was missing, if anything, is to prove that nCr is always an integer (comes by definition of what it represents, but what was missing is that n!/(r!(n-r)!) is an integer), and that it is the formula for the r-th element of the n-th row of the triangle - they are likely proven elsewhere and those proofs are assumed for this proof.
If p is prime then pCk = np and that is what he went on to prove.
He pointed out that for n not prime nCr does not always equal kn. The proof for this was a counter example, eg 6C3 = 20 which is not a multiple of 6. Every nCr is a multiple of n for r=1 and r=n-1. He mentioned in passing that if n was not prime then it was possible that factors of r! or (n-r)! could multiply together to get n.
@@cigmorfil4101 The problem with his proof is that it was a circular argument. To show pCk is a multiple of p, then n must be an integer in pCk = pn. He said that because p is prime, then obviously n is an integer. You see what i mean? His argument is circular which is invalid.
The line after a prime line is also divisible by the prime before it except the the second term.
Nice observation.
Even though I dont understand maths higher than a 8th grade level, I am so fascinated by math videos. I need to sit down and properly get into it... one day haha
If you understand this video, you actually understand some stuff on number theory on grad level :)
This online class seems awesome, btw
@@gabriellasso8808 thank you, that's quite a compliment 😊
In the diagonal case it looks like for each prime p there are sequences of p-1 multiples of p, followed by a single number not a multiple of p. Repeat ad-infinitum down the diagonal. I have no idea if this holds for all p or the entire infinite diagonal for a given p.
it does. it's easy to see it if you make a large enough triangle and write on each cell the result of making mod the prime you choose (for example. if you choose 7 then write the value mod 7)
I'm sure you will see a beautiful, recursive, pattern.
sum of row n in Pascal's triangle is 2^n so one should check n|2^n-2.
For the diagonal row let P_r be the r^th diagonal. The partials sums of the P_r diagonal i=0 to i=k are as follows:
sum P_3= k(k+1)(k+2)/6
sum P_4=k(k+1)(k+2)(k+3)/24
sum P_5 = k(k+1)(k+2)(k+3)/120
so sum P_r =(k-0)...(k+(r-1))/r!=(n+(r-1))!/(n-1)!*r!.
(this can be proved by induction and a identity),so now ask yourself for each r what values of this sum -1 are divisible by r?
Very Interesting... ;)
I did the hardest maths I could when I was at school in the 90's. I got good results on my VCE for maths (nothing under a B+, definitely some A's). And yet I feel I would fail this class if I took the exam.
I can't help wondering if I've just forgotten heaps of stuff, or if the expectations are now much higher.
Which is crazy to me, because there have been news stories about Australian students falling behind much of the world academically.
Maybe our northern neighbours are just setting a breakneck pace? Looking at things like cram schools, social hierarchy and expectations, etc. As well as their incredible populations
Because k
For the p!/k!(p-k!):
If k = p-1, this cancels to: p/1 (since in this instance p!= pxk!) therefore is an integer (1) x p
If k = p-2 this cancels to p(p-1)/2. As p is prime, hence odd (for p>2), p-1 is even so (p-1)/2 is integer
If k = p-3 this cancels to p(p-1)(p-2)/2x3. We have already shown that p-1 is even. Additionally, as p does not divide by 3 (as p is prime and k > 0), then either p-1 or p-2 divides by 3. So (p-1)(p-2)/2x3 is an integer.
If k = p-4 then we have p(p-1)(p-2)(p-3)/2x3x4. We have already shown that p-1 is even and one of p-1 or p-2 divides by 3. Additionally p-3 is even and one or other of p-1 or p-3 divides by 4 (since if we have 2 consecutive even numbers, one of them divides by 4). Therefore (p-1)(p-2)(p-3)/2x3x4 is integer.
In the general situation k = p-z, we have p(p-1)(p-2)....(p+1-z)/z!, the coefficient of p on the top must divide by all numbers
Thank for talking about my triangle
There is something i realized if you look at row 6,
1 6 15 20 15 6 1
The numbers below 6 and 15 would be 6 + 15= 2x3 + 3x5 = 3(2+5)= 3x7
Great lecture! Interesting to see how you use Notability. Just a minor remark. At 4.30, I think the condition 0 < k < p should be in the "if" condition before the "then" statement.
Singletrack Gray Codes are optimal for a prime number of bits because of this property, specifically they can contain 2**Np - 2 values for a Np bits when Np is prime (the number of observation points on the single track is prime). For instance, the resulting binary code for 5 bits would be 5 groups of 6, as follows (00001, 00011, 00111, 01111, 01011, 01001), (01000, 11000, 11001, 11011, 11010, 01010), (00010, 00110, 01110, 11110, 10110, 10010), (10000, 10001, 10011, 10111, 10101, 10100), (00100, 01100, 11100, 11101, 01101, 00101). You'll notice that each group is a rotation of any other group and no number should be repeated (unless I made a typo). Working with the singletrack gray codes led me to the same question (why does it only work for prime number - number of bits?). Gray Codes are sequences of binary numbers which only differ by one bit from number to the next (and never repeat a number, and are cyclic). Singletrack Gray Codes are useful for sensing the rotational position of a machine tool for instance. A Singletrack Gray Code for N bits of precision is a single bit binary circular sequence which achieves N bits of precision by having N sensors distributed evenly around the circle with each sensor providing one of the N bits precision by what it reads from the sequence. You can discover the bit sequence from the resulting binary code, above by grabbing one bit from each number of the sequence. So for instance taking the 0 bit: 111111001100000000011110000111. Taking the leading (16 bit): 000000011110000111111111001100. Notice both have 30 bits. Remembering this is circular, if you wrap the 0 bit around, you'll notice that at the join point, it's in the middle of a 9 bit run of 1's. The 16 bit also has a 9 bit run of 1's. So starting with this 9 bit run, the singletrack sequence is 9 1's, 2 0's, 2 1's, 9 0's, 4 1's, and 4 0's.
Is there any non-prime row whose elements (excluding its ones) are all multiples?
Yes, there are some of odd numbers. It's home work.
You can see row 4, 1 4 6 4, all multiples of 2.
So yes, they do exist. This does not prove there are _always_ non-prime rows that have this property, only that there is at least 1.
Very cool
Now, are these properties characteristic for primes, i.e. do they never apply to non-primes?
See Anthony Morris! Composite primes that make the prime number cross ! Nice 👌
The part highlighted in green is not a number inside the Pascal triangle. Why must it be an integer?
This video is related to AKS PRIMALITY TEST for prime numbers.
Ahhh!. I did number theory 101 and scraped through. Its so obvious when somebody shows you but my brain just cant think at this level to come up with these solutions. That's why Im not a mathematician even though I might have a math's degree. I still enjoy watching though :)
P will only appear in the denominator when k=0 that is only the case with the last step : p!/ 0!(p-0)! which is one of the two numbers you took out in the first place.
The proof that the numbers are all multiples of p is trivial. When k isn't zero and isn't p, k! and (p-k)! only contain prime factors less than p. Nothing in those factorials cancels the p.
Here's something that I found helpful. Declare (n choose -1) = 0 -- after all, how many sets of (-1) elements can one create? -- and (n choose n+1) = 0. I have found that using those numbers helps with deriving things using (n + 1 choose k) = (n choose k-1) + (n choose k).
I don't understand why n is a whole number. Why can't n be a fraction with p as the denominator so that pn is a whole number and not a multiple of p.
Yes, you can have 11 chose 20, it is defined to be 0 :)
I think it's just undefined in most settings
No, it's undefined since you'll have a negative number inside the factorial.
what classroom software is this?
well that property is how Fermat figured if n is prime, and an integer a, a to the nth minus a is divisible by that prime
Wow, really?
How can I solve this
The functions f and g are defined by
F: x ---- remainder when x2 is divided by 7
And g:x ---- remainder when x2 is divided by 5
Show f(5) = g(3)
Which part are you stuck at? I guess there's something you don't understand about the function definitions?
Could someone explain that why the highlighted green part in the last is a whole number?
Since we are analyzing the numbers in Pascal's triangle, we know n*p is a whole number and we know p is a whole number. Hence n must be a whole number as well.
@@yyanji Exactly what I don't understand, why those numbers in Pascal's triangle is np? Or are they came from just calculation?
@@blazeottozean469 you can try to develop that fraction, but since we are talking about the pascal triangle we know, by definition, that the result will be a integer. (All pascal triangle numbers are the result of the addition of two whole numbers.)
So n has to be a integer as well.
Because If you divide p-1! by k!(p-k)! it always will return a whole number. (So n)
@@JeroenElsen Sorry for being dumb, but that is exactly what I don't understand why it is.
rip sean
I've never seen a student who actually discusses in breakouts 😂😂 You must have very enthusiastic students!
What is really interesting, does it work both ways? Are the prime rows the ONLY rows, where all numbers are multiples of the row number?
Is the converse true? Ie. composite rows are never all 0 mod the row #? Then you could prove that p is a prime iff all the p-1 non-unitary entries in the p:th row are 0 mod p.
Edit: Doesn't work because of powers of primes. Silly me.
This seems like a simple enough proof. That said, I'm done with my bachelor's degree and this might be a class for high school students.
1:54 It took me a second but I was surprised to see it
I still don't understand the reason why row with Prime number has its multiples. Can anyone explain.
Pascal's triangle row can be expressed as binomial coefficient nCr (n choose r). The formula is n!/[r!(n-r)!].
Notice that for prime number n, the denominator part of the formula will never divide the factor n itself, so the product is guaranteed to result in multiple of n.
he made another video on this.
Nice
Does that mean that, if we color all the position which are NOT a multiple of the 2nd in their row, we will find a pattern which is by definition of a prime indescribable ? Now i'm curious to see that...
Those which are not multiples of the 2nd in their row are exactly those k (in n choose k) where a primefactor of n also appears in a factorization of k.
@@deedit4666 But you used the word "prime" which is NP, you'd need to calculate the entire triangle to be able to predict the next. There would be no recognizable pattern.
@@hurktang yes
Number Theory: Yang Hui's Triangle
Algebra: Al-Karaji's Triangle
Probability: Pascal's Triangle
In terms of the non-prime rows, are all entries multiples of at least one of the factors of the composite?
Is there a pattern amongst them?
For the diagonals shown, for prime p, every pth term is not a factor of that prime.
I wouldn't hate school if my teachers taught like this
Are not all of the non-trivial values in row 14 multiples of 14?
91 is not a multiple of 14. Even if you don't know the 14 times table, in order to get an odd number in multiplication, you have to multiply an Odd number by an Odd number. So, 91 cannot be a multiple of 14, ever. All multiples of 14 are even. :)
They are not multple of 14, however they are all divisible by 7
Umm I just realize that 3432 is NOT divisible by 7 (the exact middle number), also true for row 1 6 15 20 15 6 1 that they have factor of 3 yet except the middle one is undivisible by 3 🤔
I proved it before your explanation of the proof. ^_^
Why is this true only for prime rows?
But if you add up "enough" integers some ppl think you get -1/12
Ok, 8:52 in... the question: Because `p` is prime and so `k` will never be a factor in `p`.
A consequence is Freshman's dream: a^p+ b^p = (a+b)^p (mod p)
The exercise delighted me enough that I had to go and come up with the proof (side note, while I didn't see it until today, this video released on my birthday, so wonderful birthday present). Though I must say, this has proven harder than I expected. I have the spirit of the proof. I thought it was complete, but as I was typing it up here, I realized there was something I had failed to account for. And while I think I can wave my hand at the fix, it's not fully rigorous. Which, as a mathematician, bothers me. Let me start giving what I had without trying to rewrite the entire thing (excuse the formality in the first part. My inner mathematician made me do it):
First, I had to figure out the proper statement of the problem. So I wrote down the coefficients in (n choose k) form to observe what is "good" (appropriately a factor of the prime) and what's "bad". I found
For p=2: (2 choose 1) is good, (3 choose 2) is bad, (4 choose 3) is good, (5 choose 4) is bad,...
For p=3 (3 choose 1) is good, (4 choose 2) is good, (5 choose 3) is bad
At this point, it becomes clear that the "bad" ones are when the k in (n choose k) is a multiple of p. Playing around with a formulation of the problem I came up with:
Let p be prime and let k be an non-zero natural number. Consider the binomial coefficient N=(p+k choose k+1). Then N is not a multiple of p if and only if k+1 is a multiple of p
Proof: First, let's observe that (p+k choose k+1) = (p+k)!/((k+1)!(p+k-(k+1))!) Now p+k-(k+1) p-1. Because p-1 < p and p is prime, p is not a factor of (p-1)!
Consider k. As k is an integer, we can write k as np+m where n is a natural number and m is a natural number between 0 and p-1
Now consider N_1=(p+k)!=(p+np+m)!=((n+1)p+m)!. Observe, p, 2p, 3p,...,(n+1)p are factors of N_1.However, because m < p, (n+2)p is not a factor of N_1 Thus, p^(n+1) is a factor of N_1.
We now consider (k+1)!, but we have 2 cases. First consider the case that m=p-1. Note that if m=p-1, then k+1=np+(p-1)+1=np+p=(n+1)p. Thus, k+1 is a multiple of p. In particular, N_2=(k+1)!=((n+1)p)! has factors p, 2p, ..., (n+1)p. Thus, p^(n+1) is a factor of N_2. Because p^(n+1) is a factor of both the numerator and denominator of (p+k)!/((k+1)!(p-1)!) and there are no more factors of p remaining, N is not a multiple of p.
In the case that m is not p-1, then note that because 0 < m < p-1, then np < k+1 < (n+1)p (k+1 > np because m >=0 and k+1 < (n+1)p because m < p-1). Thus, N_2= (k+1)! has factors p, 2p,...,np, but (n+1)p is not a factor of N_2. Thus p^n is a factor of N_2. Thus, when we consider (p+k)!/((k+1)!(p-1)!), we can extract a factor of p^(n+1) from the numerator, and a factor p^n from the denominator (recall: p is not a factor of (p-1)!, so p^n is all the p's we have in the denominator), we have that N is a multiple of p.
... However, I realized after typing all of that that what I did did not account for all of the "p" factors which occur. For example, what if n=p? Then np=p^2 and we get an additional factor of p that previously had not been accounted for. If n=2p, then np=2p^2. Then in our list of sources of factors of p, we'd have p^2 and 2p^2 which gives us 2 unaccounted for factors of p. We could try to account for these factors of p in the same way we kept track of the factors of p originally, but things get even more complicated. What if n=p^2? Then np = p^3, which gives yet another previously unaccounted for factors of p.
All of this comes to say that beyond the factors of p that we initially accounted for, we cannot determine the exact number of factors of p in the numerator and denominator. However, what we should be able to do is show that when k+1 is a multiple of p, we have the same number of factors of p in the numerator and denominator, while when k+1 is not a multiple of p, we have strictly less. That's fairly easy to hand wave: when k+1 is a multiple of p, our proof already showed that the list of sources of p-factors are identical in the numerator and denominator, so the number of p-factors must also match. Meanwhile when k+1 is not a multiple of p, the set of sources of p-factors in the denominator is contained in the set of sources of p-factors in the numerator, so while we may not be able to determine exactly how many more p-factors the numerator has, we can guarantee that it has strictly more.
... I think this whole thing took me 2 hours to work out and write up. I definitely intended to get some grading done tonight, but I guess other things got in the way
The 1's are actually prime/prime or prime^0.
Sure thing. But they need to be excluded for the rule to work as they are in every row which is included in the rule
It appears to follow for all odd numbers
No, 84 is in the row for 9, the first possible exception (9 is the first non-prime odd number).
really intrigued by the title. i came up with a solution on the exercise.
show: (np-1)C([n-1]p) is not divisible by p, for any n>1, such that n is any integer and p is any prime.
(np-1)C([n-1]p) is simply the combination notation for any term in the p diagonal that is not divisible by p.
i tried it for p=2, 3, 5 and they all seem to obey the property.
to justify, we need to prove that p does not appear in either the numerator (as a factor) or denominator (as a divisor) of the expanded combination notation.
we expand the notation,
(np-1)C([n-1]p)
= (np-1)!/[(np-p)!·(p-1)!]
= [(np-1)...(np-p+1)·(np-p)!]/[(np-p)!·(p-1)!]
= (np-1)...(np-p+1)/(p-1)!
p is not a factor in (p-1)! bc p>(p-1). likewise, none of the factors from (np-1)...(np-p+1) has the factor of p; the nearest factors to them are np and (n-1)p or np-p.
that being said, p is neither a factor or divisor of the term (np-1)C([n-1]p). consequently, p does not divide (np-1)C([n-1]p) hence the pattern.
Welp, your formulation of the problem is much better than how I formulated it, and I think my formulation conned me into an inelegant proof that I had to wave my hands at times just to avoid some notational tedium. That said, my proof did also prove the other half (that the other numbers on the diagonal are multiples of p), so there's that
@@ALeafOnTheWind42 that's great. i also made a proof that generalizes the entire situation as well (including non-interest terms) and it follows just the same manner as the one i previously commented.
we can represent any prime diagonal sequence dp using the notation
a(n) = (p+n)C(n+1), or the nth term of the sequence with n=0 as the first term. with this, we can find any term in any prime diagonal.
the term of interest is the (kp-1)th term of a diagonal in this situation, with kp the k multiple of p, or simply n= kp-1.
the problem now is show: (p+n)C(n+1)|p is false when n= kp-1
in similar fashion as the proof i mentioned above, we also need to show that p is not in either the numerator or the denominator.
we evaluate the notation at n= kp-1
(p+n)C(n+1)
= (p+[kp-1])C([kp-1]+1)
= (kp+p-1)C(kp)
= (kp+p-1)!/[(kp)!·([kp+p-1]-[kp])!
= (kp+p-1)!/[(kp)!·(p-1)!]
= (kp+[p-1])...(kp+1)·(kp)!/[(kp)!·(p-1)!]
= (kp+[p-1])...(kp+1)/(p-1)!
in the last line, p is not a factor in (p-1)! since p>(p-1), and p is not a factor in (kp+[p-1])...(kp+1) either since the nearest multiple of p are kp and kp+p or (k+1)p. therefore p is neither in the numerator nor the denominator of the expansion. consequently, (p+n)C(n+1)|p is false when n= kp-1.
to prove the other terms, we adjust n. if n>kp-1 then the numerator has kp-p or (k-1)p as a factor, if n
@@snsnni Yeah, that's how I formulated it as well (different variable names - I swapped n and k) but otherwise the same. My problem was instead of actually canceling the terms before determining the number of times p appears as a factor in the numerator and denominator, I tried to count them outright. At first it didn't seem so bad. The only numbers where we could get a factor of p (in your notation) would be p, 2p,...(k+1)p (in the numerator) and at first I was thinking that meant the numerator would have a factor of p^(k+1) and no higher power of p. In the case where n+1 is a multiple of p, the same holds in the denominator. In the case where n+1 is not a multiple of p, then the numbers that contribute a factor of p only go up to kp. It's a strict subset of factors of p, so there's not enough to cancel all of the factors of p in the numerator so we have to have a multiple of p.
I was happy with this until I realized that I didn't actually account for all of the factors of p. After all, what if k is large enough that p² appears? That's a factor of p that I didn't account for previously. I eventually realized that it doesn't matter because at the heart of it, in the n+1 is a multiple of p case, the exact same numbers contribute p in the numerator and denominator, so they cancel out, while otherwise the denominator has a strict subset. But I was trying to make my proof formal, and was running into notational hell
@@ALeafOnTheWind42 you have a very insightful mind. it's really nice to interact with you here. keep it up!! :)
Oh! I speak Arabie language
شكرا
How is P! = P*(P-1)! ?
An example might help. 5! = 5 x (4 x 3 x 2 x 1) = 5 x 4!
@@John_259 Right, thank you!
God... Fu-...
Can you mathematicians give it a rest with these seemingly pointless but simultaneously intriguing questions a rest?
Most practical application of mathematics came from mathematicians answering seemingly pointless yet intriguing questions, and another scientist/physicist/engineer/etc. discovered that the solution to some of these "seemingly pointless questions" are exactly the missing piece of the puzzle to their grand discovery.
So no, we're not gonna give it a rest.
P is greater than k
Bye. I think that the triangle should be attirbuted to Nicola Tartaglia. en.wikipedia.org/wiki/Niccol%C3%B2_Fontana_Tartaglia
3 is prime
5 is prime
7 is prime
9 is experimental error
11 is prime
13 is prime
Another interesting thing is when you take the "middle" row (1-1-2-3-6-10-20 etc...):
To get the next number, you will either have to multiply by 2 or by a fraction:
To get from an odd row to an even row, the factor will always be 2 (1*2=2 ; 3*2=6 ; 10*2=20 etc...) and to get from an even row to an odd row the factors will always be fractions in a specific order:
The first factor is 1/1, then 3/2, then 5/3, 7/4, etc...
What I find interesting is that the fractions are getting closer to 2 over time, however they will never reach 2
I hope that you could understand what I'm saying and I apologize for any mistakes , I'm not a native speaker :-P
Makes no sense. What is K and what does P choose K have to do with the Pth row of the triangle? Without explaining that, the rest is meaningless.
1. He explicitly defined K as 0
@@hiredfiredtired that is not a definition of k. That is just a consequence of the fact that he is using k in p choose k. He could have left that part out and the original expression would still be true since 5 choose 6 or 5 choose -3 is illogical. What he didn't explain is what k is or why he is choosing k from p in the first place.
Okay So P! = NP. Got it.
All that was true, but painfully slow. So many words for something so intuitively true. You can literally write the formula for the binomial coefficent (p k) and to point the obvious fact that always will be divisible by p, when p is prime number. What is the big deal here?
Interesting
Just a comment to help with the algorithm
Claim: I did this proof in my head.
Proof: not necessary. ; - )
Please call it by its proper name ; Khayyam/ Pascal Triangle. This triangle was created by Khayyam 500 yrs before Pascal and 200 yrs before Chinese.
Is this some joke along with Gougu Theorem 👀
U DON’T KNOW WHAT IS PRIME NUMBER！
YOU ONLY EXPLAINED EVERY NUMBER CAN BE PRIME-FACTORIZED。
Pascals triangle is wrong... look at the "2" - should not that be a 4 or possibly a more? (for reasons I won't go in to) but - just saying...
Mathematics is nothing more than symbolic representation of measured values in some kind of quantitative event, applicable to any concept whether it is real or not. Two angels plus two angels equal four angels; the math works but does not prove angels exist. Mathematics is not some kind of secret language of the universe; it is just quantitation of values. There are only four quantitative operations: plus, minus, times, and division; well, only two really; plus, and minus. You can find all kinds of patterns such as prime numbers, but they have no actual meaning other than inadvertent patterns. Those who make more of mathematics than that, have conceptual delusions, the stuff that cults are made of…