It’s so cool how much you can analyse with deceivingly little information. Great vid

@davidwright8432

26 күн бұрын

It's not deceivingly little! Surprisingly so, perhaps. But you aren't deceived - rather, provided with all you truly need to get started!

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

28 күн бұрын

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

28 күн бұрын

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

26 күн бұрын

@@shmuelzehavi4940 My comment started with "In addition:" This was meant to imply that the complete proof included the discussion from the video.

@duckyoutube6318

14 күн бұрын

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

11 күн бұрын

* which *are* 7 and 11

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

Ай бұрын

@@aryaharikrishnan564 I think I might prefer this reasoning since you don’t really need to introduce any thinking with remainders. Nice 👍

This is the best and easiest way of showing divisibility by all these numbers, good job!

@hedgehog11953

21 күн бұрын

@@asparkdeity8717 thanks! More stuff like this to come

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

Ай бұрын

@@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

Ай бұрын

@@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.

Nice video, I didn’t see that trick with 3 coming but I would have got the rest

@hedgehog11953

Ай бұрын

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.

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.

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).

I love how this is so true, but to complex to remember

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

I've seen this done on Numberphile with Matt Parker and they resolve that they also have the same answer.

@hedgehog11953

Ай бұрын

@@DanDart what’s the video called - I don’t think I have seen this video?

@DanDart

Ай бұрын

@@hedgehog11953 kzread.info/dash/bejne/jIGfq8t_o5abeLQ.htmlsi=RagzEB0Y2UUY19z-

@graemep804

Ай бұрын

m.kzread.info/dash/bejne/jIGfq8t_o5abeLQ.html

@RJSRdg

Ай бұрын

​@@hedgehog11953It's called "Squaring Primes - Numberphile"

@DanDart

Ай бұрын

The link doesn't seem to have persisted here. It's called "Squaring Primes".

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

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

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

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.

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.

These twelve integers (and their negatives) are always factors of p^2-1, (but for p

@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!

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.

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

P = 1 it is ovious

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.

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!

p=7

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...

point less question