International Math Olympiad | 2005 Q4 

Just for the record, the problem was phrased differently to this. It asked for all numbers that were relatively prime to all numbers in this sequence. So it was a little harder, as you had to discover that there a member of the sequence that any prime would divide. Source: was there and got 6 out of 7 for this problem.

If you're uncomfortable with fields and inverses mod p etc, here's a slight modification that might feel more natural. Call the number 2^n + 3^n + 6^n - 1= a_n. Now, look at 6a_n. Choosing n = p-2 we get 6a_(p-2)= 3*2^(p-1) + 2*3^(p-1)+ 6^(p-1)-6, which we reduce using Fermats little theorem to 3+2+1-6=0. Now we know 6a_(p-2) is divisible by p, but because p is prime and not 2 or 3, this means p divides a_(p-2). This is the same idea, but the solution may be formulated in a more elementary way. Still requires Fermats Little Theorem ofc

7:40

Wow you uploaded three videos in one day. I envy your passion. Hope you get silver button soon.

Thanks so much for such a great content

there is general n including for any prime 2 and 3 n = φ(6p) - 1 x = 2^n + 3^n + 6^n - 1 6x = 3×2^φ(6p) + 2×3^φ(6p) + 6^ φ(6p) - 6 = 3 + 2 + 1 - 6 mod 6p 6x is a multiple of 6p so x is a multiple of p upd: it works if p is coprime with 2 and 3

I just want to say that I saw your whole number theory lessons, and this is the first one that made me really think and understand about the inverse (-1 "power") numbers.

You don't know how much of a help are you for a student passionate about Maths.

Thanks Michael Penn. God bless you, this videos are hugely educative

There’s a simpler way to prove: 2^(-1) + 3^(-1) + 6^(-1) = 1 ... mod p throughout Without reintroducing p. Using 2x3 = 6 and its multiplicative inverse. You get 2^(-1) + 3^(-1) + 6^(-1) = 3(6^(-1)) + 2(6^(-1)) + 6^(-1) = ( 3+2+1)6^(-1) = 1

Your transitions are always top notch.

Thank you Mike Penn I could not solve it until I saw you use Fermat Little Theorem.

Most fun math channel on youtube. 100k subs soon

Huh... if p=3, wouldn't n=2 be a viable solution as well? 2^2 + 3^2 + 6^2 - 1 = 4 + 9 + 36 - 1 = 48

Fantástico. Esse cara tem uma visão além do alcance. Parabéns. A aplicação do Pequeno Teorema de Fermat de forma modificada foi incrível. Essa é a verdadeira matemática, o uso de truques que fazem o problema ficar fácil. Uma bela solução de um problema de uma competição tão difícil. Resolveu em pouco tempo. Inacreditável. Parabéns.

Wow. That's really beautiful. Thanks as always Michael Penn!

Just found out my algebra professor suggested this problem I can't breathe

Given a right-angled triangle ABC, angle A = 90 degrees. On the BC side, point D is chosen so that the radii of the circles inscribed in the triangular ABD and ACD are the same. It is known that the length of the segment AD is equal to 1 (AD = 1). Find the area of a triangle ABC.

Beautiful. This one was really easy if you knew how to start it.

Yay, i got this one out. Number theory was never my forte. Essentially same as Michael's proof, but without needing the inverse until the end. The other direction i tried without success was to notice the first three terms are in the expansion of (3^n + 1)(2^n + 1) so the expression can be rewritten as (3^n + 1)(2^n + 1) -2, but then i stalled.

Where is the homework??? Mr GPS, (Good Place to Stop)???

Prove that in any right-angled triangle with area 1, the cheviana drawn from the vertex of the right angle and dividing the original triangle into two triangles with equal inscribed circles has length 1.

Doesn't 3 also divide the n=2 case?

First show 2^-1 = 3^-1 + 6^-1 mod p then 2^(p-2) + 3^(p-2) + 6^(p-2) = 2^-1+3^-1+6^-1=2^-1+2^-2 =2(2^-1) = 1 mod p

Since F(p) is a (finite) field, 6^-1 can be factored out of 2^-1 + 3^-1) + 6^-1 directly, giving: 2^(p-2) + 3^(p-2) + 6^(p-2) - 1 = 2^-1 + 3^-1 + 6^-1 - 1 = 6^-1 (3 + 2 + 1) - 1 = 6^-1 * 6 - 1 = 0 (mod p) More generally in any field, a^-1 can be expressed as 1/a and rational expressions can be manipulated as they would be in Q, as long as the denominators aren't 0 (mod p). So, the latter part of the above equation could equally well be expressed as: 2^-1 + 3^-1 + 6^-1 - 1 = 1/2 + 1/3 + 1/6 - 1 = (3 + 2 + 1) / 6 - 1 = 0 (mod p)

