Problem Solving | Techniques from Number Theory

[@Bodyknock]

7:46 When constructing that table of squares it’s actually helpful to, instead of list numbers 0 to 8, list the number -4, -3, -2, -1, 0, 1, 2, 3 and 4. Notice that the negative numbers in that list are congruent to 5, 6, 7 and 8 respectively, so you’re constructing the same equivalent list of residues. But, the key thing here is that obviously -3 squared equals 3 squared, -4 squared equals 4 squared, and so on. Thus you get a natural symmetry in this list of squares - the upper part of the list is just a reflection of the lower part. It’s just a nice way to view the squares in modular arithmetic.

[@sharathpr42]

Easy solution to problem 1: The GCD must divide n² +100 as well as (n + 1)² + 100 .. => it also divides their difference (n + 1)² + 100 - (n² + 100) i.e. 2n + 1 Note that 2n + 1 is always smaller than n² + 100.. Therefore the max GCD is itself 2n + 1 such that it satisfies the condition 2n + 1 | n² + 100 => 2n + 1 | 4n² + 400 => 2n + 1 | (2n + 1)² - (4n + 2) + 400 + 1 => 2n + 1 | 401 For maximum GCD, 2n + 1 = 401 n = 200 and max(GCD) = 401

[@littlefermat]

Nice video! Number theory is definitely one of the most fun types in math Olympiad. I actually see that the main subtopics in NT are (divisibility - mod - Diophantine equations- quadratic residues) Of course there lots of other things as well...

[@bebarshossny5148]

Great to see you here

[@goodplacetostop2973]

0:24 I hope whoever it was, that person is okay 28:20 All of a sudden, a video unlisted for months now goes public...

[@AKhoja]

Who are you and why are you so obsessed with Michael?

[@goodplacetostop2973]

@@AKhoja I’m just a memer that runs this joke account for 10 months. That’s about it

[@goodplacetostop2973]

HOMEWORK : Find all positive integers n which satisfy the following two conditions: (i) n has at least four different positive divisors; (ii) for any divisors a and b of n satisfying 1 < a < b < n, the number b - a divides n. SOURCE : 2010 Middle European Mathematical Olympiad

[@clark1708]

n can't be odd, since all its divisors would be odd but the difference between any two odd numbers is even. Therefore n has the factors n/2 and 2, which means n/2-2 is a factor. This forces 3*(n/2-2)

[@goodplacetostop2973]

​@@clark1708 SOLUTION The original solution really tried hard about n odd, but Clark basically said it in one sentence. That was a proof by contradiction, you ended up with n = 2 x whatever, n being odd. Here's the part for n even : "For n even, n= 2x for some integer x. Then x−2 divides n. Any divisor of n smaller than x = n/2 is at most n/3. Therefore, x−2 ≤ n / 3, yielding x ≤ 6. Checking all possibilities for x, we arrive to three new satisfactory values of n, namely, 6, 8,and 12."

[@ashrafyaseer4769]

If you read my comment, then I request you to make some videos like this on combinatorics

[@Nah_Bohdi]

Concured, indubitably.

[@divyanshtripathi7867]

Thank you for this problem solving techniques in number theory.

[@ramakrishnasen4386]

This is like the summary of all your past number theory videos. "Now thats a good place to stop!"

[@manuel3494]

During the heat death of the universe, i can just imagine at the last picosecond of this existence his voice saying "and that's a good place to stop"

[@tomatrix7525]

It’s a good summary but it’s nit even close to covering everything. Everything would take like 24 hours straight to explain

[@nl1201]

27:31 When I was minding my own business and suddenly my brain think a cringy moment I did 10 years ago

[@Zxv975]

I always struggle to remember Fermat's theorem, but writing it as a^p ≡ a mod p It makes perfect sense and is borderline obvious. As you multiply a by itself it takes on a different value in the range 0-(p-1), and only after p multiplications does it return back to where it starts from.

[@galo5818]

Yeah, but that doesn't answer the question of why it does not work for all numbers instead of only for prime numbers.

[@Zxv975]

