This can be observed from symmetry. We only find new solutions if p divides 7^q-2^q and q divides 7^p-2^p. If either gcd(p-1,q)=1 or gcd(q-1,p)=1, then we find the solutions as shown, if both gcd's are>1, we get gcd(p-1,q)=q (since q is prime), hence p>q, but from the symmetric argument q>p, hence contradiction.
This reasoning might be backwards. Michael's case 1 was good because it assumes p divides 7^p-2^p, and arrives at the fact that p=5. That way when he does case 2, he can assume p divides 7^q-2^q
@@angelmendez-rivera351 4 cases 7^(n+1)-2^(n+1) and so on, you always have a 5 at the end and it being that we're looking for primes means that we have a 5.7-2=5 9-4=5,3-8=-5, 1-6=-5
@@angelmendez-rivera351 you know that every 4 natural numbers you end up with the same last digit, then it's an easy proof that it ends with a 5, making it divisible by 5.
@@munchenmunchen3042 We're working in Z[p], so it is ok. Notice that p!=2 so we could divide by 2 in Z[p] ring. [if you want to see an integer here: 7/2 == 7*(p+1)/2 mod p]
@@nournote This is the multiplicative order, see: en.wikipedia.org/wiki/Multiplicative_order. The order divides p-1 (in general case divides eulerphi(n), but here n=p prime).
You can spot 5 being a divisor of p or q from the fact that 7^x - 2^x = (7-2)*(7^(x-1) + 2*7^(x-2) +... + 7*2^(x-2)+ 2^(x-1)). This is true for both p & q. So then you can find the prime factors of 7^5 - 2^5, one of which is definitely 5 being 7 minus 2. 16775 is indeed divisible by 5 which gives 3355 which incidently is also divisible by 5 and also by 61 and 11. Hence solutions (5,5), (5,11) & (5,61). Due to the symmetry of the original formula (11,5) & (61,5) are also solutions.
Sadly, the wording of the problem does not preclude p = q . So if we let p = q = 1, then (1,1) also works since pq =1, and the numerator of 25 is divisible by 1. The set of *all* (p,q) which satisfy the expression and conditions therefore includes the mostly trivial instance of the primes (1,1).
@@wowZhenek Thanks for the correction, and yes, by restructuring the operational definition " A number divisible only by 1 and itself " and requiring that 1 be a number, 1 is not a prime number. Evelyn Lamb gives an interesting history & definition in her article: "Why Isn't 1 a Prime Number?", Evelyn Lamb SCIENTIFIC AMERICAN, April 2, 2019 . Her suggested definition of a prime, "p" is: "The number p cannot be written as the product of two whole numbers, neither of which is a unit" This of course, reduces to the operational definition and excludes 1 from the primes without begging the question. Just out of curiosity, which definition did you learn?
@@Mathblade I am a simple man, my dude. I learn what I was taught in school. Tens of years ago. I don't know whose definition it was or why, all I know is that 1 is not a prime, for now.
Without having to introduce new variables, when having 7^q≈2^q(p), then 7^q*((p+1)/2)^q≈1(p), then the order mod p of (7(p+1))/2 has to divide q, so it has to be q (if it was 1, then p=5). But the order divides φ(p)=p-1, therefore q
So....gcd(p-1, q) =/=1 .... how do we know that it only works when p=3 and q=2 - how can we know so easily? How do we not know that there isn't a solution in significantly higher numbers?
The second part is much too complex. Obviously, q ≠ 2. One has 7^p ≡ 2^p mod q, thus (7/2)^p ≡ 1 mod q. Assuming p ≠ 5 (p = 5 is the first part), the order of 7/2 is > 1, thus the order of 7/2 is p, so that p < q. Similarly, q < p. Thus this second part gives no other solutions.
Hi, Michael! Thanks for the video! I think you've missed (5;25) pair at 4:55 mark - we have one five from the '5' term and one five from (7^q-2^q) term. Wolfram Alpha says this is a valid solution.
How do we know that in the subcase N°1, there does not exist 2 very big prime numbers p and q other than 2 and 3, such that the gcd(p-1,q) is not equal to 1 ?
I programmed this and got one 'normal' looking answer. Then it spat out every answer where the integer is > 10^16, which from what I know of this type of problem and how R works I assume are not real answers. Time to find out if my pair was correct.
@@angelmendez-rivera351 This channel rarely has solutions that reach double digits, but that makes me wonder what the largest number featured on one of these problems is.
Beautiful Number Theory Problem and equally beautiful solution but I hope Mr.Penn will do some combinatorics problems in the future..It will be really fun
Powers don't work like that in modular arithmetic; they are horrendously non-invertible. The behavior of roots in modular arithmetic is a very complicated question. Even the question square roots in modular arithmetic require some undergrad-level machinery to get going. Here's an easier example. 17^3=5^3mod(7), but does 17=5mod(7)? No.
There is a problem... Let gcd(p-1,q)=d then d|p-1 d|q this means either d=1, perfectly possible. Or d=q... If d=q then, q|p-1, If q=p-1, then (3,2) the only solution but if not then... *Wait... You are RiGHT!*
Isn't case 1 just a subcase of case 2's subcase 2? I think all you really need is to first show that it's the case that gcd(p-1,q)=1 and just do it from there.
Micheal there are a theorm sayd if (A+b)^p _A^p _b^p) If p is prime then all coefision is divisible by p except A^p and b^p And that why we minus him I solved a solution p=q=5 by this method and i think i proved too Im not sure It always work !!!!!!!!!!
@@angelmendez-rivera351 first consider p=q Then we get (7^p _2^p)^2/p^2 Then we can ignore the square power We want( 7^p_2^p)/p To be integer We can right this at this form (7_2)^p Minus or plus some stuff but by this theorem all of that stuff is divisible by p then we can ignor We want 5^p /p There for there are one possiblity which is 5 beacaus p is prime and only 5 can divide 5^p
I would do your case 2 a little differently. To negate case 1, we can assume p divides 7^q-2^q AND q divides 7^p-2^p, for p not equal to q. Then 7^q=2^q mod p. It's clear from this that p cannot be 2 for we would get 1=0 mod p, and therefore neither can q. Moreover, we already took care of the p=5 case, so we can assume p is odd and not 5. Then we can find integers a, b, c, d such that 2a+pb=1 and 2c+qd=1. Then 7^q=2^q mod p implies: (7a)^q=(7^q)(a^q)=(2^q)(a^q)=(2a)^q=(1-bp)^q=1 mod p If k is the least positive integer such that (7a)^k=1 mod p, then k must divide q and k must divide p-1 (see lemma). Since q is prime, k=1 or q. If k=1, then 7a=1 mod p, so 7=2 mod p which implies p divides 5, so p=5 (a contradiction). If k=q, then q divides p-1, which implies q
Hey can anyone help me with this problem on linear algebra it will be appreciated Let A , B be n x n matrices with entries from complex numbers such that A and B are Markov Let C = AB For i,j between 1 and n If |a_i,j|
@@bsmith6276 I get - infinity if the question is lim as x ==> + inf of x^2 * [ e^(1/x) - e^(1+1/x) ], since that goes to inf^2 * (e^0 - e^(1+0)) = inf^2 * (1- e), but if the question is lim as x ==> + inf of x^2 * [ e^(1/x) - e^(1/x) + 1], then that goes to inf^2 * 1 = + infinity, but if the question is lim as x ==> 0+ of x^2 * [ e^(1/x) - e^(1/x) + 1], then that clearly = 0, but if the question is lim as x ==> 0+ of x^2 * [ e^(1/x) - e^(1+1/x)], then that = lim as x ==> 0+ of x^2 * [ e^(1/x) - e^(1/x) * e] by exponent rules, which then = lim as x ==> 0+ of (1 - e) * x^2 * e^(1/x) = (1 - e) * lim as x ==> 0+ of e^(1/x) / x^(-2) = (1 - e) * lim as x ==> 0+ of [-e^(1/x)/x^2] / [-2*x^(-3)] by L'Hôpital's Rule = (1 - e) * lim as x ==> 0+ of e^(1/x) / [2*x^(-1)] = (1 - e) * lim as x ==> 0+ of [-e^(1/x)/x^2] / [-2*x^(-2)] by L'Hôpital's Rule again = (1 - e) * lim as x ==> 0+ of e^(1/x) / 2, which finally goes to - infinity.
gcd(p-1,q)>1 has infinite solutions!!!
This is correct! How can we fix this step?
This can be observed from symmetry. We only find new solutions if p divides 7^q-2^q and q divides 7^p-2^p. If either gcd(p-1,q)=1 or gcd(q-1,p)=1, then we find the solutions as shown, if both gcd's are>1, we get gcd(p-1,q)=q (since q is prime), hence p>q, but from the symmetric argument q>p, hence contradiction.
@@karlpaulparmakson6917 very good explanation!
@@karlpaulparmakson6917 thank you sir
So conclusion that I draw for the case p|(7^q-2^q):
p=2,7 are not solutions .
1st case:2
11:26 Happy Saturday everyone, have a great week-end!
This is your 420th comment in this channel
@@aril_archive6518 420 already? Oh I've never paid attention to that number! That's a meme milestone lol
Greeting from Hong Kong. Love your channel!
I'm from Hong Kong but I can't find this question in either 1999-2000 or 2000-2001 HKMO papers
Could it be IMO preliminary?
never even knew that we had a math Olympiad here, love from hk!
forsenE
always has been.
Surely WLOG p 1 has infinite solutions).
We find that p = 5. q in (5, 11, 61).
Then we invoke symmetry about p
One of the best answers without any thumbs up? Clear and concise without all that noise...
To reach p=5 just use power rules, 7^n-2^n always ends up in a multiplicitive of 5.
This reasoning might be backwards. Michael's case 1 was good because it assumes p divides 7^p-2^p, and arrives at the fact that p=5. That way when he does case 2, he can assume p divides 7^q-2^q
@@angelmendez-rivera351 4 cases 7^(n+1)-2^(n+1) and so on, you always have a 5 at the end and it being that we're looking for primes means that we have a 5.7-2=5 9-4=5,3-8=-5, 1-6=-5
@@angelmendez-rivera351 the 4 cases are calculated much quicker though
@@angelmendez-rivera351 you know that every 4 natural numbers you end up with the same last digit, then it's an easy proof that it ends with a 5, making it divisible by 5.
@@angelmendez-rivera351 it proves that 5 is necessarily an answer
Nice to see one from home, greetings from Hong Kong.
Much quicker solution:
the system is symmetric so we can assume that p
But here 7/2 is not integer but to be order it has to be integer
@@munchenmunchen3042 We're working in Z[p], so it is ok. Notice that p!=2 so we could divide by 2 in Z[p] ring.
[if you want to see an integer here: 7/2 == 7*(p+1)/2 mod p]
@@robertgerbicz what does it mean 'to be order'?
@@robertgerbicz thanks
@@nournote This is the multiplicative order, see: en.wikipedia.org/wiki/Multiplicative_order.
The order divides p-1 (in general case divides eulerphi(n), but here n=p prime).
hi from your little fan from hk~~~
I just wanna say I'm glad this channel exists. Great explanations for contest problems. Keep up the good work!
You can spot 5 being a divisor of p or q from the fact that 7^x - 2^x = (7-2)*(7^(x-1) + 2*7^(x-2) +... + 7*2^(x-2)+ 2^(x-1)). This is true for both p & q. So then you can find the prime factors of 7^5 - 2^5, one of which is definitely 5 being 7 minus 2. 16775 is indeed divisible by 5 which gives 3355 which incidently is also divisible by 5 and also by 61 and 11. Hence solutions (5,5), (5,11) & (5,61). Due to the symmetry of the original formula (11,5) & (61,5) are also solutions.
Shoutout from Hong Kong. Great video!
Sadly, the wording of the problem does not preclude p = q . So if we let p = q = 1, then (1,1) also
works since pq =1, and the numerator of 25 is divisible by 1. The set of *all* (p,q) which satisfy
the expression and conditions therefore includes the mostly trivial instance of the primes (1,1).
Pretty sure 1 is not a prime
@@wowZhenek Thanks for the correction, and yes, by restructuring the operational definition " A number divisible only by 1 and itself " and requiring that 1 be a number, 1 is not a prime number. Evelyn Lamb gives an interesting history & definition in her article: "Why Isn't 1 a Prime Number?", Evelyn Lamb SCIENTIFIC AMERICAN, April 2, 2019 . Her suggested definition of a prime, "p" is: "The number p cannot be written as the product of two whole numbers, neither of which is a unit" This of course, reduces to the operational definition and excludes 1 from the primes without begging the question. Just out of curiosity, which definition did you learn?
@@Mathblade I am a simple man, my dude. I learn what I was taught in school. Tens of years ago. I don't know whose definition it was or why, all I know is that 1 is not a prime, for now.
Wanted to suggest obvious answer p=q=1, but then understood something 😂 so yeah, no trivial solutions for us guys
He did say that p and q should be primes.
Really good content as of late. Great work
Greeting from Hong Kong!!!
The second case you can show by like p|7^-2^q and q|7^p-2^p
Is that we assume that p>=q becayse of symmetry
Then p
Without having to introduce new variables, when having 7^q≈2^q(p), then 7^q*((p+1)/2)^q≈1(p), then the order mod p of (7(p+1))/2 has to divide q, so it has to be q (if it was 1, then p=5). But the order divides φ(p)=p-1, therefore q
So....gcd(p-1, q) =/=1 .... how do we know that it only works when p=3 and q=2 - how can we know so easily? How do we not know that there isn't a solution in significantly higher numbers?
a great number theory question
Fans from Hong Kong 🇭🇰 +1 🙌🏻
The second part is much too complex. Obviously, q ≠ 2. One has 7^p ≡ 2^p mod q, thus (7/2)^p ≡ 1 mod q. Assuming p ≠ 5 (p = 5 is the first part), the order of 7/2 is > 1, thus the order of 7/2 is p, so that p < q. Similarly, q < p. Thus this second part gives no other solutions.
I LOVE your “ok.great.” T-shirt. It’s so you!🇬🇧🇺🇸
Hi, Michael! Thanks for the video!
I think you've missed (5;25) pair at 4:55 mark - we have one five from the '5' term and one five from (7^q-2^q) term. Wolfram Alpha says this is a valid solution.
25 is not prime.
How do we know that in the subcase N°1, there does not exist 2 very big prime numbers p and q other than 2 and 3, such that the gcd(p-1,q) is not equal to 1 ?
I programmed this and got one 'normal' looking answer. Then it spat out every answer where the integer is > 10^16, which from what I know of this type of problem and how R works I assume are not real answers. Time to find out if my pair was correct.
@@angelmendez-rivera351 This channel rarely has solutions that reach double digits, but that makes me wonder what the largest number featured on one of these problems is.
Beautiful Number Theory Problem and equally beautiful solution but I hope Mr.Penn will do some combinatorics problems in the future..It will be really fun
There is a combinatorics problem scheduled in a few days!
You meant "future" instead of "feature" , right ?
@@MichaelPennMath Thank You so much Sir
That's a good place to sto
Cant take the qth root on both sides of 7^q=2^q(mod p), only works for x^2 = y ^2 (mod p) iff x = y (mod p) or x = -y (mod p)
Powers don't work like that in modular arithmetic; they are horrendously non-invertible. The behavior of roots in modular arithmetic is a very complicated question. Even the question square roots in modular arithmetic require some undergrad-level machinery to get going.
Here's an easier example. 17^3=5^3mod(7), but does 17=5mod(7)? No.
@@seanziewonzie my bad then. It works for squares, though
@@adrianamor8472
17^2=5^2(mod11) but 17 and 5 are not equal mod 11.
@@seanziewonzie I mean that x^2 = y^2 ( mod p) iff x = y (mod p) OR x = -y (mod p), in the example above 17 = -5 (mod 11)
Note that x^2 = y^2 (mod p) p divides (x-y)(x+y) p divides x-y or p divides (x+y) x = y (mod p) or x = -y (mod p)
Wait (p-1,q)>1 has a bunch of possible solutions! Like (p,q)=(7,3),(11,5)...
There is a problem... Let gcd(p-1,q)=d then
d|p-1
d|q this means either d=1, perfectly possible. Or d=q...
If d=q then,
q|p-1, If q=p-1, then (3,2) the only solution but if not then...
*Wait... You are RiGHT!*
@@TechToppers What if we assume wlog that p is less than or equal to q.
@@justanotherman1114 Hmm... I assumed that earlier in rough work and then I forgot. Lemme try.
Greetings from Hong Kong!
Isn't case 1 just a subcase of case 2's subcase 2?
I think all you really need is to first show that it's the case that gcd(p-1,q)=1 and just do it from there.
Yep, this one was great...
Hmmm! it all boils down to knowing FLT like the back of your hand.
Love from Nepal 😊❤
Like from Hong Kong!
Micheal there are a theorm sayd if
(A+b)^p _A^p _b^p)
If p is prime then all coefision is divisible by p except A^p and b^p
And that why we minus him
I solved a solution p=q=5 by this method and i think i proved too
Im not sure
It always work !!!!!!!!!!
@@angelmendez-rivera351 first consider p=q
Then we get (7^p _2^p)^2/p^2
Then we can ignore the square power
We want( 7^p_2^p)/p
To be integer
We can right this at this form (7_2)^p
Minus or plus some stuff but by this theorem all of that stuff is divisible by p then we can ignor
We want 5^p /p
There for there are one possiblity which is 5 beacaus p is prime and only 5 can divide 5^p
@@angelmendez-rivera351 it work only in this case if you want to p=q
It solutionsss only when p=q and in this case there is one solution
👍👍👍👍👍
@@angelmendez-rivera351 if you want to watch the video watch
"Fool-proof test for primes numberphile"
No bother to solve this problem on the board. Just at a glance for p = 1, q = 1, the result is 25.
nice
Video has 314 likes, so I'm not gonna like it right now
I would do your case 2 a little differently. To negate case 1, we can assume p divides 7^q-2^q AND q divides 7^p-2^p, for p not equal to q. Then 7^q=2^q mod p.
It's clear from this that p cannot be 2 for we would get 1=0 mod p, and therefore neither can q. Moreover, we already took care of the p=5 case, so we can assume p is odd and not 5. Then we can find integers a, b, c, d such that 2a+pb=1 and 2c+qd=1. Then 7^q=2^q mod p implies:
(7a)^q=(7^q)(a^q)=(2^q)(a^q)=(2a)^q=(1-bp)^q=1 mod p
If k is the least positive integer such that (7a)^k=1 mod p, then k must divide q and k must divide p-1 (see lemma). Since q is prime, k=1 or q.
If k=1, then 7a=1 mod p, so 7=2 mod p which implies p divides 5, so p=5 (a contradiction).
If k=q, then q divides p-1, which implies q
Hi, I'm from HK!
Ayyy me too!
@@williamadams137 I'm a Form 3 student
I’m F4
@@williamadams137 F.4 can understand this?
Sure, why not
Hey can anyone help me with this problem on linear algebra it will be appreciated
Let A , B be n x n matrices with entries from complex numbers such that A and B are Markov
Let C = AB
For i,j between 1 and n
If |a_i,j|
I'm affraid p=q=1 is a solution, where is it?
1 isn't a prime.
Hey mecheal
Lim x---》 +&
X^2(e^1/x - e^ 1/x+1 )
A ned plzz 😢
@@angelmendez-rivera351 I assume that means to take the limit to positive infinity. I get a limit of zero in that case
@@bsmith6276 I get - infinity if the question is lim as x ==> + inf of x^2 * [ e^(1/x) - e^(1+1/x) ], since that goes to inf^2 * (e^0 - e^(1+0)) = inf^2 * (1- e), but if the question is lim as x ==> + inf of x^2 * [ e^(1/x) - e^(1/x) + 1], then that goes to inf^2 * 1 = + infinity, but if the question is lim as x ==> 0+ of x^2 * [ e^(1/x) - e^(1/x) + 1], then that clearly = 0, but if the question is lim as x ==> 0+ of x^2 * [ e^(1/x) - e^(1+1/x)], then that = lim as x ==> 0+ of x^2 * [ e^(1/x) - e^(1/x) * e] by exponent rules, which then = lim as x ==> 0+ of (1 - e) * x^2 * e^(1/x) = (1 - e) * lim as x ==> 0+ of e^(1/x) / x^(-2) = (1 - e) * lim as x ==> 0+ of [-e^(1/x)/x^2] / [-2*x^(-3)] by L'Hôpital's Rule = (1 - e) * lim as x ==> 0+ of e^(1/x) / [2*x^(-1)] = (1 - e) * lim as x ==> 0+ of [-e^(1/x)/x^2] / [-2*x^(-2)] by L'Hôpital's Rule again = (1 - e) * lim as x ==> 0+ of e^(1/x) / 2, which finally goes to - infinity.
@@angelmendez-rivera351 You can not post your Instagram account to communicate about this question, I did not understand very well from the comment
@@megauser8512 I think you are wrong because I think the result is 1
@@angelmendez-rivera351 You did not make a mistake, but @B Smith did.
second