You make it seem so easy.

6(2^-1)= (3)(2)(2^-1) = 3 mod p and 6(3^-1)=(2)(3)(3^-1)= 2 mod p, hence by subtraction 6^(2^-1)-6(3^-1) = 3-2 = 1, so 6(2^-1-3^-1)=1 Therefore 2^-1+3^-1 = 6^-1

Extremely good

Thanks sir

Muchas gracias ☺😷😷😶

It's nice. It's very nice!

p=2 works because the expression is always even (even + odd + even - odd) for any value of n. p=3 works with any even n because both 3^n and 6^n ≡ 0 mod 3 and 2^2m ≡ 4^m ≡ 1 mod 3. The simplest case is n=2 when the expression is congruent to 2^2 - 1, which is divisible by 3. For the general case where p >3, we can reduce the amount of working with negative indices by simply considering the expression: (3*2).(2^(p-2) + 3^(p-2) + 6^(p-2) - 1) mod p = (3*2(p-1) + 2*3^(p-1) + 6^(p-1) - 6) mod p ≡ (3*1 + 2*1 + 1 - 6) mod p, using Fermat's Little Theorem ≡ 0 mod p, showing that (2^(p-2) + 3^(p-2) + 6^(p-2) - 1) ≡ 0 mod p, since 6 is not congruent to 0 mod p for p>3. Hence n=(p-2) is a solution to the problem. Although completely equivalent, that just seems a little "cleaner" that the video's explanation.

The best Master

