I have the same question as Pedro Jose below. At 8:15 you say q is the smallest prime that divides p+1, but we have already assumed p is odd, so 2 must divide p+1 and therefore q=2. However, you never seem to use the fact that q is minimal, and later at 19:35 you say q is arbitrary. Did you mean to say q is any prime that divides p+1, instead of the smallest one?
To arrive to your answer I think it is simpler and easy to follow if we solve this way: n^p+1 Let k=‐--------- >0 as p^n+1>0 --> k=1,2,3,... p^n+1 For k=1, n^p=p^n --> mod(n,p)=0. Then n=up, u=1,2,3,... if n>=p. But mod(p,n)=0 --> p=vn, v=1,2,3,... if p>=n. Multiplying n=up and p=vn gives np=uvpn --> uv=1 meaning u=v=1. Therefore n=p. If n>p, u=2,3,... For u=2, n=2p. Putting it into n^p=p^n gives (2p)^p=p^(2p) (2^p)p^p=(p^p)² --> (p^p)[(p^p)-(2^p)]=0 p^p=2^p --> p=2, n=4 For p>n, by symmetry, gives p=4, n=2. Now we consider u>2. (up)^p=p^up (u^p)(p^p)=(p^p)^u (p^p)[(p^p)^(u-1)-u^p]=0 (p^p)^(u-1)=u^p Multiplying by p^p gives (p^p)^u=(up)^p (p^u)^p=(up)^p --> p^u=up The only solution is p=u=2, contradict u>2. Similarly for p>n by symmetry. Hence the solution is (n,p)={(2,4),(4,2)} and n=p for all prime number p. Note that it has not been shown that there is no solution for k>1.
At around 13:20, by flt, couldn't you say that q must divide 2p+1? Since you also know that q|p+1, then p + 1 = 0 mod q so 2p+1 = p = -1 mod q. From this contradiction we know that this case has no solutions. I am not sure whether this is okay...
For ex n^2 == 1 (mod 15) Has solutions n == 1,-1,4,-4 (mod 15) (Might be more..) If this result is specific to when q is prime. Then please provide a proof to it.
It's true for q is prime. If a prime number divides the product of two numbers, it must divide one of them. n^2==1 (mod q) n^2-1==0 (mod q) q|(n^2-1) q|(n+1)(n-1) Because q is prime and divides (n+1)(n-1), it must divide n+1 or n-1. That is n==+/-1 (mod q)
@letsthinkcritically, if n>=3, I thought about a simpler approach after the n n+1 = k (p^n+1) mod(p) = k mod(p) so because n n+1 = k (or k = 1 but in this case n=p) so n^p+1 = (n+1) (p^n+1) so n^p=n p^n +n+p^n and if we take that mod(n) we have 0 = 0+0+p^n mod(n) p^n = 0 mod(n) = k x n and as p is prime, p=n Do you agree ? Thanks M.
Good evening! I did not get all. But I was surprised, when you did not mention (2,2) as a solution when you take p even, so p=2. Just at the end. But being strict, when you find that p=n, you did it for p>=3. What I did not undestand, it is why did you say at 08:17 to pick a q prime minimal such that q | p+1. As you have assumed that p>=3, so p is odd and then p+1 is even and obviously q=2. I did not get why call q. But I watch on the video very quickly, I will saw more times, pausing and try to understand. If I am not abble, I call for help.
I would just use calculus. We can still use calculus in competitions, it’s just the official solution will use a way that does not require calculus. To compare n^p and p^n without using calculus I would perform induction on n and p.
Let ε > 0. The claim to prove is that log(x)/x > log(x + ε)/(x + ε) when x > e. If x > e, then multiplication by x and x + ε is monotonic, thus if log(x)/x > log(x + ε)/(x + ε), then (x + ε)·log(x) > x·log(x + ε). The exponential operation is monotonic, so if (x + ε)·log(x) > x·log(x + ε) for x > e and ε > 0, then x^(x + ε) > (x + ε)^x. If x^(x + ε) > (x + ε)^x for x > e and ε > 0, then x^ε > (1 + ε/x)^x. By the Bernoulli inequality, x^ε > 1 + ε, which holds for x > e and ε > 0. Using reverse logic, you can then conclude precisey that log(x)/x is increasing. As for Bernoulli's inequality, anyone at a competition should know it, and the inequality x^ε > 1 + ε is straightforward.
I usually look for contest problems on Art of Problem Solving (AoPS). There are many interesting problems with solutions contributed by other users. Try to learn by reading their ideas, and one day you will also be able to produce similar work for other people!
sir i really want to solve problems like other great mathematicians but some times i am not able to solve some problems like these, so i want to know how can i become good at proving and problem solving.
We have n^(2p) == 1 (mod q), and n^(ord(q,n)) == 1 (mod q), and ord(q,n) is the minimal positive integer that satisfies n^? == 1 (mod q) We note that if n == 1 (mod q), then ord(q,n) = 1, trivially, and 2p is always divisible by 1. Otherwise, we make note of the sequence of values n, n^2, n^3, ... n^ord(q,n) (all mod q). This nonrepeating sequence starts at 'n', and ends at 1, and does not contain a 1 before that end (since ord(q,n) is minimal). The next term in the sequence, multiplying by another factor of n (mod q), will yield n (mod q) again, and continuing onward will cause the cycle of the same values to repeat. We will obtain a result of 1 if and only if we are at a term in the sequence that is an integer multiple of ord(q,n). Since we know that n^2p == 1 (mod q), then it follows that 2p must be a multiple of ord(q,n); i.e. that 2p is divisible by ord(q,n).
This could be an absurd question, but can't we start with observation (by inspection) that at equality (n=p),p being any prime, the equality holds good? Not sure what I am missing here? n > 0 ,of course
Pick prime q minimal such that q | p + 1.
But p + 1 is an even number.
Therefore q = 2.
Thats what I was thinking.
3 divides 6 but 3 is not equal to 2. The point here is to choose an arbitrary q so we can build an argument on all the factors of p+1
I have the same question as Pedro Jose below. At 8:15 you say q is the smallest prime that divides p+1, but we have already assumed p is odd, so 2 must divide p+1 and therefore q=2. However, you never seem to use the fact that q is minimal, and later at 19:35 you say q is arbitrary. Did you mean to say q is any prime that divides p+1, instead of the smallest one?
To arrive to your answer I think it is simpler and easy to follow if we solve this way:
n^p+1
Let k=‐--------- >0 as p^n+1>0 --> k=1,2,3,...
p^n+1
For k=1, n^p=p^n --> mod(n,p)=0. Then n=up, u=1,2,3,... if n>=p. But mod(p,n)=0 --> p=vn, v=1,2,3,... if p>=n. Multiplying n=up and p=vn gives np=uvpn --> uv=1 meaning u=v=1. Therefore n=p.
If n>p, u=2,3,... For u=2, n=2p. Putting it into n^p=p^n gives (2p)^p=p^(2p)
(2^p)p^p=(p^p)² --> (p^p)[(p^p)-(2^p)]=0
p^p=2^p --> p=2, n=4
For p>n, by symmetry, gives p=4, n=2.
Now we consider u>2. (up)^p=p^up
(u^p)(p^p)=(p^p)^u
(p^p)[(p^p)^(u-1)-u^p]=0
(p^p)^(u-1)=u^p
Multiplying by p^p gives (p^p)^u=(up)^p
(p^u)^p=(up)^p --> p^u=up
The only solution is p=u=2, contradict u>2. Similarly for p>n by symmetry.
Hence the solution is (n,p)={(2,4),(4,2)} and n=p for all prime number p.
Note that it has not been shown that there is no solution for k>1.
overpowered problems really really loved it
Thank you!!
Now I got the point! Very beautiful soulution! Congratulations.
At around 13:20, by flt, couldn't you say that q must divide 2p+1? Since you also know that q|p+1, then p + 1 = 0 mod q so 2p+1 = p = -1 mod q. From this contradiction we know that this case has no solutions. I am not sure whether this is okay...
15:45
How can one say that n^2 == 1(mod q)
Has only n == 1 (mod q) and n == -1 (mod q)
as solutions.
For ex n^2 == 1 (mod 15)
Has solutions n == 1,-1,4,-4 (mod 15)
(Might be more..)
If this result is specific to when q is prime. Then please provide a proof to it.
It's true for q is prime.
If a prime number divides the product of two numbers, it must divide one of them.
n^2==1 (mod q) n^2-1==0 (mod q) q|(n^2-1) q|(n+1)(n-1)
Because q is prime and divides (n+1)(n-1), it must divide n+1 or n-1. That is n==+/-1 (mod q)
@letsthinkcritically, if n>=3, I thought about a simpler approach after the n n+1 = k (p^n+1) mod(p) = k mod(p)
so because n n+1 = k (or k = 1 but in this case n=p)
so n^p+1 = (n+1) (p^n+1)
so n^p=n p^n +n+p^n
and if we take that mod(n) we have
0 = 0+0+p^n mod(n)
p^n = 0 mod(n) = k x n and as p is prime, p=n
Do you agree ?
Thanks
M.
Good evening! I did not get all. But I was surprised, when you did not mention (2,2) as a solution when you take p even, so p=2. Just at the end. But being strict, when you find that p=n, you did it for p>=3. What I did not undestand, it is why did you say at 08:17 to pick a q prime minimal such that q | p+1. As you have assumed that p>=3, so p is odd and then p+1 is even and obviously q=2. I did not get why call q. But I watch on the video very quickly, I will saw more times, pausing and try to understand. If I am not abble, I call for help.
How would you show (log x)/x is decreasing when x > e in competition?
I would just use calculus. We can still use calculus in competitions, it’s just the official solution will use a way that does not require calculus.
To compare n^p and p^n without using calculus I would perform induction on n and p.
Let ε > 0. The claim to prove is that log(x)/x > log(x + ε)/(x + ε) when x > e. If x > e, then multiplication by x and x + ε is monotonic, thus if log(x)/x > log(x + ε)/(x + ε), then (x + ε)·log(x) > x·log(x + ε). The exponential operation is monotonic, so if (x + ε)·log(x) > x·log(x + ε) for x > e and ε > 0, then x^(x + ε) > (x + ε)^x. If x^(x + ε) > (x + ε)^x for x > e and ε > 0, then x^ε > (1 + ε/x)^x. By the Bernoulli inequality, x^ε > 1 + ε, which holds for x > e and ε > 0.
Using reverse logic, you can then conclude precisey that log(x)/x is increasing. As for Bernoulli's inequality, anyone at a competition should know it, and the inequality x^ε > 1 + ε is straightforward.
Let f(x) = (logx)/x
==> f'(x) = (1-logx)/x²
Now x > e ==> logx > 1 ==> 1-logx < 0
Hence f'(x) < 0 , x > e ==> f(x) is decreasing function
Phew! I tried, but I couldn't figure it out, I got stuck on computing the thing modulo powers of p.
N=p is a solution,( n^n+1)/(n^n+1)=1 , 1 is integer
Hi professor I'm a new member of your channel and I found your video great ... Can you share with me some titles of books for problem solving ....
I usually look for contest problems on Art of Problem Solving (AoPS). There are many interesting problems with solutions contributed by other users. Try to learn by reading their ideas, and one day you will also be able to produce similar work for other people!
@@letsthinkcritically thanks a bunch
REALLY NICE PROBLEM AND I AM REALLY LOVING THE BOOK U SUGGESTED!! TYSM Aur u on aops???If yes please share your id
Can you tell me the name of the book , which he suggested ?
No I am not on AoPS.
The book is Problems in Combinatorics by Ioan Tomescu.
@@letsthinkcritically Hey ! Thanks for answering my question as well ! :)
hey i'm not sure that if n^2 equals to 1 mod q then n must be -1 or 1 mod q??? that's not obviously
its true only because q is prime.
n^2-1 = 0 mod q and so either n+1 or n-1 = 0 mod q
@@letsthinkcritically ok ok i'm stupid a bit. Anyway thank you for your explaination
but both n and p have to be greater than 3 to say that p>n isn t it
Yes, so I settled the p=2 case separately.
sir i really want to solve problems like other great mathematicians but some times i am not able to solve some problems like these, so i want to know how can i become good at proving and problem solving.
When (3,3) is also a solutions.
how p>=n ?
why did you say nᵖ + 1 ≥ pⁿ + 1, I don't get it
Because the denominator is a divisor of the numerator, and since both are positive, surely the denominator cannot be greater than the numerator.
OHHH I GET IT! THANKS A LOT
love your channel! Thanks.
How is 2p divisible by order(q,n).
Can anyone explain?
We have n^(2p) == 1 (mod q), and n^(ord(q,n)) == 1 (mod q), and ord(q,n) is the minimal positive integer that satisfies n^? == 1 (mod q)
We note that if n == 1 (mod q), then ord(q,n) = 1, trivially, and 2p is always divisible by 1.
Otherwise, we make note of the sequence of values n, n^2, n^3, ... n^ord(q,n) (all mod q). This nonrepeating sequence starts at 'n', and ends at 1, and does not contain a 1 before that end (since ord(q,n) is minimal). The next term in the sequence, multiplying by another factor of n (mod q), will yield n (mod q) again, and continuing onward will cause the cycle of the same values to repeat. We will obtain a result of 1 if and only if we are at a term in the sequence that is an integer multiple of ord(q,n).
Since we know that n^2p == 1 (mod q), then it follows that 2p must be a multiple of ord(q,n); i.e. that 2p is divisible by ord(q,n).
I have a different solution. Is anyone interested in seeing it?
Yes
Ok, so I thought I had a pretty nice solution but I just realised that for it to be complete, I would have to prove that k-1
Very good video, subscribed.
Your students are lucky.
Thank you for your compliment ~
@@letsthinkcritically do you teach in the US?
very good.
Thank you!!
Nice problems!!
super, very good, i love tu canal
Ty
This could be an absurd question, but can't we start with observation (by inspection) that at equality (n=p),p being any prime, the equality holds good? Not sure what I am missing here? n > 0 ,of course
Yes, but you have to show that together with (n,p) = (4,2), they are the only solutions.
@@letsthinkcritically At 7:55 I was expecting to include the case {n,p}={2,2}
oh, I see it at 21:15... sorry.
Awesome!
I wouldn't have been able to solve that 👍
P = N(P)
Excelente