Or, that n! = 0 (mod 8) requires only that n >= 4, not the stronger n >= 8. The reason we had to go as high as 7 in the first problem was because 7 is prime.
@@davidblauyoutube I don't see why 7 being prime has to do with it..why not gonto 5 like Indid since 5 factorial is when the factorial is a multiple of 10 and ends in zero and the left hand terms are never multiples of 5 and 10 so you are done.
Because, as other in the comments have pointed out, three powers of three is trivially dismissable as not summable to a factorial, I shall instead investigate four powers of three. 3^a+3^b+3^c+3^d=n!. Find all solutions (a,b,c,d,n). First, we shall note that mod 13, the powers of three cycle (1,3,9). Thus, summing two produces these residues mod 13: (2,4,5,6,10,12). You can thus check that if you sum any two of these together you do not get 0 mod 13. Thus, n must be less than or equal to 12, as all n>=13 have 13 as a factor, while any four powers of three do not. For a lower bound, we observe that 4*3^1=12>3!, thus 4
@@mareksroka5629 That's because 0 is not considered a natural number. For whatever reason. Since the original problem specified, this solution is no included. If the set were expanded, this would certainly count.
@@themathhatter5290 depends on who you ask, there’s actually some debate wether 0 is a natural number or not. Most mathematicians don’t consider 0 to be a natural number, but there are some that do. My understanding for why they like to include 0 is because if you want to talk about the positive integers (aka the natural numbers without 0), you just write ℤ^+, but if you want to consider nonnegative integers, you write ℕ. Otherwise, if you want to include 0 you always need to union it in, which gets annoying to do
To be clear, HMMT (the Harvard MIT math tournament), is in fact a tournament for high school students! You might think from the name that is a contest for Harvard/MIT students, but it's just them that write it.
@@ritam8767 The college students write the test for high schoolers to take. And it takes place at Harvard or MIT depending on the year. That said they're still pretty difficult! You should check out some problems on there they are freely available online
@@perrydimes6915 There are 2 separate tests. They don't alternate the location. The one at Harvard is generally easier, while the one at MIT is more difficult. And if I recall, you can only sign up for one or the other. Back then, my mathematical ability was close to poor, so I could only solve upwards of 4/10 questions on any individual exam at the Harvard test. Also, the Harvard test is in November, while the MIT one in February.
I should clarify, it doesn't mean I got 4 correct each exam, just that I don't think I ever got more than 4 correct. Often times I would get 1 or 2, sometimes 0.
For the last question you presented, it's very clear that LHS is always odd for any natural number, and the RHS is even for natural numbers bigger than or equal to 2 So all that's left is to check if n=1 works, but 1! Is equal to 1 and the least LHS can be is 9, so there are no solutions for 3^a + 3^b + 3^c = n!
8:45 - It's impossible, because the factorial of 4, 5, 6 and so on is always an even number, and the sum of three powers of three is always an odd number.
You can eliminate n>=5 with the same modulus idea you used with n>=7. To do so consider a modulus of 15 (5! and bigger are 0 mod 15). The remainders mod 15 of powers of 2 are 1,2,4,8 and no combinations of pairs of these add to 0 mod 15.
2^(k+4) +1 = 2^4(2^k +1) -15 and 15 does not divide 2^k +1 for k =1,2,3,4. So 15 does not divide 2^k+1 for any natural k ( By induction) And write 2^a + 2^b = 2^m (2^k+1)= n! As 15 does not divide left hand side of above euality, so 15 cannot divide right side also. Hence , possible values of n are 1,2,3,4 only.
There is a simpler way for the first question. Suppose n>4. Then 3|n! and 5|n!. Using 3|n! we find that a and b must be of opposite parity. However, 5|n! shows that either a and b are 0 and 2 mod 4 or they are 1 and 3 mod 4 respectively. This is in contradiction with the fact that they are opposite parity. So, we only need to check n = 1, 2, 3, 4, which is very simple.
My solution involved factoring the left into 2^a(1 + 2^(b-a)). Reducing the odd factor mod 3 and 5 shows it can’t be divisible by both at once. Hence n is at most 4.
Its also equivalent to solve 2^a(1+2^b)=n! Notice that when n>=5, n! must be divisible by 15. So 1+2^b must be divisible by 15. Write down the chart for 1+2^b mod 15: 2 3 5 9 2 3… not possible.
2^a+2^b=2^a(1+2^(b-a)) for n>=5 there are no solutions since n! Divides both 3 and 5 but to divide 3 b-a must be odd and to divide 5 b-a must be even( 4n+2)
Great, now I don't even have to write this one out (that's how I've solved it as well)! You forgot to mention that we can assume b>=a since solution (a, b, n) implies solution (b, a, n).
@@sasharichter not realy. Even geniuses will miss obvious stuf every now and then, expecially if they already know an alternative solution to the problem. Adding to that we don't really know wether the solution given in the video was the intended by the author or was the solution found by the creator of the video.
the first one is kinda easy; a solution doesn't exist over the natural numbers. for the second, we can notice that in mod(7) the subtraction is not compatible with the mod(3), mod(4), mod(5), and mod(6) cases therefore we can assume that solution doesn't exist for n>6. Now we check for n=2,3,4,5,6 and we find that the solutions are, in (a,b,n) form, (2,1,2), (3,1,3), (5,3,4) and (7,3,5)
@@iceberg_heisenberg if the powers of 2 differ by a multiple of 12 won't they satisfy the condition for all the modulus you stated Eg: 2^24-2^12 is divisible by 2,3,4,5,6 and 7 So how do you rule out the existence of a large factorial satisfying the equation?
Also note that he explicitly examined the 2^0 case in the mod 7 table he constructed which could have been read to imply he was including 0 in the Naturals, even though he later then excluded it.
@@ty6339 Some people include 0 in the Natural Numbers, some don’t. (Professor Penn normally doesn’t, that’s why he didn’t mention the solution (0,0,2) )
Another nice solution: for bounding the values of n, assume, without loss on generality, that a4 then n! is divisible by 3 and 5, and, therefore, (1+2^c) must be divisible by 3 and 5, as 2^a is coprime with them. but for 1+2^c to be divisible by 3, c must be odd, while for 1+2^c to be divisible by 5 c must be writen as 4k+2, in particular, must be even. Therefore showing it is impossible for n>4.
Shorter solution: 1. n = 1 and n = 2 yield nothing so n>2. 2. a != b because n! is never power of 2 for n>2, without loss of generality it means a>b or 2^b*(2^(a-b) + 1) = n! 3. so that part 2^(a-b)+1 should be divisible by all prime factors larger than 2 that are included in n!. 4. first primes larger than 2 are 3 and 5. note that 2^m + 1 is only divisible by 3 if m = 2*k+1 or 1 mod 2 . and 2^m +1 is divisible by 5 only if m = 4*k + 2 or 2 mod 4 (if you need prove for that, note 2^m+1 = 3 for m = 1 and 2^m + 1 = 5 for m = 2, now keep increasing m until you get the next divisible by 3 or 5 respectively and ad infinitum) 5. It's easy to see that one is odd and the other is even so 2^(a-b) + 1 divisible by both 3 and 5 does not exists. hence n! can't have both 3 and 5 or n
Here’s a solution that further narrows down the possibilities for n: If n≥5, then 2^a + 2^b = 0 (mod 3) → a ≠ b (mod 2) But also 2^a + 2^b = 0 (mod 5) → a - b = 2 (mod 4) → a = b (mod 2), a contradiction. So, n ε {1,2,3,4} and then it can be checked that only n=3,4 works.
Well, I just factored 2^a * (2^(b-a) + 1) and reasoned that all the factors of 2 in n! come from 2^a, and thus (n! / 2^a) has no factors of 2. Then proceeding similarly to your approach: 2^(b-a) + 1 ≡ 0 (mod 3) ⟹ (b-a) is odd, and 2^(b-a) + 1 ≡ 0 (mod 5) ⟹ (b-a) ≡ 2 (mod 4) which is even.
@10:57: 4! is congruent to 0 (mod 8), so the proof that there are no natural numbers a, b, c, and n such that 3^a + 3^b + 3^c = n! can be concluded when it is shown that the only possible solutions must have n >= 4.
Generalisation: Given the equation x^(a_1) + x^(a_2) + ... + x^(a_N) = n! where x, a_i, N, n are elements of the natural numbers. With the equation n! > N * x, a lower bound of n can be determined. This is more complicated for the upper bound. If y is an element of the natural numbers, then for x^k mod y a solution set L_y = { ... } can be specified. If every possible sum of N elements of the solution set is not divisible by y, then an upper bound for n is the number y-1. Logically, y > N applies here. My question now is: Is there a simple relationship between x, N and the smallest upper bound? Or do you really have to try several y until you find it? In the video he gave us 7 and 8.
I did as follows: if a=b then n! must be a power of 2, so nb. Then set x=a-b and write 2^b(2^x+1)=n! If n>=3, we must have 2^x+1 = 0 (mod 3), hence 2^x=2 (mod 3) implying x is odd. If n>=5, we must have 2^5+1 = 0 (mod 5), hence 2^x=4 (mod 5) implying x = 2 (mod 4). Since these cannot be true at the same time, we conclude n
Since the two exponents are 10000 form in binary, the left hand side can have at most two bits which is 1. The RHS on the other hand will generally have many bits as 1. The only exception is 6, which is 110 binary. So n = 2, a = 0, b =0; n = 3, a = 0, b = 2.
8:55 I came up with 8 almost immediately through this reasoning: powers of 2 circle back to 1 quickly under mod 7 because 7 is 1 less than a power of 2. 8 is 1 less than a power of 3 so they also circle back quickly. 8 is 1 less than 9. The powers of 3 will just have alternating remainders 1 and 3 mod 8. 3 * 3 circles back to 1, and any combination of smaller remainders will fall short of 8. The quick circling back with one less than a power minimizes the amount of possible remainders relative to the size of the divisor, and importantly, if b is the base, and you pick (b^p)-1 as the divisor, the largest possible remainder will be b^(p - 1), which really leaves quite a gap for larger bases.
Thank you Michael, one thing that was not mentioned: when you write a number in base two, you have the condition that the exponents are different, so the a = b must be mentioned. It is clear that there is no answer in this case, because the product is a power of two, and on the right side, for n > 2, we have at least one factor other than 2.
for the 3s problem it is way easyer since it is a sum of 3 odd numbers equaling a factorial which is even all the time (except from 0 and 1) => it's imposible
Thank you for the solution. As a=b is an easy case to check out, let us pose c=a-b>0 without loss of generality, we get n!=2^b(2^c+1). The second factor is odd, thus it equals 3x5x7x9x...x (n-1) or n. We show that 2^c+1=0 mod 3 only if c is odd, and 2^c+1=0 mod 5 only if c=2 mod 4 then c is even which is a contradiction. As a result, n
To be 0 mod 3, 2^a + 2^b must have a and b of different parity, because 2^x mod 3 alternates between 1 and 2. But to be 0 mod 5, 2^a+2^b must have the same parity (digits go 2,4,8,6,2,4,8,6... and 2+8 or 4+6 are the only possibilities). This shows that n>=5 is impossible.
If n! = 2^a(2^c+1), then 2^c+1 must be divisible by any remaining odd factor. If we take 3, and the largest power of 3 dividing n! is n^x, then knowing 2+1=3, divisibility by 9 can be explored like this: 2^y + 1 = 3[2^(y-1) - 2^(y-2) +...+1] y must be divisible by 3 If z is the smallest exponent making 2^z + 1 divisible by 3^t, divisibility by 3^(t+1) can be explored like this: 2^zu + 1 = (2^z + 1)[2^(z(u-1))-...+1] u must be divisible by 3. Though, [2^(z(u-1))-...+1] can be divisible by not only 3, but also 9. Since 2^z + 1 is divisible by 3^t, the entire series' remainder from it is u, so when u=3, it can't suddenly be divisible by 9. In conclusion, if 2^z + 1 divisible by 3^t, z must be 3^(t-1). n! < 2^{[(n+1)/2]log2 * n} {[(n+1)/2]log2 * n} < 3^(t-1) {[(n+1)/2]log2 * n} < 3^[(n-3)/3] If n>=15, a solution is impossible.
A cool way to check if some number is sum of powers of two is finding its binary representation. Powers of two are in the form of 10...0 so the sum of then is something with 2 ones: 10...010...0 or 110...0 or 10...0 (in case a=b) So it is straightforward to check for "small numbers". That way you only need to translate n! to binary por n = 1..6
WLOG, assume a >= b. Then 2^a + 2^b = (2^b) x (2^(a-b) + 1). So n! has to be of the form (a power of 2) times (a power of 2 + 1). We obviously can't make 1! or 2! if a and b are natural numbers. 3! = 2 x 3 that clearly fits with b=1, (a-b)=1 => (1, 2, 3) 4! = 4 x 3! = 2^3 x 3 which also fits, with b=3, (a-b)=1 => (3, 4, 4) 5! = 5 x 4! = 2^3 x 15 but 15 isn't a power of 2 plus 1 6! = 6 x 5! = 2^4 x 45 but 45 isn't a power of 2 plus 1 The others are excluded by the mod7 argument. I just thought the arithmetic involved here was particularly simple - enough to work out the four cases in your head.
Symmetry exists between a and b: If (a,b,n) is a solution, then (b,a,n) is also a solution. (Proof trivial) We can choose b >= a. All other solutions follow from symmetry. Since a,b are elements of the natural numbers, we can choose a quantity m from element of the natural numbers with zero, so that: b = a + m. It follows: 2^a + 2^b = 2^a * (1 + 2^m) = n! If we choose m >= 2, the factor 3 or 5 is missing on the left side. Then no n > 2 can exist. Since there is a factor greater than or equal to 5 on the left-hand side, n >= 5 must apply. This leads to a contradiction. For m >= 2, no solution exists. The case m = 0 leads to the following equation: 2^(a+1) = n! Since no factor 3 can appear on the left-hand side, n
Why choose n=7. WLOG, a ≥ b; so 2^a+2^b = 2^b(2^(a-b)+1). n! ≡ 0 for all odd primes p ≤ n, implying that 2^(a-b) must be ≡ -1 modulo those primes. Trivially, 2^1 ≡ -1 (mod 3) and 2^2 ≡ -1 (mod 5) but no power of 2 ≡ -1 (mod 7). (So, 2 is not a primitive root mod 7.) So, there can't be any solutions with n ≥ 7.
Reading through the comments, I didn't notice anyone consider either of the following two related problems. (I could have missed something, so I apologize if one or both of these are redundant from another thread.) I like them because they have small but non-empty solution sets and because it's not difficult to prove that they have no further solutions. Find all positive integers a, b, m, and n such that: 1) 3^a + 3^b = m! + n! 2) (3^a) (4^b) = m! + n!
You don't have to try to combine two to get 0 mod(7). Instead you can add 1 to them and see if you get 0 mod(7). This since 2^a+2^b = 2^c(1+2^d) (when a & b are natural numbers).
Trying to solve it without looking at video: Let b>=a WLOG, factor 2^a (1+2^{b-a})=n!. If b-a=0, then we require n! to be a power of two. Hence n=2 and a=b=0 is the only solution here since for n>=3 we'd need it to be divisible by 3, which no power of two is. If b-a=1, then we need n! to be 3 times a power of two. So we need 3=3 since 3 is prime so n! isn't divisible by 3 for n
The explicit calculation on the end could be avoided by noting that 2 ≡ -1(mod 3) and 2^2 ≡ -1 (mod 5). Thus to be divisible both by 3 and by 5 (as the factorial is for n ≥ 5), the difference of a and b has to be both odd (for the left side to be divisible by 3) and even (for the left side to be divisible by 5), which clearly is impossible. Remains 3! = 6 and 4! = 24, which are both 3 times a power of 2, and therefore can be written as sum of consecutive powers of 2: 6 = 2^1+2^2,, 24 = 2^3+2^4. If we allow 0 as natural number, we also get 2^0+2^0 = 2!
For the 3^a + 3^b +3^c the mod 8 argument actually means that n is less than 4, because 4 factorial mod 8 is zero too (it contains a 2 and a 4). And since the sum 3^a+3^b+3^c is at least 9, there are no solutions.
No, that is sufficient and you're not the only one that noticed it. It does make me wonder though, does 3^a+3^b=n! have more positive integer solutions besides (1,1,3)?
So let's give it a try & write the first 10 factorials in ternary system & see if they're writen with one 2 or two 1s and further just zero's: 1!=1 2x1!=2x1=2 10!=10x2!=10x2=20
@@Apollorion you can prove that this is impossible for n>= 7 assume wlog a>=b, then 5| 3^a + 3^b => 3^(a-b) = -1 mod5 => a-b=2 mod4 => a-b is even we also know that 7| 3^a + 3^b => 3^(a-b) = -1mod 7 but 3 raised to an even power is never -1 mod 7 just by checking 3^2 =2, 3^4 = 4, 3^6 =1 mod7
wlog assume a=5 we reduce mod 15 to get 2^a(1+2^(b-a))=0 (mod 15) => 8^a2^a(1+2^(b-a))=0 (mod 15) => 1+2^(b-a)=0 (mod 15) => 2^c = -1 (mod 15) where c = b-a is a natural number since 2=2(mod 15), 2^2=4(mod 15), 2^3=8(mod 15), 2^4=1(mod 15) so this can never happen (from here it will repeat) so n
I didn't know mod 7 would work, I used mod 105. Not actually as crazy as it sounds, I just kept doubling the number (and subtracting 105 as needed) until I got a repeat digit. A "nicer" way to show 5! and 6! have no solutions is to first prove that there are no solutions where a = b, then you have b = a + c, where c is a member of the natural numbers (WLOG we don't need to consider cases where a > b) So you can factor it as 2^a ( 1 + 2^c) Which means the left part, 2^a contains all the factors of 2, and the right part, 1 + 2^c contains all of the prime factors that are not 2. Then you only need to look at whether any values of c support 1 + 2^c = 15 or 1 + 2^c = 45
But according to ISO 80000-2, Item 7-2.1, N, "the set of natural numbers" is "the set of positive integers and zero", "N={0,1,2,3,...}". Thus, zero is a natural number. Therefore, (a,b,n) can be (0,0,2) in addition to what you found.
I think it would be cool to show why this modular arithmetic approach *doesn’t* work to show there are no solutions to a^n+b^n =c^n for n greater than 2.
It's *quite* awkward to start the solution *exactly* with the answer, picking 7 without any explanation/rationale whatever. I found the solution myself and 7 can easily be discovered to be the key instead of picking it out of the blue.
k * 7 always has at least three 1s in its binary representation for any integer k >= 1. More generally, k * (2^n - 1) always has at least n 1s in its binary representation. This means that for 2^a + 2^b + 2^c = n!, for example, you can stop at n=4 because n>=5 is a multiple of 15 and will always have four 1s in its binary representation. (You can easily prove the above with a similar table of powers of two mod (2^n - 1) as for the mod 7 case.)
So, I spent a few minutes on this before watching the video. Let's say a>=b. You can note that 2^a+2^b=2^b*(2^(a-b)+1). So, for each prime factor in n! other than 2, 2^(a-b)+1 must be divisible by that, since 2^b is a power of 2. Let's put a-b=t. That means for n>=3, 2^t mod 3 = 2 (possible with t mod 2 = 1), for n>=5, 2^t mod 5 = 4 (possible with t mod 4 = 2), and for n>=7, 2^t mod 7 = 6. This has no solutions, as 2^t mod 7 is a loop that goes 1,2,4,1,2,4,etc. That means that n is strictly less than 7. This infinitely limits possible solutions. An additional note is that 2^t+1 is always odd with the exception of t = 0, in which case it's 2, and n! must be a power of 2 in that case. n cannot be 0 or 1, as 2^x>=1 for non-negative x, so 2^a+2^b>=2. There's a solution for n = 2 (a=b=0), and further n are not powers of 2 as they're divisible by 3, so t =/= 0 for them, and dividing n! by 2^b, at which point it becomes odd, finds 2^t+1. 3!=6. 6/2=3, and 3-1=2 is a power of 2. This has a solution, with a pair 1,2 4!=24. 24/8=3, and 3-1=2 is a power of 2. This has a solution, with a pair 3,4 5!=120. 120/8=15, 15-1=14 is not a power of 2, so no solution. 6!=720. 720/16=45, 45-1=44, not a power of 2, so no solution. So, solutions are only possible for n=2,3,4, with a-b pairs (0,0),(1,2) and (3,4) respectively. Of course, changing values of a and b does not impact the solution, so there's a total of 5 sets of values a, b, and n can have. Or 4 if 0 is not natural.
I solved it using this alternative approach: a) 2^a + 2^b can be rewritten as 2^c * (2^d + 1), where c is the smaller of the numbers a and b (Note: I interpreted natural numbers as including the 0). b) Then all odd prime factors of n! must devide 2^d + 1. c) It can easily be shown that 2^d + 1 can never be divisible by both 3 and 5. d) Therefor the only possible numbers n are 2, 3 and 4, which indeed all 3 have a solution (2! = 2^0 + 2^0, 3! = 2^2 + 2^1, 4! = 2^4 + 2^3).
@@AmirAnsari-kh7jb You have to look at the multiplication tables modulo 3 and modulo 5 of powers of 2. If 2^d + 1 is divisible by 3, 2^d must be 2 modulo 3, which is only the case if d is odd (d=1, 3, 5, ...). On the other hand, if 2^d + 1 is divisible by 5, 2^d must be 4 modulo 5, which is only the case for d=2, 6, 10, 14, ..., i.e. d = 4*k + 2, which implies that d must be even.
Using binary is not really needed IMO. If 2^a + 2^b = n, then at least one of the two powers (say 2^a) has to be >= n/2. Hence for 720, we get that we have to use a power of two between 360 and 720, and there is only one, 512 (and this is always the case). Since what remains, 208, is not a power of two, this is impossible.
Very nice video but I still I have a question .If we apply the same trick to 3**a+3**b=n! For n=4 we will find that we cannot constract a 0mod(4) solution from 3 base expinentials so following thr the same process we would say that n shoukd be less than 4 but for n =9 we have alot of 0mod(9) solutions for 3**a so how we know which number to pick?
My solution is a bit simpler I feel. OK so to rule out n >=5 first take the equation mod 3. As any power of 2x mod 3 is 1 if even and 2 if odd then the only combination which works is if out of a and b one is even and one is odd. wlog say a is even b is odd. So the equation can be written as 2*4^c + 4^d = n! Now take this mod 5. As every power of 4 mod 5 is 1 or 4, the only possibilies are 2 or 3 + 1 or 4. But none of these combos are 0 mod 5. So n
One could tell that 'a' and 'b' have different parities by writing the equation mod 3. Then for n>=5, write the equation mod 5 and use the last observation. With this method we don't need to eliminate the two cases n=6,7 and the proof is more straightforward.
I watched his other videos. I think he always makes things more complicated than necessary. In this case, all you have to do is to show 2^a+2^b cannot be divisible by 15 and hence n cannot be greater than or equal to 5. However, we do have to show that b is not equal to a and it can be proved BWOC. b=a => 2^a+2^b=2^(a+1) which is not divisible by 3. Therefore, n cannot be greater than or equal to 3 On the other hand, 2^a+2^b is GE 2^1+2^1=4 which implies n must be greater than 2. Contradiction.
For the general problem, where the base of the exponents is a number K, one should look that equation mod (K-1). If the number of addenda is not a multiple of K-1 itself than the LHS is not congruent to 0 mod (K-1), while the factorial is congruent to 0 mod (K-1) at least for all n >= (K-1). Of course this cannot be done in the first case where K=2, but in the second case where K=3, just looking the equator mod 2, provides a very easy proof that no solutions exist
The thing to look for is quickly-repeating modular cycles, because they give you a limited number of choices to add together to get a given modular value. For the 2s problem, the non-modular sequence of powers is 1, 2, 4, 8, 16, 32, ... Since 8 occurs in the sequence, an obvious choice is n = 8-1 = 7, which reduces this to the cycle 1, 2, 4, 1, 2, 4 ... For the 3s problem, the sequence begins 1, 3, 9, 27, 81, ... so the obvious choice is n = 9-1 = 8 to produce the cycle 1, 3, 1, 3, ...
Yes, you try 2, then you try 3, then you try 4, etc. With experience you can skip some of them. In this case it's fairly obvious that you want an odd modulus. I simplified the problem to 2^x(1+2^y) = n!. From there it is easy to see that the odd factors in (1+2^y) are going to be the problem, and now we have just one variable for the modulus. From there you just have to try 3, 5 and 7.
After the mod 7 piece, note that either a = b and n! = 2^(a+1) is a binary representation of n! and therefore unique or a != b and 2^a + 2^b is a binary representation of n! and therefore unique, so write out binary representation of factorials between 2 and 6 and the solutions are obvious.
My Solution: Assume WLOG that b>= a: 2^a(1+2^(b-a)) = n! Now we know that the LHS can't be a multiple of 7 because of the old IMO problem, which was to prove that 7 can't divide 2^n +1 (of course the profe is just to realise that the sequence is periodic mod7 with period 3) So we just need to discuss the cases when n is less than or equal to 6. To simplify the cases notice that a is just the maximum power of 2 that is in n!, Which means we can find a immediately in each case (a=b is a simple case) And so we are done!
First case I thought that it is needed 5 as a factor at the LHS also to have 0 at the end. But it might not be sufficient enough without further checks. a=b=-1 also works, but not in N.
Had a slightly different approach: 2^a+2^b can be written as 2^c(1+2^d). One can show pretty easily that for all d=1+2k (1+2^d) divides 3 and for all d=2+4k (1+2^d) divides 5. So there is no d, s.t. (1+2^d) divides both 3 and 5 but since n! for n>= 5 must divide 3 and 5, n has to be smaller than 5.
That's an interesting question. Reducing modulo any integer won't help, because we can always have zero. Observation 1) assuming b>a, the largest power of 2 in n! is going to be a. Observation 2) we need 3.5.7....m= 2^(b-a)-1, and as long as we can find such numbers, we have solutions. E.g. 3=4-1, therefore 3!=4-2. 3x5=15=16-1, therefore 5!=120=128-8, 3x5x7= 105 not equal to 2^x-1, no solution. If we can show there's an upper limit after that 3.5.7...n +1 is not a power of two, we have proven that there are a limited number of answers.
The last thing that I wanna mention is that one should be more careful when using the binary or ternary representation rules used in the video. The argument only works when powers are supposed to be distinct. For example a perfect power of 3 can be written as the sum of three powers of 3, although it has only one non-zero digit in its ternary representation. After all the idea itself is nice and these little mistakes could happen in any class.
For the original problem (and also the variation 5^a + 5^b = n! someone has already suggested) where just two powers are added, I wonder if there is any benefit in factoring the sum: Assume wlog a < b. Then 2^a + 2^b = 2^a(1+2^(b-a)). This would in turn mean that a would have to be exactly the multiplicity of 2 as a factor of n! So you could fairly directly calculate the smaller of a or b for each value of n, but that does not guarantee that there is a solution for the larger of a or b. To prove there are no solutions beyond a certain n, you would have to observe that 7|n! when n >= 7, and that (1+2^(b-a)) can never be a multiple of 7, using a similar proof as presented here. It is a little more clear here where the 7 came out of (rather than just thin air), since you would be looking for primes that are not of the form 2^k+1.
maybe theres some way to prove this more generally? like prove that there are a finite amount of solutions to m^n + m^(a) = k! for any m. or maybe m^(a_1)+m^(a_2)+m^(a_3)...+m^(a_m) = k!
actually for the last problem, for m>=3, if all a_i are >=1, m^(a_1)+m^(a_2)+m^(a_3)...+m^(a_m) is conrguent to 0 mod m, and so mod(m-1), the sum is equal to 1+1+1+1...m times which is congruent to m which is congruent to 1 mod m. and so there are no solutions for all a_i >=1. if any a_i are equal to 0, then m^(a_i) is congruent to 1 mod m-1, so you get the same sum anyways. therefore the only possible solutions for the equation would be where k
let 4 < n. taking the equation mod 3 tells us that “a” has to be of the form 2c and “b” of the form 2d+1 (or vice versa). then taking the equation mod 5 tells us there are no solutions. which means n has to be less than 5. So you don’t have to check n = 5 or 6. 🤷♂️
wow im disappointed that when i first saw this problem, i did not make the connection to binary representations of decimal numbers. once you mentioned binary, everything clicked in my head and the solution seemed obvious
I factored the LHS to (a>=b wlog) 2^b * (2^{a-b} + 1). We know b from the powers of 2 in n!. What remains must be odd and if n!/2^b is not one greater than a power of 2 then there is no solution. If a=b then the LHS is a power of 2 and again no solution. Unless a=b=0 and n=2.
For the 3^a+3^b+3^c problem it is sufficient to note that its an odd number (1 mod 2)
Or, that n! = 0 (mod 8) requires only that n >= 4, not the stronger n >= 8. The reason we had to go as high as 7 in the first problem was because 7 is prime.
Yes a very direct solution.
Brilliant observation! I totally missed this in my own comment about 4! being congruent to 0 (mod 8).
@@davidblauyoutube I don't see why 7 being prime has to do with it..why not gonto 5 like Indid since 5 factorial is when the factorial is a multiple of 10 and ends in zero and the left hand terms are never multiples of 5 and 10 so you are done.
Agree n! is always even for n>=4 and 3^a+3^b+3^c is always odd for all nonegative integers.
Because, as other in the comments have pointed out, three powers of three is trivially dismissable as not summable to a factorial, I shall instead investigate four powers of three. 3^a+3^b+3^c+3^d=n!. Find all solutions (a,b,c,d,n).
First, we shall note that mod 13, the powers of three cycle (1,3,9). Thus, summing two produces these residues mod 13: (2,4,5,6,10,12). You can thus check that if you sum any two of these together you do not get 0 mod 13. Thus, n must be less than or equal to 12, as all n>=13 have 13 as a factor, while any four powers of three do not. For a lower bound, we observe that 4*3^1=12>3!, thus 4
I love your choice of working base 3. Brilliant!
I love how you cosplay Mike with “and that is a good place to stop”!
I really don't understand why everyone completly disergard any of a,b,c or d possibly being 0.
We have 3! = 20(base 3) = 1+1+1+10(base 3).
@@mareksroka5629 That's because 0 is not considered a natural number. For whatever reason. Since the original problem specified, this solution is no included. If the set were expanded, this would certainly count.
@@themathhatter5290 depends on who you ask, there’s actually some debate wether 0 is a natural number or not. Most mathematicians don’t consider 0 to be a natural number, but there are some that do. My understanding for why they like to include 0 is because if you want to talk about the positive integers (aka the natural numbers without 0), you just write ℤ^+, but if you want to consider nonnegative integers, you write ℕ. Otherwise, if you want to include 0 you always need to union it in, which gets annoying to do
To be clear, HMMT (the Harvard MIT math tournament), is in fact a tournament for high school students! You might think from the name that is a contest for Harvard/MIT students, but it's just them that write it.
If it's for high school students then why are college students participating?
@@ritam8767 The college students write the test for high schoolers to take. And it takes place at Harvard or MIT depending on the year. That said they're still pretty difficult! You should check out some problems on there they are freely available online
@@perrydimes6915 oh so they set the problems, right I see.
I felt this one was very simple, alright I'll check a few others.
@@perrydimes6915 There are 2 separate tests. They don't alternate the location. The one at Harvard is generally easier, while the one at MIT is more difficult. And if I recall, you can only sign up for one or the other. Back then, my mathematical ability was close to poor, so I could only solve upwards of 4/10 questions on any individual exam at the Harvard test. Also, the Harvard test is in November, while the MIT one in February.
I should clarify, it doesn't mean I got 4 correct each exam, just that I don't think I ever got more than 4 correct. Often times I would get 1 or 2, sometimes 0.
For the last question you presented, it's very clear that LHS is always odd for any natural number, and the RHS is even for natural numbers bigger than or equal to 2
So all that's left is to check if n=1 works, but 1! Is equal to 1 and the least LHS can be is 9, so there are no solutions for
3^a + 3^b + 3^c = n!
LHS also can be 3, but yea ur completely right
@@kroepoek3764 It can't be 3, 3^0 is not allowed. a,b,c must be >=1
@@spencergrogin1074 where did they say that?
@@kroepoek3764 The board says that all triples have to be in N, Natural numbers. (1,2,3...)
@@spencergrogin1074 oh I was taught 0 was a natural number, but I looked it up and ur right
Michael's videos are my melange: highly addictive and heightens my (mathematical) awareness!
For 2^a+2^b it is possible to prove it can not be 0 mod(3) and 0 mod(5) at the same time, so n
8:45 - It's impossible, because the factorial of 4, 5, 6 and so on is always an even number, and the sum of three powers of three is always an odd number.
You can eliminate n>=5 with the same modulus idea you used with n>=7. To do so consider a modulus of 15 (5! and bigger are 0 mod 15). The remainders mod 15 of powers of 2 are 1,2,4,8 and no combinations of pairs of these add to 0 mod 15.
2^(k+4) +1 = 2^4(2^k +1) -15
and 15 does not divide 2^k +1 for k =1,2,3,4.
So 15 does not divide 2^k+1 for any natural k ( By induction)
And write 2^a + 2^b = 2^m (2^k+1)= n!
As 15 does not divide left hand side of above euality, so 15 cannot divide right side also.
Hence , possible values of n are 1,2,3,4 only.
Yes , on same lines, 7 does not devide 2^n+1 , for any n.
There is a simpler way for the first question. Suppose n>4. Then 3|n! and 5|n!. Using 3|n! we find that a and b must be of opposite parity. However, 5|n! shows that either a and b are 0 and 2 mod 4 or they are 1 and 3 mod 4 respectively. This is in contradiction with the fact that they are opposite parity. So, we only need to check n = 1, 2, 3, 4, which is very simple.
My solution involved factoring the left into 2^a(1 + 2^(b-a)). Reducing the odd factor mod 3 and 5 shows it can’t be divisible by both at once. Hence n is at most 4.
Its also equivalent to solve 2^a(1+2^b)=n! Notice that when n>=5, n! must be divisible by 15. So 1+2^b must be divisible by 15. Write down the chart for 1+2^b mod 15: 2 3 5 9 2 3… not possible.
In the second problem, you could simplify it by taking n=4 at the start instead of 8 because n! is congruent to 0 (mod 8) for n=4
ua-cam.com/video/LazMBkEm_3Y/v-deo.html
2^a+2^b=2^a(1+2^(b-a)) for n>=5 there are no solutions since n! Divides both 3 and 5 but to divide 3 b-a must be odd and to divide 5 b-a must be even( 4n+2)
Great, now I don't even have to write this one out (that's how I've solved it as well)! You forgot to mention that we can assume b>=a since solution (a, b, n) implies solution (b, a, n).
@@nonamehere9658 well you can also just let b>=a WLOG.
given the author missed such a simple solution I wonder how he solves much harder problems if he indeed solves them himself...
Alternatively, the trick he used with 7 also works with 15: powers of 2 are 1, 2, 4, 8, and then it repeats, and two of these don't sum to 0.
@@sasharichter not realy. Even geniuses will miss obvious stuf every now and then, expecially if they already know an alternative solution to the problem. Adding to that we don't really know wether the solution given in the video was the intended by the author or was the solution found by the creator of the video.
11:43 Homework
11:53 Here’s two exercises then : 5^a + 5^b = n! then 2^a - 2^b = n!
12:01 Good Place To Stop
perfect time, iconic phrase.
5^a+5^b= 2 mod 4
Thus we only need to check n=1,2,3
which are all impossible if a and b are natural numbers
If we allow 0 for the exponent n=2,3 works
I can solve it if you change it to 5^a - 5^b = n! AND 2^a - 2^b = n!
n = 5
the first one is kinda easy; a solution doesn't exist over the natural numbers.
for the second, we can notice that in mod(7) the subtraction is not compatible with the mod(3), mod(4), mod(5), and mod(6) cases therefore we can assume that solution doesn't exist for n>6.
Now we check for n=2,3,4,5,6 and we find that the solutions are, in (a,b,n) form, (2,1,2), (3,1,3), (5,3,4) and (7,3,5)
@@iceberg_heisenberg if the powers of 2 differ by a multiple of 12 won't they satisfy the condition for all the modulus you stated
Eg: 2^24-2^12 is divisible by 2,3,4,5,6 and 7
So how do you rule out the existence of a large factorial satisfying the equation?
I both love these problems and your Dune Tees.
Thank you, professor!
As always there is the controversy about 0 belonging to N or not, if we believe that it belongs clearly (0,0,2) is also a solution.
0: "You make me feel... you make me feel like a natural number...."
Also note that he explicitly examined the 2^0 case in the mod 7 table he constructed which could have been read to imply he was including 0 in the Naturals, even though he later then excluded it.
What do you mean believe?
@@ty6339 Some people include 0 in the Natural Numbers, some don’t. (Professor Penn normally doesn’t, that’s why he didn’t mention the solution (0,0,2) )
@@Bodyknock I know, its just that the word ''believe'' sounded weird to me, since its a matter of definition.
9:05 Couldn't you have been even more restrictive there? n! is congruent to 0 mod 8 if n>=4.
Another nice solution: for bounding the values of n, assume, without loss on generality, that a4 then n! is divisible by 3 and 5, and, therefore, (1+2^c) must be divisible by 3 and 5, as 2^a is coprime with them. but for 1+2^c to be divisible by 3, c must be odd, while for 1+2^c to be divisible by 5 c must be writen as 4k+2, in particular, must be even. Therefore showing it is impossible for n>4.
Shorter solution:
1. n = 1 and n = 2 yield nothing so n>2.
2. a != b because n! is never power of 2 for n>2, without loss of generality it means a>b or 2^b*(2^(a-b) + 1) = n!
3. so that part 2^(a-b)+1 should be divisible by all prime factors larger than 2 that are included in n!.
4. first primes larger than 2 are 3 and 5. note that 2^m + 1 is only divisible by 3 if m = 2*k+1 or 1 mod 2 . and 2^m +1 is divisible by 5 only if m = 4*k + 2 or 2 mod 4
(if you need prove for that, note 2^m+1 = 3 for m = 1 and 2^m + 1 = 5 for m = 2, now keep increasing m until you get the next divisible by 3 or 5 respectively and ad infinitum)
5. It's easy to see that one is odd and the other is even so 2^(a-b) + 1 divisible by both 3 and 5 does not exists. hence n! can't have both 3 and 5 or n
It's a high school competition, so yes, we can get into highschool with our proofs :)
Here’s a solution that further narrows down the possibilities for n:
If n≥5, then 2^a + 2^b = 0 (mod 3) → a ≠ b (mod 2)
But also 2^a + 2^b = 0 (mod 5) → a - b = 2 (mod 4) → a = b (mod 2), a contradiction.
So, n ε {1,2,3,4} and then it can be checked that only n=3,4 works.
Well, I just factored 2^a * (2^(b-a) + 1) and reasoned that all the factors of 2 in n! come from 2^a, and thus (n! / 2^a) has no factors of 2. Then proceeding similarly to your approach: 2^(b-a) + 1 ≡ 0 (mod 3) ⟹ (b-a) is odd, and 2^(b-a) + 1 ≡ 0 (mod 5) ⟹ (b-a) ≡ 2 (mod 4) which is even.
@@websnarf That’s exactly what I did the first time, I changed the solution a bit here.
Magic math Trick 🤔
ua-cam.com/users/shortsuyPllWuSyuw?feature=share
@10:57: 4! is congruent to 0 (mod 8), so the proof that there are no natural numbers a, b, c, and n such that 3^a + 3^b + 3^c = n! can be concluded when it is shown that the only possible solutions must have n >= 4.
Generalisation:
Given the equation
x^(a_1) + x^(a_2) + ... + x^(a_N) = n!
where x, a_i, N, n are elements of the natural numbers. With the equation n! > N * x, a lower bound of n can be determined. This is more complicated for the upper bound. If y is an element of the natural numbers, then for x^k mod y a solution set L_y = { ... } can be specified. If every possible sum of N elements of the solution set is not divisible by y, then an upper bound for n is the number y-1. Logically, y > N applies here.
My question now is: Is there a simple relationship between x, N and the smallest upper bound? Or do you really have to try several y until you find it? In the video he gave us 7 and 8.
Let b < a. Factor out 2 ^ b. (2 ^ (a -b) + 1)mod 15 is never 0. n! for n>=5 mod 15 is 0. Therefore, n
This is really lovely. Nice work Boris!!!
You have enviable and amazing skills Michael. Noticed you hurt your left hand - hope is not serious and that it’s better now.
I did as follows: if a=b then n! must be a power of 2, so nb. Then set x=a-b and write 2^b(2^x+1)=n!
If n>=3, we must have 2^x+1 = 0 (mod 3), hence 2^x=2 (mod 3) implying x is odd.
If n>=5, we must have 2^5+1 = 0 (mod 5), hence 2^x=4 (mod 5) implying x = 2 (mod 4).
Since these cannot be true at the same time, we conclude n
Since the two exponents are 10000 form in binary, the left hand side can have at most two bits which is 1.
The RHS on the other hand will generally have many bits as 1. The only exception is 6, which is 110 binary.
So
n = 2, a = 0, b =0;
n = 3, a = 0, b = 2.
8:55 I came up with 8 almost immediately through this reasoning: powers of 2 circle back to 1 quickly under mod 7 because 7 is 1 less than a power of 2. 8 is 1 less than a power of 3 so they also circle back quickly. 8 is 1 less than 9. The powers of 3 will just have alternating remainders 1 and 3 mod 8. 3 * 3 circles back to 1, and any combination of smaller remainders will fall short of 8. The quick circling back with one less than a power minimizes the amount of possible remainders relative to the size of the divisor, and importantly, if b is the base, and you pick (b^p)-1 as the divisor, the largest possible remainder will be b^(p - 1), which really leaves quite a gap for larger bases.
Thank you Michael, one thing that was not mentioned: when you write a number in base two, you have the condition that the exponents are different, so the a = b must be mentioned.
It is clear that there is no answer in this case, because the product is a power of two, and on the right side, for n > 2, we have at least one factor other than 2.
for the 3s problem it is way easyer since it is a sum of 3 odd numbers equaling a factorial which is even all the time (except from 0 and 1) => it's imposible
I love that proof :-)
Yeah, I didn’t see yours, but I was thinking the exact same thinf
If we consider that 2^x + 1 is not congruent to 0 mod 15 (3*5) we have that n
ua-cam.com/video/LazMBkEm_3Y/v-deo.html
Thank you for the solution. As a=b is an easy case to check out, let us pose c=a-b>0 without loss of generality, we get n!=2^b(2^c+1). The second factor is odd, thus it equals 3x5x7x9x...x (n-1) or n. We show that 2^c+1=0 mod 3 only if c is odd, and 2^c+1=0 mod 5 only if c=2 mod 4 then c is even which is a contradiction. As a result, n
To be 0 mod 3, 2^a + 2^b must have a and b of different parity, because 2^x mod 3 alternates between 1 and 2. But to be 0 mod 5, 2^a+2^b must have the same parity (digits go 2,4,8,6,2,4,8,6... and 2+8 or 4+6 are the only possibilities). This shows that n>=5 is impossible.
ok here is my problem, given the equasion k^a + k^b + ... (k times) = n!, find the function sm(k,n) - smallest n where there are no solution
yes, I wonder whether this is in the OEIS (by the way I think you want sm(k) = (the smallest) n, not sm(k,n))
If n! = 2^a(2^c+1), then 2^c+1 must be divisible by any remaining odd factor.
If we take 3, and the largest power of 3 dividing n! is n^x, then knowing 2+1=3, divisibility by 9 can be explored like this:
2^y + 1 = 3[2^(y-1) - 2^(y-2) +...+1]
y must be divisible by 3
If z is the smallest exponent making 2^z + 1 divisible by 3^t, divisibility by 3^(t+1) can be explored like this:
2^zu + 1 = (2^z + 1)[2^(z(u-1))-...+1]
u must be divisible by 3.
Though, [2^(z(u-1))-...+1] can be divisible by not only 3, but also 9. Since 2^z + 1 is divisible by 3^t, the entire series' remainder from it is u, so when u=3, it can't suddenly be divisible by 9.
In conclusion, if 2^z + 1 divisible by 3^t, z must be 3^(t-1).
n! < 2^{[(n+1)/2]log2 * n}
{[(n+1)/2]log2 * n} < 3^(t-1)
{[(n+1)/2]log2 * n} < 3^[(n-3)/3]
If n>=15, a solution is impossible.
A cool way to check if some number is sum of powers of two is finding its binary representation. Powers of two are in the form of 10...0 so the sum of then is something with 2 ones:
10...010...0 or 110...0 or 10...0 (in case a=b)
So it is straightforward to check for "small numbers". That way you only need to translate n! to binary por n = 1..6
WLOG, assume a >= b. Then 2^a + 2^b = (2^b) x (2^(a-b) + 1). So n! has to be of the form (a power of 2) times (a power of 2 + 1).
We obviously can't make 1! or 2! if a and b are natural numbers.
3! = 2 x 3 that clearly fits with b=1, (a-b)=1 => (1, 2, 3)
4! = 4 x 3! = 2^3 x 3 which also fits, with b=3, (a-b)=1 => (3, 4, 4)
5! = 5 x 4! = 2^3 x 15 but 15 isn't a power of 2 plus 1
6! = 6 x 5! = 2^4 x 45 but 45 isn't a power of 2 plus 1
The others are excluded by the mod7 argument.
I just thought the arithmetic involved here was particularly simple - enough to work out the four cases in your head.
Symmetry exists between a and b: If (a,b,n) is a solution, then (b,a,n) is also a solution. (Proof trivial)
We can choose b >= a. All other solutions follow from symmetry. Since a,b are elements of the natural numbers, we can choose a quantity m from element of the natural numbers with zero, so that: b = a + m. It follows:
2^a + 2^b = 2^a * (1 + 2^m) = n!
If we choose m >= 2, the factor 3 or 5 is missing on the left side. Then no n > 2 can exist. Since there is a factor greater than or equal to 5 on the left-hand side, n >= 5 must apply. This leads to a contradiction. For m >= 2, no solution exists.
The case m = 0 leads to the following equation:
2^(a+1) = n!
Since no factor 3 can appear on the left-hand side, n
Freaking love this channel even though I barely understand most of the problems
Why choose n=7. WLOG, a ≥ b; so 2^a+2^b = 2^b(2^(a-b)+1). n! ≡ 0 for all odd primes p ≤ n, implying that 2^(a-b) must be ≡ -1 modulo those primes. Trivially,
2^1 ≡ -1 (mod 3) and 2^2 ≡ -1 (mod 5) but no power of 2 ≡ -1 (mod 7). (So, 2 is not a primitive root mod 7.) So, there can't be any solutions with n ≥ 7.
9:59 shouldn't you have said 3 elements?
Reading through the comments, I didn't notice anyone consider either of the following two related problems. (I could have missed something, so I apologize if one or both of these are redundant from another thread.) I like them because they have small but non-empty solution sets and because it's not difficult to prove that they have no further solutions.
Find all positive integers a, b, m, and n such that:
1) 3^a + 3^b = m! + n!
2) (3^a) (4^b) = m! + n!
Magic math Trick 🤔
ua-cam.com/users/shortsuyPllWuSyuw?feature=share
You don't have to try to combine two to get 0 mod(7). Instead you can add 1 to them and see if you get 0 mod(7). This since 2^a+2^b = 2^c(1+2^d) (when a & b are natural numbers).
Not sure if someone already posted this one: if a-b is even we are done (since then 2^{a-b}+1 won't be divisible by 3 (mod 4) primes, so n
ua-cam.com/video/LazMBkEm_3Y/v-deo.html
Trying to solve it without looking at video:
Let b>=a WLOG, factor 2^a (1+2^{b-a})=n!.
If b-a=0, then we require n! to be a power of two. Hence n=2 and a=b=0 is the only solution here since for n>=3 we'd need it to be divisible by 3, which no power of two is.
If b-a=1, then we need n! to be 3 times a power of two. So we need 3=3 since 3 is prime so n! isn't divisible by 3 for n
The explicit calculation on the end could be avoided by noting that 2 ≡ -1(mod 3) and 2^2 ≡ -1 (mod 5). Thus to be divisible both by 3 and by 5 (as the factorial is for n ≥ 5), the difference of a and b has to be both odd (for the left side to be divisible by 3) and even (for the left side to be divisible by 5), which clearly is impossible. Remains 3! = 6 and 4! = 24, which are both 3 times a power of 2, and therefore can be written as sum of consecutive powers of 2: 6 = 2^1+2^2,, 24 = 2^3+2^4. If we allow 0 as natural number, we also get 2^0+2^0 = 2!
3^a+3^b+3^c is odd, so there is no solution for n>1 as 2|n!
Yeah, I said the same thing
Interesting, it boils down to experience I guess
ua-cam.com/video/LazMBkEm_3Y/v-deo.html
For the 3^a + 3^b +3^c the mod 8 argument actually means that n is less than 4, because 4 factorial mod 8 is zero too (it contains a 2 and a 4).
And since the sum 3^a+3^b+3^c is at least 9, there are no solutions.
Can someone explain why my proposal for a solution that I made two hours ago was erased, what mistake I made?
Even better is to use mod 15. Obviously, 2^a+2^b is not divisible by 15 for the same reason. But 15 | 5!. So, n
Isn’t it sufficient to say that 3^x is an odd number and adding three odd numbers can never be an even number and all n! where n > 1 are even?
No, that is sufficient and you're not the only one that noticed it.
It does make me wonder though, does 3^a+3^b=n! have more positive integer solutions besides (1,1,3)?
@@Apollorion I am also curious of that
So let's give it a try & write the first 10 factorials in ternary system & see if they're writen with one 2 or two 1s and further just zero's:
1!=1
2x1!=2x1=2
10!=10x2!=10x2=20
@@Apollorion I mean sure you checked a bunch of cases, but that’s not a proof haha, I like your thought though
@@Apollorion you can prove that this is impossible for n>= 7
assume wlog a>=b, then 5| 3^a + 3^b => 3^(a-b) = -1 mod5
=> a-b=2 mod4 => a-b is even
we also know that 7| 3^a + 3^b => 3^(a-b) = -1mod 7
but 3 raised to an even power is never -1 mod 7
just by checking 3^2 =2, 3^4 = 4, 3^6 =1 mod7
wlog assume a=5 we reduce mod 15 to get
2^a(1+2^(b-a))=0 (mod 15) => 8^a2^a(1+2^(b-a))=0 (mod 15) => 1+2^(b-a)=0 (mod 15) => 2^c = -1 (mod 15) where c = b-a is a natural number
since
2=2(mod 15), 2^2=4(mod 15), 2^3=8(mod 15), 2^4=1(mod 15) so this can never happen (from here it will repeat)
so n
I didn't know mod 7 would work, I used mod 105. Not actually as crazy as it sounds, I just kept doubling the number (and subtracting 105 as needed) until I got a repeat digit.
A "nicer" way to show 5! and 6! have no solutions is to first prove that there are no solutions where a = b, then you have b = a + c, where c is a member of the natural numbers (WLOG we don't need to consider cases where a > b)
So you can factor it as
2^a ( 1 + 2^c)
Which means the left part, 2^a contains all the factors of 2, and the right part, 1 + 2^c contains all of the prime factors that are not 2.
Then you only need to look at whether any values of c support 1 + 2^c = 15 or 1 + 2^c = 45
But according to ISO 80000-2, Item 7-2.1, N, "the set of natural numbers" is "the set of positive integers and zero", "N={0,1,2,3,...}". Thus, zero is a natural number. Therefore, (a,b,n) can be (0,0,2) in addition to what you found.
I think it would be cool to show why this modular arithmetic approach *doesn’t* work to show there are no solutions to a^n+b^n =c^n for n greater than 2.
6:58 wow I would never have thought of that
It's *quite* awkward to start the solution *exactly* with the answer, picking 7 without any explanation/rationale whatever. I found the solution myself and 7 can easily be discovered to be the key instead of picking it out of the blue.
k * 7 always has at least three 1s in its binary representation for any integer k >= 1. More generally, k * (2^n - 1) always has at least n 1s in its binary representation. This means that for 2^a + 2^b + 2^c = n!, for example, you can stop at n=4 because n>=5 is a multiple of 15 and will always have four 1s in its binary representation.
(You can easily prove the above with a similar table of powers of two mod (2^n - 1) as for the mod 7 case.)
So, I spent a few minutes on this before watching the video.
Let's say a>=b. You can note that 2^a+2^b=2^b*(2^(a-b)+1). So, for each prime factor in n! other than 2, 2^(a-b)+1 must be divisible by that, since 2^b is a power of 2. Let's put a-b=t.
That means for n>=3, 2^t mod 3 = 2 (possible with t mod 2 = 1), for n>=5, 2^t mod 5 = 4 (possible with t mod 4 = 2), and for n>=7, 2^t mod 7 = 6. This has no solutions, as 2^t mod 7 is a loop that goes 1,2,4,1,2,4,etc. That means that n is strictly less than 7. This infinitely limits possible solutions.
An additional note is that 2^t+1 is always odd with the exception of t = 0, in which case it's 2, and n! must be a power of 2 in that case.
n cannot be 0 or 1, as 2^x>=1 for non-negative x, so 2^a+2^b>=2. There's a solution for n = 2 (a=b=0), and further n are not powers of 2 as they're divisible by 3, so t =/= 0 for them, and dividing n! by 2^b, at which point it becomes odd, finds 2^t+1.
3!=6. 6/2=3, and 3-1=2 is a power of 2. This has a solution, with a pair 1,2
4!=24. 24/8=3, and 3-1=2 is a power of 2. This has a solution, with a pair 3,4
5!=120. 120/8=15, 15-1=14 is not a power of 2, so no solution.
6!=720. 720/16=45, 45-1=44, not a power of 2, so no solution.
So, solutions are only possible for n=2,3,4, with a-b pairs (0,0),(1,2) and (3,4) respectively. Of course, changing values of a and b does not impact the solution, so there's a total of 5 sets of values a, b, and n can have. Or 4 if 0 is not natural.
I solved it using this alternative approach:
a) 2^a + 2^b can be rewritten as 2^c * (2^d + 1), where c is the smaller of the numbers a and b (Note: I interpreted natural numbers as including the 0).
b) Then all odd prime factors of n! must devide 2^d + 1.
c) It can easily be shown that 2^d + 1 can never be divisible by both 3 and 5.
d) Therefor the only possible numbers n are 2, 3 and 4, which indeed all 3 have a solution (2! = 2^0 + 2^0, 3! = 2^2 + 2^1, 4! = 2^4 + 2^3).
@@AmirAnsari-kh7jb You have to look at the multiplication tables modulo 3 and modulo 5 of powers of 2. If 2^d + 1 is divisible by 3, 2^d must be 2 modulo 3, which is only the case if d is odd (d=1, 3, 5, ...). On the other hand, if 2^d + 1 is divisible by 5, 2^d must be 4 modulo 5, which is only the case for d=2, 6, 10, 14, ..., i.e. d = 4*k + 2, which implies that d must be even.
It's not really obvious to guess that n
Using binary is not really needed IMO. If 2^a + 2^b = n, then at least one of the two powers (say 2^a) has to be >= n/2. Hence for 720, we get that we have to use a power of two between 360 and 720, and there is only one, 512 (and this is always the case). Since what remains, 208, is not a power of two, this is impossible.
Very nice video but I still I have a question .If we apply the same trick to 3**a+3**b=n! For n=4 we will find that we cannot constract a 0mod(4) solution from 3 base expinentials so following thr the same process we would say that n shoukd be less than 4 but for n =9 we have alot of 0mod(9) solutions for 3**a so how we know which number to pick?
hey! 4! is congruent to 0 mod 8 too
My solution is a bit simpler I feel. OK so to rule out n >=5 first take the equation mod 3. As any power of 2x mod 3 is 1 if even and 2 if odd then the only combination which works is if out of a and b one is even and one is odd. wlog say a is even b is odd.
So the equation can be written as
2*4^c + 4^d = n!
Now take this mod 5.
As every power of 4 mod 5 is 1 or 4, the only possibilies are
2 or 3 + 1 or 4.
But none of these combos are 0 mod 5.
So n
One could tell that 'a' and 'b' have different parities by writing the equation mod 3. Then for n>=5, write the equation mod 5 and use the last observation. With this method we don't need to eliminate the two cases n=6,7 and the proof is more straightforward.
I watched his other videos. I think he always makes things more complicated than necessary. In this case, all you have to do is to show 2^a+2^b cannot be divisible by 15 and hence n cannot be greater than or equal to 5. However, we do have to show that b is not equal to a and it can be proved BWOC.
b=a => 2^a+2^b=2^(a+1) which is not divisible by 3.
Therefore, n cannot be greater than or equal to 3
On the other hand, 2^a+2^b is GE 2^1+2^1=4 which implies n must be greater than 2.
Contradiction.
For the general problem, where the base of the exponents is a number K, one should look that equation mod (K-1). If the number of addenda is not a multiple of K-1 itself than the LHS is not congruent to 0 mod (K-1), while the factorial is congruent to 0 mod (K-1) at least for all n >= (K-1).
Of course this cannot be done in the first case where K=2, but in the second case where K=3, just looking the equator mod 2, provides a very easy proof that no solutions exist
I like the argument at 7:00 - so easy, but I don't think I would have seen it myself.
Is there any algorithm for picking the modulus for solving such problems?
The thing to look for is quickly-repeating modular cycles, because they give you a limited number of choices to add together to get a given modular value. For the 2s problem, the non-modular sequence of powers is 1, 2, 4, 8, 16, 32, ... Since 8 occurs in the sequence, an obvious choice is n = 8-1 = 7, which reduces this to the cycle 1, 2, 4, 1, 2, 4 ... For the 3s problem, the sequence begins 1, 3, 9, 27, 81, ... so the obvious choice is n = 9-1 = 8 to produce the cycle 1, 3, 1, 3, ...
Yes, you try 2, then you try 3, then you try 4, etc. With experience you can skip some of them. In this case it's fairly obvious that you want an odd modulus.
I simplified the problem to 2^x(1+2^y) = n!. From there it is easy to see that the odd factors in (1+2^y) are going to be the problem, and now we have just one variable for the modulus. From there you just have to try 3, 5 and 7.
@@davidblauyoutube but why 8 why not 4 or just a matter of experience?
More important the algorithm is to casually propose the modulus like it's trivial when presenting :)
After the mod 7 piece, note that either a = b and n! = 2^(a+1) is a binary representation of n! and therefore unique or a != b and 2^a + 2^b is a binary representation of n! and therefore unique, so write out binary representation of factorials between 2 and 6 and the solutions are obvious.
I was told at school never to write the digit 8 as two circles one above the other. it should start off as an S then loop back to the start point.
ua-cam.com/video/LazMBkEm_3Y/v-deo.html
I don't understand why (0,0,2) isn't a valid solution. N includes 0, right?
How can we do this if the powers of twos are subtracted instead of summed? 2^7 - 2^3 = 120, also 2^5-2^3 = 24,
The solution for n=5, n=6 is just beautiful!
How did you know to go with n=7 for the cut off?
Why not 5 or 3?
My Solution:
Assume WLOG that b>= a:
2^a(1+2^(b-a)) = n!
Now we know that the LHS can't be a multiple of 7 because of the old IMO problem, which was to prove that 7 can't divide 2^n +1 (of course the profe is just to realise that the sequence is periodic mod7 with period 3)
So we just need to discuss the cases when n is less than or equal to 6.
To simplify the cases notice that a is just the maximum power of 2 that is in n!, Which means we can find a immediately in each case (a=b is a simple case)
And so we are done!
This is essentially the same solution as the video. Factoring the left hand side does not change the solution in a substantial way.
Love the Tshirt!!
As soon as we limit n to {3..6}, just convert each n! to binary. Any solution must have exactly 2 one bits. That's 6 and 24.
No need to check 5, 6 and 7, since n! is 0 mod 8 for n >= 4.
2⁰+2⁰=2!
(0,0,2) is solutions
I don't understand the 2nd problem. 3^a+3^b+3^c is odd and n! is even so there is no solution. There is no need to check every sub cases.
Could you write the factorials in binary and check for numbers with only 2 1s in their binary digits?
If interested, I posted a proof using this approach in the comments
First case I thought that it is needed 5 as a factor at the LHS also to have 0 at the end. But it might not be sufficient enough without further checks. a=b=-1 also works, but not in N.
ua-cam.com/video/LazMBkEm_3Y/v-deo.html
Had a slightly different approach: 2^a+2^b can be written as 2^c(1+2^d). One can show pretty easily that for all d=1+2k (1+2^d) divides 3 and for all d=2+4k (1+2^d) divides 5. So there is no d, s.t. (1+2^d) divides both 3 and 5 but since n! for n>= 5 must divide 3 and 5, n has to be smaller than 5.
Love the T-shirt! Wish they had it in green and orange.
ua-cam.com/video/LazMBkEm_3Y/v-deo.html
How about the difference of powers of two?
That's an interesting question. Reducing modulo any integer won't help, because we can always have zero.
Observation 1) assuming b>a, the largest power of 2 in n! is going to be a.
Observation 2) we need 3.5.7....m= 2^(b-a)-1, and as long as we can find such numbers, we have solutions. E.g. 3=4-1, therefore 3!=4-2. 3x5=15=16-1, therefore 5!=120=128-8, 3x5x7= 105 not equal to 2^x-1, no solution. If we can show there's an upper limit after that 3.5.7...n +1 is not a power of two, we have proven that there are a limited number of answers.
What I did was to show that if n>=5 (then 15|n!) it is impossible for 15 to divide 2^a+2^b as well
The last thing that I wanna mention is that one should be more careful when using the binary or ternary representation rules used in the video. The argument only works when powers are supposed to be distinct. For example a perfect power of 3 can be written as the sum of three powers of 3, although it has only one non-zero digit in its ternary representation. After all the idea itself is nice and these little mistakes could happen in any class.
For the original problem (and also the variation 5^a + 5^b = n! someone has already suggested) where just two powers are added, I wonder if there is any benefit in factoring the sum:
Assume wlog a < b.
Then 2^a + 2^b = 2^a(1+2^(b-a)).
This would in turn mean that a would have to be exactly the multiplicity of 2 as a factor of n!
So you could fairly directly calculate the smaller of a or b for each value of n, but that does not guarantee that there is a solution for the larger of a or b.
To prove there are no solutions beyond a certain n, you would have to observe that 7|n! when n >= 7, and that (1+2^(b-a)) can never be a multiple of 7, using a similar proof as presented here. It is a little more clear here where the 7 came out of (rather than just thin air), since you would be looking for primes that are not of the form 2^k+1.
maybe theres some way to prove this more generally? like prove that there are a finite amount of solutions to m^n + m^(a) = k! for any m. or maybe m^(a_1)+m^(a_2)+m^(a_3)...+m^(a_m) = k!
actually for the last problem, for m>=3, if all a_i are >=1, m^(a_1)+m^(a_2)+m^(a_3)...+m^(a_m) is conrguent to 0 mod m, and so mod(m-1), the sum is equal to 1+1+1+1...m times which is congruent to m which is congruent to 1 mod m. and so there are no solutions for all a_i >=1. if any a_i are equal to 0, then m^(a_i) is congruent to 1 mod m-1, so you get the same sum anyways. therefore the only possible solutions for the equation would be where k
for the first problem just consider the sum mod m^2-1 and you'll find the solution quickly enough
Thank You Genius
Easy to show n=5 then 2^(a-b)+1 == 0 mod 15 again not possible. So n
let 4 < n. taking the equation mod 3 tells us that “a” has to be of the form 2c and “b” of the form 2d+1 (or vice versa). then taking the equation mod 5 tells us there are no solutions. which means n has to be less than 5. So you don’t have to check n = 5 or 6. 🤷♂️
I found it interesting that if a,b, and n are all integers, it yields that (-1,-1,0) and (-1,-1,1) are both solutions because .5+.5=1
This was also a problem 5 on the 2nd round of the Russian Mathematical Olympiad.
For the 3's problem, isn't the issue that you can't add 3 of them to get 0 mod 8, not 2?
ua-cam.com/video/LazMBkEm_3Y/v-deo.html
wow im disappointed that when i first saw this problem, i did not make the connection to binary representations of decimal numbers. once you mentioned binary, everything clicked in my head and the solution seemed obvious
uh... n! with n >= 4 is also congruent to 0 mod 8
I factored the LHS to (a>=b wlog) 2^b * (2^{a-b} + 1). We know b from the powers of 2 in n!. What remains must be odd and if n!/2^b is not one greater than a power of 2 then there is no solution. If a=b then the LHS is a power of 2 and again no solution. Unless a=b=0 and n=2.