2^n+3^n+6^n-1=[[[ 2n+3n+[6n/1=6n]=[ 2n+3n+6n]=[[2+3]=[6+6n]=[ 6+6]=12 tada n=1

Yes, of course. Why didn't I think of that?

Sir 1/2, 1/3, 16 are very very special number in this property question was asked in ioqn 2020 of 5 marker

Couldn't you more simply use that 1/2 +1/3 + 1/6 -1 is 0 and 0 is a multiple of every number?

bruh I spent 30 minutes trying to find some kind of relationship with adding modular inverses, and even tried proving that it was possible for at least one to be congruent to -2 (mod p) and I completely forgot that 1/2 + 1/3 + 1/6 = 1.

For any even number n: n>0, 2^n+3^n+6^n-1 is a multiple of 3 (and not for any odd n). For any odd number n: 2^n+3^n+6^n-1 is a multiple of 5 (and not for any even n). You can easily demonstrate this by enumerating all cases mod 3 and mod 5 respectively. Hence there will not be an n such that 2^n+3^n+6^n-1 is a multiple of 15. So you can prove that there will not be an n to make 2^n+3^n+6^n-1 a multiple of k for all natural numbers k. So it is true for primes, not for arbitrary natural numbers.

Amazing proof.

In fact for p=3 any even value of n works

can someone explain the whole using the ^-1 thing, fractions don't always have the same properties as integers. I feel like I'm missing something here.

This problem uses a lot of casework.

Sir pls bring a course for ioqm and inmo pls there need 🙃🙃

very nice :-)

Well kick idea that is an EVEN number, and primes except 2 are all odd, so they will be at least 2XpXm where m any natural number

Maybe I missed it, but you had 4 terms yet when you factored the 6 to the p-2 out of the equation, but later you had only 3 terms. I am trying to understand what happened to the 2 to the p-2 term. I thought that term, once the 6 to the p-2 was factored out, would yield a 1/(3 to the p+2) in the place as one of the four terms. Pardon me if I am wrong. Michael is an excellent mathematican, so I feel completely awkward in pointing out anything that looks curious. :-) Thank you.

Good

7:38 so for p primes greater than 3, there is only one solution for n being equal to "p-2" ??

What is q in 1:24

I’m wondering now if for any two different primes p and q there is an n such that p^n -1 is divisible by q

Wow Imo in 7 minutes

My understanding of multiplicative inverses (mod p) is that, for example, the inverse of 3 (mod 7) is 5, because 3·5 is congruent to 1 (mod 7). But Michael seems to be using a different version of inverses here, where the inverse of 3 is 1/3. My number theory isn't so advanced...can someone help me clear this up?

but you already have that 2^-1+3^-1+6^-1-1 is congruent to 0 mod p

Solve INMO problem

I've never studied university mathematics so I tried to understand this.... After messing around with Fermat's little theorem, I finally understood intuitively why it works when a and p are coprime so I understood that part okay, what completely confounded me was the multiplicative inverse part. I guess I understood what the multiplicative inverse "means" but I have no idea why 1/2 + 1/3 + 1/6 = 1 mod p ; like why would that even work? Why can the multiplicative inverse even be written as fractions and why on earth do they behave as fractions would? I was thinking that maybe it's necessary to have studied some form of number theory at university but that can't be the case because this is an IMO question for high school students. Is all this stuff intuitively obvious to you guys (i.e am I just not smart enough to do this or is this way above my intellectual level) or does this require some form of formal study of number theory to fully grasp? I find it astounding and quite difficult to believe there are people who can just look at this once and understand immediately why it works. I've sat here for around half an hour trying to understand why the multiplicative inverse thing works, why on earth the "inverse" can even be written as a fraction etc. with no success. I tried to look at a few comments and there was talk of fields, but do high school students even know what a field is? I've never even heard of it before. Anyway, I'd really appreciate some advice and resources for people who aren't as smart as IMO people. I really want to understand this (as in really understand deeply and intuitively, not just learn the formula and apply it perfunctorily and mechanically). I'm just in disbelief that there are high school kids my age or younger who can do this, and more importantly, who understand deeply and profoundly how and why all of this works intuitively. It took me over half an hour of deep thinking to even get an intuitive sense of why Fermat's little theorem actually works .... should I just wait til I get to university or is there something I can read to understand this? Or should I just accept this is way beyond my level / IQ. Thanks for your help.

To prove that is equal to 0 couldn't you just do (under mod p) x=(2^-1)+(3^-1)+(6^-1)-1 6x=3+2+1-6=0 x=0 (Since 6≠0 due to the prime being neither 2 nor 3). It really seemed like you were leasing to using this and then you just proved it in a really complex way

At 4:25 Yeah..... but at 4:29 What?! I have never done that...!

Who have some books in number theory

This is pretty clumsy... 1/2 + 1/3 + 1/6 = 1 in any field of characteristic not 2 or 3 as it is in the rational numbers, with the same proof.

Wow this video has no dislikes so far.... rn

👍👍👍👍👍

First, at 2:15, this is wrong: for p = 2, if n = 0, 2^n and 6^n are not even numbers! Anyway, even n = 0 works. For p = 3, one can do much simpler: assume n ≥ 1, so that 2^n + 3^n + 6^n − 1 ≡ 2^n − 1, then obviously n = 2 works. Concerning p ≥ 5: One has 1/2 + 1/3 + 1/6 = 1 in any field where 2 and 3 are invertible (thus 6 is invertible too, with (1/6) = (1/2)·(1/3)), because the proof (multiply both sides by 6 and simplify the left side) involves only field operations, so that you do not have to consider Q in particular. Hence the result.

for p=3 => n=2 is much easier...

At 2:54, you could also use n equals 2 for p equals 3..since you get 48 which is 16 times 3..anyone else see this?

top

So the trick is simple: Want a natural number? Take an integer and turn it to natural.😎

T

For all primes p, p /[2^(p-2)+3^(p-2)+3^(p-2) - 1], hence we can conclude there there are an infinite number of twin primes. Proof: 6(2^-1)= (3)(2)(2^-1) = 3 mod p and 6(3^-1)=(2)(3)(3^-1)= 2 mod p, Hence by subtraction 6^(2^-1)-6(3^-1) = 3-2 = 1, so 6(2^-1-3^-1)=1 Therefore 2^-1 - 3^-1 = 6^-1 (mod p) hence we have shown 2^-1 =3^-1 + 6^-1 Using FLT 2^(p-1) = 1 => 2^(p-2) = 2^-1 (mod p) Similarly 3^(p-1)= 1 => 3^(p-2) = 3^-1 and 6^(p-1) = 6^ -1 => 6^(p-2)=6^-1 (mod p) [2^(p-2) + 3^(p-2) + 3^(p-2) - 1] = [(2^-1+3^-1+6^-1-1] = (2^-1 + 2^-1 - 1] = (2^-1)x2 - 1 = 1 - 1 = 0 (mod p) Therefore p divides 2^(p-2) + 3^(p-2)+6^(p-2) - 1, for all primes p. Therefore there will always be a pair of primes p -2 and p such that p divides 2^(p-2)+3^(p-2)+6^(p-2) - 1 No matter how large p is there exist p - 2 for this to be true. Hence there are INFINITE TWIN PRIMES. Is this not an unsolved problem? Examples:73 divides 2^71 + 3^71 + 6 ^71 and 103 divides 2^101+3^101+6^101 have verified using Wolfram Alpha

I'm going to be honest. These hints didn't help me.

Watch this video: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-yBvsNueXIw4.html

good place to stop 7:40

Good

T