A Fun Twist on a Familiar Problem
2024 ж. 14 Мам.
7 500 Рет қаралды
We find the last non-zero digit of 75! written in base 10. Our approach can be generalised to finding the last non-zero digit of any factorial.
00:00 Intro
00:21 Prime factorisation
01:58 Modular arithmetic
05:06 Removing 15!
06:51 Including 2^18
07:57 Determining the last digit
I attempted this before watching the video, and did get the last non-zero digit as being a '4', but then realised after watching precisely the first minute of the video that I had wrongly counted what power of 5 was in 75! (I'd followed the correct logic of counting the multiples of five, and then of 25, but had somehow wrongly managed to claim 25 multiples of 5 and thus reached 28 powers of 5 overall), so I paused and recalculated and changed my answer to '2', then watched the rest of the video and learned it actually was a '4'. I then went back to the calculations I had written down and realised that when I had gone on to count how many powers of each of the other prime factors there were (to change them to mod 10 and then multiply them all together mod 10 for the final answer) I had also undercounted the powers of two (again i had followed the same logic as I had for the 5s, but after finding 37 multiples of two, and 18 of four I had then made 37+18 equal to 53 somehow, then added the rest of it to 53 to come up with 69 powers of 2 instead of 71). In the end two blatant arithmetic errors had cancelled each other's effects out to originally give me a correct answer overall, so I guess that's why maths exams usually award several method points in addition to the answer point, so I wouldn't have flukily got full marks for happening upon the correct answer by incorrect arithmetic.
This is a nice approach! I took a longer trip and took the primes under 100, and took them each mod 10 to get 75! = 2^{71}3^{47}5^{18}7^{20}9^{8} - then 9^8 = 1, 7^{20} = 1, 3^{47} = 3^3, and you can remove 2^{18}5^{18} from that to get 75!/10^{18} = 2^{53} 3^3 mod 10 and since 2^5 = 2 that ends up being 2^13 = 2^5 = 2 and 3^3 = 7 giving 2^{53} 3^3 mod 10 = 2 (7) = 4 mod 10
Very nicely and concisely explained.
This is why I love number theory
Very cool use of modular arithmetic!
Working in mod 10, this is (10!)^7 * 5! (numbers one thu 10, seven times, and then 71-75). Since we only care about the last nonzero digit, I can just isolate the last digit of 10!, which is 8, and take 8^7, which is equivalent to (-2)^7 in mod 10, or -128. This is equivalent to positive 2 in mod 10. Then just multiply by 5!, and get 240. Therefore the last nonzero number is 4. I think. One in nine chance I just got lucky.
the idea to count in tens is sound, but execution isn't 15! -> 8 while your calculations would've given 8^1*120 =960 -> 6 but generally you have x9*x8*x7*x6*x5*x4*x3*x2*x1*x0, where we need to get rid of zeroes at the end x0 simplifies to x x5*x2 simplifies to (x5//5)*(x2//2) and the rest just leave the last digit 9*8*7*6*(x5//5)*4*3*(x2//2)*1*x -> (x5//5)*(x2//2)*x*8 and in cases when x isn't divisible by 5 and x5 isn't divisible by 25, it can be simplified even further very easily (x5//5)*(x2//2)*x*8 = (2*x+1)*(5*x+1)*x*8
@@NoNameAtAll2 haha, okay. thanks
I proved that the last nonzero digit of n! is 6 if n=3, and otherwise is 2^((n-n1+2*n2-3*n3+4*n4)/4) mod 10, where n1, n2, n3, n4 are the number of 1’s, 2’s, 3’s, 4’s in the base-5 expansion of n. Here, 75 in base 5 is 300, so it’s 2^((75-3*1)/4)=2^18=4 mod 10, as you calculated! The proof of this formula is just a careful bookkeeping of exactly what you’re doing in the video, so it’s not worth my time to write it out, but it’s a nice general result so I thought I’d spell it out!
New subscriber here, I love number theory!
I just looked at the last numbers of each digit, because only they determine the last non zero digit. I did 9!, which ends in 8, then took 8^7, because the numers from 1 to 9 get multiplied into another seven times, with 1*2*3*4*5 remaining at the end. 8^7 ends in 2 that *2*3*4*5 ends in 4, so that is my solution.
Nice! That's how I did it.
The primes up to 75 and their frequency in the prime factorization of 75! are: 2 : 37 + 18 + 9 + 4 + 2 + 1 = 71 3 : 25 + 8 + 2 = 35 5 : 15 + 3 = 18 7 : 10 + 1 = 11 11 : 6 13 : 5 17 : 4 19 : 3 23 : 3 29 : 2 31 : 2 37 : 2 41 : 1 43 : 1 47 : 1 53 : 1 59 : 1 61 : 1 67 : 1 71 : 1 73 : 1 The 18 instances of factor 5 are cancelled by 18 instances of factor 2 (creating a factor of 10), leaving 71 - 18 = 53 instances of factor 2 to contribute to the last non-zero digit. The frequency of remaining factors modulo 10: 2 (mod 10) : 53 ==> 2^53 = (2^4)^13 * 2 = 2 (mod 10) 3 (mod 10) : 35 + 5 + 3 + 1 + 1+ 1 = 46 ==> 3^46 = (3^4)^11 * 3^2 = 9 (mod 10) 7 (mod 10) : 11 + 4 + 2 + 1 + 1 = 19 ==> 7^19 = (7^4)^4 * 7^3 = 3 (mod 10) 9 (mod 10) : 3 + 2 + 1 = 6 ==> 9^6 = (9^2)^3 = 1 (mod 10) 1 (mod 10) : 6 + 2 + 1 + 1 + 1 = 11 ==> 1^11 = 1 (mod 10) 2 * 9 * 3 * 1 *1 = 54 = 4 (mod 10) ==> Last non-zero digit is a 4 .
floor(75/5) + floor(75/25) = 15 + 3 implies 5^18 is in prime factorization of 75!. Since there are plenty of 2's to go around, we have 18 products of 2 and 5 which implies 18 trailing zeroes in 75!. Your idea of working mod 5 reduced the length of the products being considered. Will give this whirl mod 10 since it directly isolates the last digit, but is probably more onerous computationally.
Yes, there's a nice way to generalise this to count the number of times m appears in the prime factorisation of n! using the formula floor(n/m) + floor(n/m^2) + ... This essentially just counts the number of multiples of m up to n, then the number of multiples of m^2, and so on.
@@DrBarker thanks, floor(75/5) counts all multiples 5, but only counts the digit 5 once for 5^2,2*5^2 and 3*5^2 Neat how floor(75/25) corrects those three “omissions” by floor(75/5) 😀
If you have time, try the following combinatorics problem: How many multiples of 14 divide 14! and have exactly 14 divisors ? It is similar to CMIMC problem. I want to see if your approach is similar to what I tried and if you get the same answer I got. Thx
@@MyOneFiftiethOfADollar Here are my initial thoughts: In order to have exactly 14 divisors, an integer must have a prime factorisation of the form p^6 * q^1. This is like how the number of divisors of p^m * q^n is (m + 1)(n +1), if p and q are distinct primes. Our integer must be a multiple of 14, so must contain 2 and 7 in its factorisation. This leaves only 2^6 * 7, since 2 * 7^6 isn't a divisor of 14!. So I think there is only one multiple of 14 which works?
@@DrBarker I had no doubts this problem would not challenge you significantly. That’s same solution I arrived at. It was patterned after a Carnegie Mellon math competition problem which dealt with 12! The prime factorization of 12 yielded more possibilities(3x2 divisors) than 14=2x7 and I believe there were 6 values that met the criterion. Thank you for giving up some of your time, very little it appears😀 Also for problems like this where n is larger in n!, one would have to consider single p divisors of the form p^m since it has m+1 divisors. More tersely d(p^m) = m+1 In our problem 2^10 came the closest to being considered.
Slightly simpler: Those 15 blocks of 4 consecutive numbers can all be divided by 2 to remove 2^15 from the 75!/5^15. Each block's product is 2 mod 5. Two of these multiplied together is 4 mod 5, or -1 mod 5. So the first 14 blocks multiply to 1 mod 5, and need take no further part. The last product is 2 mod 5, which is like 32 and we still need to divide by another 2^3 so that leaves 4 mod 5. The last nonzero digit is 4. Can't be 9 as it must be even.
Applying the mod 5 selectively in the denominator when there are also 5's in the denominator seems a little sketchy to me. You can move that argument into the product before dividing instead. So it's okay :)
I used a somewhat more brute-force approach: Last digit of 75! = d = Last digit of (75! excluding powers of 2 and multiples of 5 • powers of 2 • multiples of 5) Powers of 2 = 2²¹ Multiples of 5 = 5¹⁵ • 15! = 5¹⁸ • 14! excluding 5,10 • 3! => d = Last digit of (75! excluding powers of 2 and multiples of 5 • 14! excluding 5,10 • 3! • 2³ • 10¹⁸) = 75! exc powers of 2 and mults of 5 • 14! exc 5,10 • 3! mod 10 • 2³ = 1⁸2⁸3⁸4⁸6⁷7⁷8⁷9⁷ excluding 1¹2²4²6¹8¹ (64,32,16,8,4,2,1) • 1²2²3²4²6¹7¹8¹9¹ • 1¹2¹3¹ • 2³ = 2¹²3¹¹4⁸6⁷7⁸8⁷9⁸ = 2⁵⁶3³⁴7⁸ Powers of 2: 2,4,8,6,2,4,... => 2⁵⁶ = 6 mod 10 Powers of 3: 3,9,7,1,3,9,... => 3³⁴ = 9 mod 10 Powers of 7: 7,9,3,1,7,9,... => 7⁸ = 1 mod 10 => d = 6•9•1 = 54 = 4 mod 10.
By Last digit 75! = d, of course you mean last nonzero digit of 75! Since d=0 the way you defined it. So why would you use terms of the form 1^m ? These terms are certainly superfluous for any actual human attempt to solve the problem.
Yes, thanks, I meant "last nonzero digit". I included the 1^n terms only to make it clearer to the reader where those numbers were coming from; I agree they're superfluous.
@@zygoloid right I understand now. Sometimes I do same thing with explicit mention of understood/ misunderstood coefficients of 1 when working with Cauchy Schwarz inequality
Around 6:00, if you just can take equivalents modulo 5 in the denominator, doesn't 5^18 become 0 so you would be dividing by zero?
75!/5^18 should be considered as product of 1..75 excluding all fives so there are actually no fives there, it's more just a shorthand notation.
How big is your whiteboard?
7:33 Are we allowed to divide by congruences ??
This is something I perhaps should have explained in more detail. The division by 5s doesn't make sense modulo 5, but is more of a shorthand way of saying to exclude those 5s from the product 75!. Division by 2 effectively means multiplication by the multiplicative inverse of 2, i.e. multiplication by 3, which is well-defined modulo 5. Similarly, division by 1, 3, and 4 are also well-defined modulo 5.
@@DrBarker right! I think the notion of multiplicative inverses is somewhat neglected in many number theory courses. Consider modulo 7 What is the meaning of the symbol 6/4? 6/4 = 6(1/4) where 1/4 means 2 since 4*2==1 (mod 7) So 6/4 = 6*2==5 (mod 7) Also 6/4 = 3/2 = 3*4==5(mod 7) since 2*4==1(mod 7) Note the definition of multiplicative inverse in modular arithmetic is analogous to (a/b)(b/a) = 1 for real numbers
After knowing N=-1 (mod 5), you can just use the obvious fact that N=0 (mod 2), and from there the CRT tells you that these two facts give you a unique solution mod 10, which you can guess as 4 or also calculate using CRT
From 1 to 10 only 3,4,6,7,8,9 contribute, 2 &5 give a 0 as does any multiple of 10. In the next decade only the last digits can contribute so 3x4x6x7x8x9=36288. again only the last '8' contributes. 8^7=2^21=something ending in 2. from 71 to 75 we only have contributions from the 3 and 4. 2x3x4=24 4 is the answer. Each decade contributes 2^3=8 Number of decades=n (2x3)^(n)= 2^(3xn) Powers of 2 end in 2,4,8,6 consecutively. Chose digit by reducing 3n mod 4 Find the contributions from the last digits of incomplete decade ignoring 10s and paired 2 and 5. Multiply chosen digit above, with product of last digits in incomplete decade. Last digit of that is answer.
"2&5 give a 0" doesn't mean numbers ending in those won't contribute at all 12*15 = 180 -> contributes 8 same with numbers ending in 0: 20 contributes 2
To save your time, it's 4
I expanded the whole product 75*74*73...*3*2*1, removed all fives (so for example 55 becomes 11 and 25 becomes 1) and removed 8,16,32,64 = 2^18. Then just multiply last digits of consecutive numbers and take last digit of the product and multiply with next last digit, and so on, and end up with a four. 😊
For those curious, 75! = 24809140811395398091946477116594033660926243886570122837795894512655842677572867409443815424000000000000000000 which does indeed have a 4 as its last non-zero digit.
Only thing I’m curious about is did you write python code to do that or just input 75! into one of the many online calculators that we all could have done ourselves had we been “curious”?
@@MyOneFiftiethOfADollar If by "write Python code", you mean "from math import factorial", then that one.