A mysterious factorial equation.
ฝัง
- เผยแพร่เมื่อ 3 มิ.ย. 2024
- We solve a nice equation over the natural numbers involving exponentiation and factorials. Our approach employs Wilson's theorem and other modular reduction tricks.
Please Subscribe: th-cam.com/users/michaelpennma...
Merch: teespring.com/stores/michael-...
Personal Website: www.michael-penn.net
Randolph College Math: www.randolphcollege.edu/mathem...
Randolph College Math and Science on Facebook: / randolph.science
Research Gate profile: www.researchgate.net/profile/...
Google Scholar profile: scholar.google.com/citations?...
If you are going to use an ad-blocker, considering using brave and tipping me BAT!
brave.com/sdp793
Buy textbooks here and help me out: amzn.to/31Bj9ye
Buy an amazon gift card and help me out: amzn.to/2PComAf
Books I like:
Abstract Algebra:
Judson(online): abstract.ups.edu/
Judson(print): amzn.to/2Xg92wD
Dummit and Foote: amzn.to/2zYOrok
Gallian: amzn.to/2zg4YEo
Artin: amzn.to/2LQ8l7C
Differential Forms:
Bachman: amzn.to/2z9wljH
Number Theory:
Crisman(online): math.gordon.edu/ntic/
Strayer: amzn.to/3bXwLah
Andrews: amzn.to/2zWlOZ0
Analysis:
Abbot: amzn.to/3cwYtuF
How to think about Analysis: amzn.to/2AIhwVm
Calculus:
OpenStax(online): openstax.org/subjects/math
OpenStax Vol 1: amzn.to/2zlreN8
OpenStax Vol 2: amzn.to/2TtwoxH
OpenStax Vol 3: amzn.to/3bPJ3Bn
My Filming Equipment:
Camera: amzn.to/3kx2JzE
Lense: amzn.to/2PFxPXA
Audio Recorder: amzn.to/2XLzkaZ
Microphones: amzn.to/3fJED0T
Lights: amzn.to/2XHxRT0
White Chalk: amzn.to/3ipu3Oh
Color Chalk: amzn.to/2XL6eIJ
Wilson + inequality + bionomial + basic congruence = amazing problem
10:47 I think we used the hypothesis when we multiplied 2*(n/2), because for that to be true, we need both 2 and (n/2) in the product, and for that, we need n/2 to be different than 2, since they come from the factorial, and therefore n>4, which implies n\geq 5.
It appeared on the SMO (Singapore Mathematical Olympiad), Open Round 2 on the year 2008, as problem number 1. Hope it helps!
@Adam Romanov You can find the pdf of it online, I got a pdf from a website fadjarp3g, plug in SMO Round 2 2008 fadjarp3g in the Google search bar and I think you should find it, hope this helps
14:00 he said "that's true for n≥5" but 4^4 > 4!, why is it
I'm sorry if it's a dumb questions
@qu-ack oh okay thanks
12:03
14:23
Something very important happened at 12:03 - u must check it out
Caesar Cipher Indeed! Thanks 👍
In general, in this video we have a "that's a good place to stop", quantity squared
Good place to start at 0:00
@@R0M4ur0 along with "let's go head and do that","all the way {up|down} to","and so on and so forth"....
I was trying that exact problem, it was in an LTE article. Thanks
Training for maths olympiad?
First thing I thought when I saw the thumbnail: "Hey, that looks like Wilson's Theorem! . . Oh wait, not quite." Wilson's Theorem says that
p | [(p-1)! + 1], iff p is prime. Here we would make n = p-1 and this becomes
(n+1) | (n! + 1), iff (n+1) is prime; vs our problem:
(n+1)ᵏ = n! + 1
which is a stronger condition on (n! + 1) than mere divisibility by (n+1).
k & n are restricted to the +ve integers, so start with k=1:
N+1 - 1 - n = n!
Works for n = 1 and 2; no others.
Solutions: (n,k) = (1,1), (2,1)
k=2:
n! + 1 will have to be a square. I think the only cases of that are n = 4, 5, and 7. n = 4 works for this equation; 5 and 7 do not:
4! + 1 = 25 = 5²
5! + 1 = 121 = 11²
7! + 1 = 5041 = 71²
So:
(4+1)² - 1 = 4! . . 24 = 24
Solution: (n,k) = (4,2)
I suspect there are no others, but I don't see a way to prove that. Let's see what Michael has...
... Very nicely done! So my suspicion was borne out. Thanks to Michael for the proof.
Fred
I wasn't aware of Wilson's Theorem, but it's not too hard to see that n+1 has to be a prime in this problem, this is the easy part of Wilson's Theorem. If n+1 has a factor, which is smaller than it, then it appears in n! as well as (n+1)^k, so the two can not be just 1 apart (they are not coprime)
Very nice solution... Nailed it👏👏
If it isn't too much of a hastle can you please put the video link in the description for theorems you used and proved in another video (like wilsons theorem here)
10:47 im guessing n>5 because you assume that there exists an n/2 >= 3, meaning n>=6
Correct, and since n+1 has to be prime, the case n=5 can be ruled out because 6 obviously isn't prime.
Una equació meravellosa. Genial
Clever solution. Especially noticing n/2 and 2 are factors of n! when n even.
I would love to see you working on inequality problems.
Le Family Patriarch
Bao Quoc Le
I love those videos.
Greetings from Spain :D
You don"t need Wilson Theorem.
(n+1)^k = n! + 1
n! + 1 is odd for n > 1, then n + 1 must be odd, then n must be even. (we don't need n + 1 prime, just the fact n is even to get k = 0[n])
Woo, that's slick
"just the fact that n is even to get k=0" how?
3:25 Not a big mistake but the left hand side is even and the right hand side is odd.
Thanks sir
Seeing your proofs is making me smarter. :)
Fantastic
Good question
Woow dope explanation.... Can u please try Putnam 2014 a5 , the official solution is unbearable 😭
Please do Putnam 2006 B2
A nice little problem from INMO 2014 , problem 2
Prove that [n] + [n/2] + [n/3] ....+ [n/n] + [√n] is even , where [n] is the floor of n
Plz see it . Thank you
Proof sketch: Notice that f(n) - f(n-1), the increase from n-1 to n, is the number of factors of n, except if n is a square number, then it is 1 more. Now use that a number has an odd number of factors if and only if it is a square.
Hello 😂
@@TechToppers hmmmm
Let f(n) be the above expression
f(n-1)
=Σⁿ⁻¹ₖ₌₁ ⌊ⁿ⁻¹/ₖ⌋ + ⌊√(n-1)⌋
= Σⁿ⁻¹ₖ₌₁ (⌈ⁿ/ₖ⌉-1) + ⌊√(n-1)⌋
(Here, we used the fact that ⌈ⁿ/ₖ⌉=⌊ⁿ⁻¹/ₖ⌋+1 for any n,k∈ℕ)
f(n)-f(n-1)
= n-Σⁿₖ₌₁ (⌈ⁿ/ₖ⌉-⌊ⁿ/ₖ⌋)
+⌊√n⌋-⌊√(n-1)⌋
Let Δ(k,n)=1 if k|n, 0 otherwise
hence ⌈ⁿ/ₖ⌉-⌊ⁿ/ₖ⌋=1-Δ(k,n)
summing from k=1 to n, it equals
Σⁿₖ₌₁ (1-Δ(k,n))
= n-Σₖₗₙ 1 = n-τ(n)
Thus
f(n)-f(n-1)=τ(n)+⌊√n⌋-⌊√(n-1)⌋
•》Case 1: n is perfect square
implying ⌊√n⌋=1+⌊√(n-1)⌋
hence f(n)-f(n-1)=τ(n)+1, which is even since τ(n) is odd if and only if n is a perfect square
•》n is not perfect square
implying ⌊√n⌋=⌊√(n-1)⌋
hence f(n)-f(n-1)=τ(n), which ia even
in either case, f(n)-f(n-1)=k
for some even k
summing from 2 to n
f(n)=(n-1)k+f(1)
= (n-1)k+2
= 2((n-1)(k/2)+1)
which is even for any n∈ℕ, as desired.
A way to skip Wilson's Theorem:
Add 1 to both sides, to get
(n+1)^k = n! + 1
Well, we know that n! + 1 is coprime to any number less than or equal to n, so any primes dividing (n+1)^k must be greater than or equal to n+1. However, by the very form of it, any primes dividing (n+1)^k must be less than or equal to n+1.
Therefore the ONLY prime dividing (n+1)^k must be n+1.
Then? How can we proceed, it's unclear for me
@@factsverse9957 Continue the argument in the video, after the point where Wilson's Theorem was used; this argument above shows that WT is unnecessary.
So, continue from 6:56 (edited to find time reference).
LTE Lemma
but... that is just a rephrase of the converse of wilson's theorem which was applied in the vid....
This problem is beautiful
n=1,2 imply k=1. Now for n>2 we must have n+1=p is a prime, otherwise n+1 would have a proper divisor 1 < d =< (n+1)/2 < n which yields a contradiction modulo d:
0=n!=(n+1)^k-1=-1 and hence we can rewrite p^k-1=(p-1)! with p>=5 or
1+p+...+p^(k-1)=(p-2)! Note that gcd(1+p+...+p^(k-1),p-1)=gcd(k,p-1)
Since (p-1)/2 < p-2 we must have
k = t (p-1)/2 for some t. Since p^(p-1)-1=
= (1+(p-1))^(p-1)-1>(p-1)^(p-1)
we must have t=1, i.e.
p^((p-1)/2)-1=(p-1)!
For p=5 we get a solution corresponding to n=4, k=2 and for p>5 we get p^((p-1)/2)-1=
=prod_(i=1)^((p-1)/2) [i(p-i)]>
>[p^2+(p-3)^2-5]p^[(p-1)/2)-2]>
>p^((p-1)/2), a contradiction. Note, that we have split the product into two factors, one for i=1,2 given by (p-1)2 (p-2) and the other for i=3,..., (p-1)/2
Vp(x!) >= 2*Vp(x) for all non prime x such that x> 4, then you can see that if n>4 and it is not prime( which is the case for n >4) k would have to be at least n, but (n + 1)^n - 1 > n! for n > 4. This is just an alternative solution:)
That was brain storming!
Uff
Will see again...
Nice problem, but at 3:28 (someone else may have already pointed this out...), you mixed up "left-hand" and "right-hand"... 😊
Let s(n) denote the sum of the digits of a positive integer n in base 10. If s(m) = 20 and s(33m) = 120,
what is the value of s(3m)?
Can someone please help me with this?
It came in India. PRMO 2019 25th August Paper
6:53 why is n + 1 a prime? Does this cover cases where n + 1 is not prime?
Reverse wilson
Just got out of Calc 3 thinking that I had gotten pretty good at math. Then I watched this and my brain melted.
This is mere child's play compared with calc 3
@@MysticMagikquite the opposite. Lots of calc stuffs are straight-up chug-in-plug-in dumb play, whilst number theory and combinatorics are whole different unpredictable beast
Good
Beautiful solution ! Kindly tell the motivation for the inequality.
Once we know k is a multiple of n, you look at the original equation again. You realize the exponent on the left hand side is at least n. Also note n^n > n!, so the left hand side is growing more rapidly than the right. The rest is details and being rigorous.
Video idea: Prove the Hardy-Ramanajan Series for partitions of n :)
He has a playlist of partitions and I think he was going to do that, or did it already. Check that out
By applying Wilson 's theorem, can we find the rest of prime numbers that are >100 (theoretically speaking)
Good luck calculating those factorials lol
@@ruairigarrett6834 You only need them mod p+1, so at least you're not dealing with numbers more than about p², but you're still doing p multiplications and might as well just try dividing p by everything less than p.
1 year later , 200k more subs
just a suggestion, can you open a new channel? one channel focuses on math question especially the Olympic question, one channel focus math theory such as analysis algebra number theory, etc.
The form of the numbers is similar to the brown numbers
Where is guy says everytime "answer=1"?
Because K is the power and n=2 (n+1)^k = n!. 1 is a constant so how did you get k=1 where n=2
3^k = 3
What k satisfies this equation?
@@RealLifeKyurem what do the 3 stripes and the -1(mod p) mean?
TNT ≡ is read “is congruent to.” -1 mod p means if you divide a number n by a prime p, the remainder is -1. In other words, it satisfies the expression:
apm - 1; for any integer a.
The reason why ≡ is used instead of =, is because any multiple of p satisfies the expression.
No Wilsons Theorem is needed. When n>4,
i) (n+1)^k= 1+n!= 1 mod (2). This imples that n is even
ii) n even implies that (n-1)! = 0 mod (n)
iii) k = ((n+1)^k-1)/n mod(n) = (n-1)! mod (n) = 0 mod(n)
(iva) k=0, no
(ivb) k>=n, Then (n+1)^k > n^n -1> n!-1. No solution,
Hence, when n>4, there is no solution.
Obviously.
Count Olaf
For integers, n^n=>n! Is true. But beyond that, it's not always true. Case in point:(1/2)^(1/2)=sqrt(2)/2 < (1/2)! = sqrt(pi)/2
Is there any problem you can't solve?
Global climate change?
0 not a natural number?
What is Mod? 😭😭😭😭
Mod gives remainder. Some examples: 5 mod 3 = 2 because 5/3 has remainder 2. 4 mod 2 = 0 because 4 is divisible by 2 (i.e. no remainder). Once again, 7 mod 2 = 1 because 7/2 has a remainder of 1.
It's important to remember when doing elementary number theory, we work in the integers and naturals. Hence all the whole number concerns.
You get (n+1)^mn-1>nⁿ>n! but isn't it was (n+1)^mn-1=n! and this means n!>nⁿ? İ think it was typo
That's the contradiction. He supposed that such an n exists and proved that its existence is impossible.
@@oussemabouaneni992 but if we get n!>nⁿ then this will be contradiction, because this never holds for these rules. But he got nⁿ>n! which is clearly true. He should be write n!>nⁿ (he got it at the end but wrote it wrongly i think, but i understood his proof method clear)
@@rustemtehmezov9494 No no he wrote it perfectly correctly. He proved that (n+1)^k - 1 > n^n > n! which means that (n+1)^k - 1 is never equal to n! for n >= 5 which is what he set out to prove.
@@oussemabouaneni992 Oh, now i understood what you mean, yeah this is accetable. (Almost same as i supposed) Thanks for clarification👍
@@rustemtehmezov9494 Cheers mate.
No Wilson's Theorem is needed. When n>4,
i) (n+1)^k= 1+n!= 1 mod (2). This implies that n is even
ii) n even and n>4 imply that (n-1)! = 0 mod (n)
iii) k = ((n+1)^k-1)/n mod(n) = (n-1)! mod (n) = 0 mod(n)
(iva) k=0, no
(ivb) k>=n, Then (n+1)^k-1 >=( n+1)^n -1>=n^n>n!. No solution,
Hence, when n>4, there is no solution.
じっと見ていると、n=4と分かりますな。
K=2
God he’s such a chad
hahahahahaha
13:33 Or just (n+1)^n -1 >= (n+1)n(n-1)... 2 - =(n+1)! -1 > n!
You say K must be a multiple of N, but the solutions given have N as a multiple of K.
all solutions with n >= 5 must have k as a multiple of n. That does not necessarily apply to the given solutions.
I got confused at how you got k=1 at n=2
Just put n=2
U get 3^k=3
Angel Mendez-Rivera That solves it. Thanks 🙏❤️ @michael penn
Immediately I don't get why n+1 is prime. If n=5 then n+1=6 is not prime.
I had to rewatch to understand it but if you reduce (n+1)^k-1=n! (mod n+1) you get 0-1=n! (mod n+1) then you rearrange to get the form from Wilson's theorem and that n+1 is prime. The zero in the above equation come from the fact that (n+1)^k is divisible by (n+1)
Hi,
This was before hair cutting, so I understand my request about the camera is not taken into account.