@@galo5818 same logic as ax mod n. If n is not a prime then multiplying a by an arbitrary constant x will result in a value that's in the range the range 0-(n-1), but it's not at all guaranteed to be unique. Here we are adding a to itself multiple times instead of multiplying, but the underlying principle remains intact and relies on primality. Remember, I'm suggesting a rephrasing, not a self-contained proof. Rewritten in this way it's clear what the intuition behind the theorem is, and a proof can clearly follow if one understands the additive periodicity of modulo. Prime clearly implies maximum additive periodicity, but perhaps less clear is that it implies maximum multiplicative periodicity. This theorem is just the statement of that less obvious fact.

[@miserepoignee9594]

Regarding the last question, it is an open problem to find a general expression for an arbitrary number as a sum of three cubes, nor is it known whether every number congruent to something other than 4 or 5 mod 9 has a solution. Numberphile has a series of videos where they talk about these problems. While most numbers admit relatively tame solutions, there are a handful of numbers even under 100 that require numbers many orders of magnitude greater in their solutions.

[@level8695]

Straight up olympiad tutoring Revolutionary stuff

[@KoshiPrime]

Your number theory videos are one of my favourites! 😊

[@googool.3769]

√-1 also need that

[@maharanirani54]

I'm kinda struggling for number theory problems, so I've been waiting for this kind of video cz I really need it for preparing contest. And I just can't believe that this video comes at the right moment when I really need it! I have watched many videos of number theory problems from this channel. Thank you very much for your help, Professor🙏.

[@reshmikuntichandra4535]

Thank you so so so so so much for this! I really needed it,and it'd be really helpful if you could make similar videos on the other topics of Math Contests (Geometry, Combinatorics, Functional Equations and others.....)

[@notananimenerd1333]

You are on VOS right?

[@reshmikuntichandra4535]

@@notananimenerd1333 Yeah😁

[@danielferdiansyah]

what a great video, it really helps for the beginner!

[@farissaadat4437]

17:30 Does anyone have a more full explanation of why x and y ought to be linear in n?

[@Why_Alex_Beats_Bobbie]

In principle it doesn't. We can choose it to be whatever we want. However, we can notice that if x and y are linear in n, the polynomial of n will be of degree 3 (ie. in general the highest power of n will be 3). This means that we would need 4 degrees of freedom to fully determine the polynomial (ie. "force" it to be equal to zero). However, each linear term gives us 2 degrees of freedom and since 2+2=4 the degrees of freedom match perfectly which means our system is likely to have a solution.

[@robertgerbicz]

Much easier way: let d=gcd(a(n),a(n+1)) | a(n+1)-a(n)=2*n+1 then d | 4*(n^2+100)-(2*n+1)*(2*n-1)=401 and clearly for n=200 we have d=401, what we needed.

[@karthikkrishnaswami3164]

Precisely. That's exactly what I did too!

[@hk3676]

I think I’m slow, how does the second line follow from the first

[@hk3676]

And why 4*(n^2 +100), why specifically 4? Is it to cancel with the rest of the terms? Is it possible you could just use a larger number and hence d will have to divide a larger number? Thank you

[@robertgerbicz]

@@hk3676 From the first line d|2*n+1 precisely d=d(n) in the video, but d=gcd(a(n),a(n+1)) it means that d|a(n)=100+n^2 and we already know that d|2*n+1. Hence d divides any linear combination of these two terms: d | 4*(100+n^2)-(2*n-1)*(2*n+1)=401. The goal is ofcourse to minimize this expression, what we got 401 is the minimal in Z[x], you could get only larger OR not constant polynom, like in my first line I've gotten only that d | 2*n+1, that is weak, because we search for max(d(n)) and 2*n+1 goes to infinity. That's why we needed that 2nd line. Any yes we need that 4 multiplier, say choose 2*(n^2+100)-(2*n+1)*n=-n+200 that has degree=1.

[@thekingadomas1656]

It's scary enough when there's 3 variables. The man literally intruduces like 7 variables :D

[@muhammadmushfiqurrahman8125]

I didn't get 17:51. How do you know x,y are linear?

[@matti1610]

Thank you so much!! Really helps.

[@davidemasi__]

What a video! However, I'd like to know better how to understand quickly I have to use 9 in the last exercise (if there is a trick)

[@adityansingla5656]

Why is this video link only?

[@petersievert6830]

Was not published apparently when you first saw it. Now other ppl wonder, how you were able to watch and comment it one month ago :-D (apparently they appear on some ppls playlists anyway)

