wow thanks hedge! I can see why this was a spec question since it has pretty much all the skills they'd expect at interview stage lol. Thanks for the swift video honestly this has helped a lot. Do you have a contact email where viewers can send in potential challenging questions?
@AlgebraicAnalysis
Ай бұрын
A somewhat systematic way of doing this would be to apply a sort of sieve in modulo: Let p be a prime, then we have p = 1 mod 4 or 3 mod 4 -> p^2 = 1 mod 4 -> p^2 - 1 = 0 mod 4 p = 1 or 3 or 5 or 7 mod 8 -> p^2 = 1 mod 8 -> p^2 - 1 = 0 mod 8 p = 3 mod 16 -> p^2 = 9 mod 16 -> p^2 - 1 = 8 mod 16 so the sieve for powers of 2 terminates here. Now let's try for powers of 3. p = 1 or 2 mod 3 -> p^2 = 1 mod 3 -> ... p = 2 mod 9 -> p^2 = 4 mod 9 -> sieve fails This gives at least 8 and 3 as factors. For primes q > 3 i.e. q >= 5, we have p = +/-2 mod q -> p^2 = 4 mod q (irreducible) -> sieve fails. Though this assumes a sort of twin prime conjecture in modulo i.e. that for any prime q >= 5, there exists a prime p = +/-2 mod q. The reverse of this, that there exists such a q for a given p, is rather obvious. Can one prove this in forward? At any rate, for the problem at hand, it suffices to just consider p = 7, which is 2 mod 5, -4 mod 11 (-> p^2 = 5 mod 11), 7 mod 13 -> p^2 is 10 mod 13, .... then you can stop before primes q > 49 since then p^2 mod q is always 49. In summary, a loose guide for this problem with p > n is to apply the sieve, then check when it fails at a prime, and guess that it fails for all primes q greater than that, by checking using the smallest prime k > n up to q < k^2. A conjecture which would be useful as a lemma would be that if the sieve fails for a prime q, then it fails for all primes greater than q.
@ronnietwelvetoes1876
Ай бұрын
P = 1 it is ovious
@killermathquant
Ай бұрын
Hedge could you go over the solution to Step 2 Spec Q9. I cant find a solution online anywhere and i feel like theres a lot more elegant solutions to it than the ones i did.
@hedgehog11953
Ай бұрын
@@killermathquant I’ll try to do one this week
@killermathquant
Ай бұрын
@hedgehog11953 wait my bad i meant Step 1 Specimen Q9 😂 I just find the absolute value inequality really finnicky
@hedgehog11953
Ай бұрын
@@killermathquant will have look at it by the end of today 👍
@dane4kka
Ай бұрын
Every perfect square has remainders 0 and 1 when divided by 3. Since p is not divisible by 3, then p^2 == 1 mod 3. So p^2-1 == 0 mod 3.
@somgesomgedus9313
Ай бұрын
My solution: p is of the form 6n+1 or 6n+5 where n>0. Then p^2-1 is either 12*n(3n+1) or 12*(n+1)(3n+2). The first term is divisible by 24 and all its divisors, since n or 3n+1 is even. The second term has these In general, there need not be more divisors as the examples p=7 and p=13 show. The second term also is divisble by 24 and all its divisors for the same reason. In general there need not be more divisors as the examples p=11 and p=17 show. Thus p^2-1 is guaranteed to be divible by 24 and all its divisors that's the best we can do
@viesic
Ай бұрын
p=7
@wjudee
Ай бұрын
i found (i’m only listing the prime powers): 2^3, 3. i did it in one min so this is just for future me to see if i got em all
@KhanFaisal-z7x
Ай бұрын
Hi, I am from India 🇮🇳. Can you explain how 2,4 and 8 has come as divisors of p^2-1. What is mod 4 meaning in the solution, please make a detailed video on the concepts used to solve the problem. Love and regards.
@asparkdeity8717
Ай бұрын
This is the best and easiest way of showing divisibility by all these numbers, good job!
@hedgehog11953
Ай бұрын
@@asparkdeity8717 thanks! More stuff like this to come
@etramulnn785
Ай бұрын
sin(x) is opp/hyp
@hedgehog11953
Ай бұрын
@@etramulnn785 can’t believe I just watched myself do that - cheers for pointing that out
@arekkrolak6320
Ай бұрын
it is quite obvious it must be divisable by 2, 3, 4 and 8 - this follows directy from (a+b)^2 = a^2 + 2ab + b^2; also there can be no more divisors as the first three results devided by 24 give prime numbers
@MrRyanroberson1
Ай бұрын
if you watch the powers of 3 and powers of 2 in the factors of numbers, they follow a pattern: 2, 4, 6, 4, 2, 12, 2, 4, 6, 4, 2, 12...; notice since all primes are 6k+/-1 that p+1 and p-1 will be one of those multiples of 6 and then one of the adjacent evens. the product of those is always at least a multiple of 24, so p^2 = 24m + 1 for all p > 3
@MrGeorge1896
Ай бұрын
All prime numbers greater than 3 are either 6n + 1 or 6n - 1 e.g. 11 = 2 * 6 - 1 and 31 = 5 * 6 + 1. So (p + 1) (p - 1) is either (6n) (6n - 2) or (6n + 2) (6n) which can be simplified to 12n (3n ± 1).
@jimmoore3767
Ай бұрын
point less question
@davidbagg9289
Ай бұрын
A desperately pedantic point, but you missed 6 and 12 as solutions. A don may not have faulted you because you did the thinking on 2, 3, and 4, and applied the necessary logic to get to 24.
@hedgehog11953
Ай бұрын
@@davidbagg9289 I wasn’t looking for each of the factors I was simply looking for what’s the largest we could do, but yes 6 and 12 are factors, 6 being a more famous result since all primes are either 1 more or less than a multiple of 6 (this would be one way of figuring that out), and 12 would be the symptom of 3 * 4. Then again, you are correct we should have listed the factors we had also worked out!
@riccardofroz
Ай бұрын
Why can't p be 5? It would be (5-1)(5+1) being equal 24.
@hedgehog11953
Ай бұрын
@@riccardofroz I think p=5 is also correct, an oversight I made
@jrpulzify4518
Ай бұрын
It says p is bigger than 6 buddy
@riccardofroz
Ай бұрын
@@jrpulzify4518 I mean, "why the problem does not allow p to be 5", since it maintains the property that the question wants to be proven.
@MagnusIngemann
Ай бұрын
I love how this is so true, but to complex to remember
@koenth2359
Ай бұрын
These twelve integers (and their negatives) are always factors of p^2-1, (but for p<19 duplications may occur). 1, 2, 4, 8, (p-1)/2, (p+1)/2, p-1, p+1, (p^2-1)/8, (p^2-1)/4, (p^2-1)/2, p^2-1
@RexxSchneider
Ай бұрын
Why isn't 3 on your list?
@koenth2359
Ай бұрын
@@RexxSchneiderCorrect, 3, 6, 12, 24, (p^2-1)/24, etc should be too, Overlooked them. So, for high enough prime, we found upto 40 integer divisors of p^2-1. Now it's upto you to find out after which prime no overlap may occur!
@archangecamilien1879
Ай бұрын
Certainly 3, lol...because p-1, p and p+1 are 3 consecutive integers...
@archangecamilien1879
Ай бұрын
...so, p being prime, one of p-1 or p+1 is divisible by 3, and p^2 - 1 = (p+1)(p-1)...it's also divisible by 2, etc...and being divisible by 2, one of them is also divisible by 4, because of p-1, p, p+1, p+2 (you could also do p-2, p-1, p, p+1), one of them is divisible by 4, but since p, p-2 and p+2 will all be odd, lol, p being odd, then the multiple of 4 has to be one of p-1 or p+1...
@archangecamilien1879
Ай бұрын
...to determine the remaining factors, lol, one need only look at two examples, lol...like 48=7^2 - 1, and 120 = 11^2 - 1...what factors do they have in common besides 3 and 4 (which I just proved must be factors in common)...hmm...looks like they are both divisible by 8...48 = 8x6=2^4 x 3, and 120 = 2^3 x 5 x 3...hmm...so the factors in common are 8 and 3...does that still work for p=13?...13^2 - 1 = 168, is that divisible by 8?...yes, it is...hmm...
@archangecamilien1879
Ай бұрын
So I just need to prove that p^2 - 1 is always divisible by 8, that's the only possibility after 3 and 4...
@archangecamilien1879
Ай бұрын
I'm so stupid, I already proved it...if one of p-1 or p+1 is divisible by 4, that means the other is divisible by 2, Jesus...I just used that same logic to prove that one of them is divisible by 3...I mean...that's pathetic...QED...the factors are 8 and 3...(by implication, of course, all the products of the divisors, like 4, or 2, or 6, etc)...
@archangecamilien1879
Ай бұрын
...that was a fairly easy question...
@KristofferBrander
Ай бұрын
Why p>6 and not p>4? Does the proof fail for p=5 in any way?
@KristofferBrander
Ай бұрын
And yes, I know that if it holds for p>4 then it holds for p>6 as well. Just wondering if there is a reason for not picking p>4.
@hedgehog11953
Ай бұрын
@@KristofferBrander There is a bit missing from this question that involves p>6, but yes you are right p=5 does indeed follow the rule.
@TheScotty1701d
Ай бұрын
It‘s from the more difficult problem to show, that 240 is a divisor of p^4-1, if p>6 is a prime.
@hedgehog11953
Ай бұрын
@@TheScotty1701d I haven’t come across this problem actually - might have a look into this
@RexxSchneider
Ай бұрын
@@hedgehog11953 It's not too difficult. You get p^4-1 = (p^2+1)(p+1)(p-1). Now we already know that (p+1)(p-1) is divisible by 24, and it's clear that p^2+1 is even. Then we observe that p (if p>5) must end in {1, 3, 7, 9 }. So if p ends in 1, we know (p-1) is divisible by 5. If p ends in 3 or 7, then p^2+1 is divisible by 5. If p ends in 9. then (p+1) is divisible by 5. In each possible case one of (p^2+1), (p+1), (p-1) is divisible by 5. This shows that p^4-1 has factors 24 x 2 x 5 = 240.
@stighemmer
Ай бұрын
In addition: To prove that 24 is the best you can do, look at the smallest two primes > 6, which is 7 and 11. p^2-1 is 48 and 120. These numbers have 24 as their largest common factor. Therefore there is no larger number dividing all p^2 -1 for prime p > 6
@eduardciuca217
Ай бұрын
But if you check for p=13 , you get p^2 - 1 =168, which is divisible by 7 ; Also , for p = 23 , p^2-1 = 528 , which is divible by 11 For p = 37 , we get p^2 - 1 = 1368 , which is divible by 19. This means we get other bigger primes which divide p^2-1.
@shmuelzehavi4940
Ай бұрын
Your proof is incomplete. You have to prove as well that there is no prime number p > 11 , such that the largest common factor of p^2 - 1 with 48 or 120 is smaller than 24.
@stighemmer
Ай бұрын
@@shmuelzehavi4940 My comment started with "In addition:" This was meant to imply that the complete proof included the discussion from the video.
@duckyoutube6318
Ай бұрын
11^2=121 not 120. Does not have a common factor of 24. Whenever you square a number like 11, or 111, or 1111, the sum will always be a palindrome. Such that. 11^2=11×11=121 111^2=111×111=12321 1111^2=1111×1111=1234321
@robertveith6383
Ай бұрын
* which *are* 7 and 11
@dhruvbhatia6808
2 ай бұрын
A better proof for divisiblility of 3 would be taking the prime as 6k +1 and 6k-1 in both cases you would get 3 as a factor
@Vijwal
2 ай бұрын
We can also show this by a simpler proof by using the fact that all primes can be written as 1(mod(6)) or -1(mod(6)) Since p isn't 2 or 3, we can write it as 6k+1 or 6k-1 , by doing p²-1 we get 36k²+12k or 36k²-12k , here by some factorization we can further get: 12k(3k+1) -> 12 is a factor and one of k or 3k+1 is even or 12k(3k-1) -> 12 is a factor and one of k or 3k-1 is even Hence we conclude that for any prime p (≠2, 3) p²-1 is divisible by 24
@hedgehog11953
2 ай бұрын
@@Vijwal I wanted to avoid using the fact that primes are one more or one less than a multiple of 6, it feels more like magic rather than a series of deductive steps that anyone could do. That being said your proof is also perfectly fine.
@tenebrae711
2 ай бұрын
@@hedgehog11953 absolutely agree on this, that's a starter question, and I suppose this video isn't really meant for advanced mathematicians, who know this property, which really is nontrivial to observe
@hedgehog11953
Ай бұрын
@@tenebrae711 Exactly! If you were to then explain to someone why primes are one more or one less than a multiple of 6 you’d then basically explain it like this.
@RexxSchneider
Ай бұрын
@@hedgehog11953 I would explain the property by saying all numbers can be written as one of { 6k, 6k+1, 6k+2, 6k+3, 6k+4, 6k+5 }. But 6k, 6k+2 and 6k+4 are even and can't be prime (for k>0). Similarly 6k+3 is divisible by 3 and can't be prime (for k>0). That means all primes greater than 3 must be of the form 6k+1 or 6k+5, which is 6(k+1)-1. So all primes greater than 3 must be a multiple of 6 plus or minus 1. Is that what you meant?
@chingpongsiu1508
Ай бұрын
Same solution here at the first sight of the problem. I am not a mathematician but a software developer. It is a common trick to speed up finding primes by just testing (6k + 1) and (6k +5), so that each step in the loop advances by 6. When you think about Sieve of Eratosthenes, it is obvious that 6k, 6k+2, 6k+3, 6k+4 are eliminated, as explained by @RexxSchneider above.
@DanDart
2 ай бұрын
I've seen this done on Numberphile with Matt Parker and they resolve that they also have the same answer.
@hedgehog11953
2 ай бұрын
@@DanDart what’s the video called - I don’t think I have seen this video?
@@hedgehog11953It's called "Squaring Primes - Numberphile"
@DanDart
Ай бұрын
The link doesn't seem to have persisted here. It's called "Squaring Primes".
@aryaharikrishnan564
2 ай бұрын
For the consecutive even numbers bit, you can also just say that (p-1) = 2q and (p+1) = 2q+2 so (p-1)(p+1) = 2q(2q+2) = 4q(q+1) and q(q+1) are consecutive numbers so always multiply to make an even number (as if q is odd then (q+1) is even, and odd x even=even, and vice versa) so (p-1)(p+1) = 4 x "some even number" so (p-1)(p+1) is divisible by 8. Similar to the mod argument
@hedgehog11953
2 ай бұрын
@@aryaharikrishnan564 I think I might prefer this reasoning since you don’t really need to introduce any thinking with remainders. Nice 👍
@JESUS_CHRlST
2 ай бұрын
Nice video, I didn’t see that trick with 3 coming but I would have got the rest
@hedgehog11953
2 ай бұрын
When originally thinking about this problem (it was embedded in a BMO1 question) I managed to get the 3 but did miss the consecutive even numbers bit.
@ThomasMeeson
2 ай бұрын
It’s so cool how much you can analyse with deceivingly little information. Great vid
@davidwright8432
Ай бұрын
It's not deceivingly little! Surprisingly so, perhaps. But you aren't deceived - rather, provided with all you truly need to get started!
@ThomasMeeson
2 ай бұрын
Great vid!
@ThomasMeeson
3 ай бұрын
You explained that very well thanks! It would be great if you could do some more interview questions
@hedgehog11953
3 ай бұрын
Wow, I made this video as sort of a throwaway to see if anyone would even bother clicking on it - didn't expect anyone to actually find it useful! And yes, I did physics and did part II astrophysics (3rd year) so did you have any topic in mind?
@ThomasMeeson
3 ай бұрын
@@hedgehog11953 I was thinking just the most common types of interview questions for a physics applicant
Пікірлер