[@tomkerruish2982]

0:23 What was that noise?

[@vokuheila]

He ate too much beans last night

[@manuel3494]

Is bezouts thereom the same as the chinese remiander thereom?

[@advaykumar9726]

No

[@timetraveller2818]

NO

[@themathsgeek8528]

Nope

[@themathsgeek8528]

Bezout's theorem follows from euclid division algorithm (expresses the gcd as linear combination of the numbers) while the crt is a theorem to solve a system of congruences with coprime modulos..

[@swastiksanyal4249]

How did you guess that 401 is to be the solution. Everytime when I do number theory stuffs I stuck at this point of claiming a guess.

[@natevanderw]

Nice work

[@krisnendubiswas3374]

quite helpful!

[@goodplacetostart9099]

Good Place To Start at 0:24

[@masoomladka8017]

Thanks ❤️❤️👍🙏🙏

[@hustler2001]

please make same for calculus

[@DeepakKumar-qg3df]

Plz continue with number theory

[@caneeducation]

Nice sir....

[@AaronRotenberg]

Is this video supposed to be link-view-only? It's the only such video on the playlist and that's probably why it has so few views.

[@helo3827]

I was okay with the second problem but the first problem made my head spin.

[@Nnm26]

yeah, wtf was that. There has to be an easier solution right? There's no way they would put that in the AIME if it's that long.

[@tomatrix7525]

@@Nnm26 I haven’t tried it for myself but there’s likely an easier solution and almost definitely an alternative one. I know Michael tends to present longer, harder or more convoluted solutions sometimes. That might be to keep it challenging and interesting for himself thouh, not sure

[@trueriver1950]

0:26 you say you have a play list where you cover everything in number theory? Really? I am surprised that a finite play list can cover every possible result, lemma, conclusion, and theorem. I would be even more surprised if you have a play list of infinite length. ;) lol

[@trueriver1950]

Corollary: an infinite playlist would not have a good pace to stop

[@themathsgeek8528]

Loll

[@serdarbozdag3749]

For the first one, division algorithm easily solves it.

[@ethanjensen7967]

24:20 local global principle again. :)

[@trueriver1950]

My preferred definition of a prime number is that it is an integer with exactly two distinct positive factors. All compound numbers have more than two distinct factors. One has exactly one positive factor and is this excluded. Zero has an infinite number of positive factors, as zero focused by any positive integer leaves a zero remainder. I'm not aware of any one else using this definition, which if they have I discovered independently. The reason I like it is that it makes the exclusion of 1 from the list of primes be consistent rather than a special case. I'd appreciate comments from number theory fans. Are there any drawbacks to my definition (other than novelty)? Has someone else already proposed it?

[@kouverbingham5997]

please make a video about how we dont know whether pi+e is rational or not, and how pathetic that is

[@mikegallegos7]

...my brain hurts, tonite ...

[@scienceandnature869]

a= golden ratio (φ)= (1+√5)/2 , b= golden ratio conjugate (Φ)= ( √5 - 1 )/2 , My new formula's We know, beta [ m , n ] =[ Γ(m)Γ(n) ]/ [ Γ(m+n) ] 1) Beta [ b, 1] = [ Γ(b)Γ(1) ]/ [ Γ(1+b) ] = Γ(b)/Γ(a) = [ 2 Γ(2b) ]/ [ Γ(a+b) ] = [ a Γ(2b+1) ]/ [ Γ(a+b)] = a 2) Beta [ a, 1] = [ Γ(a)Γ(1) ]/ [ Γ(1+a) ] = Γ(a)/ Γ(a^(2)) = [ -2 Γ(-2b) ]/ [ Γ(-a-b) ] = [ b Γ(1-2a) ]/ [ Γ(-a-b)] = b 3) (a)! = a * ( (b)! ) 4) (b)! = b * ( (a)! )

[@harshitkumar9708]

Do you not feel there are too many ads. Like 10 ads for a 30 min video 😑

[@joshuaisemperor]

Wait it only takes hour and hours to learn a lot of things in number theory? I thought it took months at least... :P

[@gammastrain5289]

Solve math problems from codeforces they are pretty cool🔥

[@kevinmae14]

can someone give me a beautiful title about this topic

[@prathmeshraut1616]

I am Time traveller