NT marathon!!!!!!!

For discussing Olympiad Level Number Theory problems
Dustan
Posts:71
Joined:Mon Aug 17, 2020 10:02 pm
Re: NT marathon!!!!!!!

Unread post by Dustan » Sun Mar 21, 2021 8:25 am

Anindya Biswas wrote:
Sun Mar 21, 2021 12:05 am
Dustan wrote:
Sat Mar 20, 2021 11:04 pm
From the discriminate, we can say $12b^2+6b+1$ is not a square.
I think this sentence needs some clearance... How can we say that $12b^2+6b+1$ is never going to be a perfect square?
If this quadratic equation has solutions in integers, then its discriminant must be a perfect square.

So, $b^2-4ac=6^2-4*12*1=36-48$ is not a perfect square. 😶

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: NT marathon!!!!!!!

Unread post by Anindya Biswas » Sun Mar 21, 2021 10:34 am

Dustan wrote:
Sun Mar 21, 2021 8:25 am
Anindya Biswas wrote:
Sun Mar 21, 2021 12:05 am
Dustan wrote:
Sat Mar 20, 2021 11:04 pm
From the discriminate, we can say $12b^2+6b+1$ is not a square.
I think this sentence needs some clearance... How can we say that $12b^2+6b+1$ is never going to be a perfect square?
If this quadratic equation has solutions in integers, then its discriminant must be a perfect square.

So, $b^2-4ac=6^2-4*12*1=36-48$ is not a perfect square. 😶
Isn't this the case when we are trying to solve $12b^2+6b+1=0$? But in this case,we are trying to find $b$ such that $12b^2+6b+1$ is a perfect square, not the root of that polynomial, so why is discriminant so important?
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Solution of Problem:2

Unread post by Mehrab4226 » Sun Mar 21, 2021 8:19 pm

Let,
$d_1,d_2,d_3 \cdots d_k$ be the divisiors of $n$ not greater than $\sqrt{n}$.
$\therefore \frac{n}{d_1},\frac{n}{d_2},\cdots \frac{n}{d_k}$ are the other divisors.

$\therefore \tau (n) \leq 2k$ [Less is when n is a square number]
But, $k \leq \sqrt{n}$ because by definition k cannot exceed $\sqrt{n}$
$\therefore \tau (n) \leq 2\sqrt{n}$

I probably read the solution before in a book. Probably :|
Last edited by Mehrab4226 on Sun Mar 21, 2021 8:34 pm, edited 1 time in total.
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Problem:3

Unread post by Mehrab4226 » Sun Mar 21, 2021 8:25 pm

Let $n$ be a positive integer and let $a_1,a_2,a_3,\cdots ,a_k$($k\geq 2)$ be distinct integers in the set $1,2,\cdots , n$ such that $n$ divides $a_i(a_{i+1}-1)$ for $i=1,2,\cdots , k-1$. Prove that $n$ does not divide $a_k(a_1-1).$

Source:
IMO SL 2009, N1
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

User avatar
Anindya Biswas
Posts:264
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: Solution of Problem:2

Unread post by Anindya Biswas » Sun Mar 21, 2021 8:28 pm

Mehrab4226 wrote:
Sun Mar 21, 2021 8:19 pm
Let,
$d_1,d_2,d_3 \cdots d_k$ be the divisiors of $n$ not greater than $\sqrt{n}$.
$\therefore \frac{n}{d_1},\frac{n}{d_2},\cdots \frac{n}{d_k}$ are the other divisors.

$\therefore \tau (n) \leq 2k$ [Less is when n is a square number]
But, $k \leq \sqrt{n}$ because by defination k cannot exceed $\sqrt{n}$
$\therefore \tau(n) \leq 2\sqrt{n}$

I probably read the solution before in a book. Probably :|
From here, we can easily see that the equality never holds. Cause if $n$ is a perfect square, then $\tau(n)$ is odd and $2\sqrt{n}$ is even. So it must always be the case that $\tau(n)<2\sqrt{n}$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

User avatar
Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
Location:Dhaka, Bangladesh

Re: Solution of Problem:2

Unread post by Mehrab4226 » Sun Mar 21, 2021 8:35 pm

Anindya Biswas wrote:
Sun Mar 21, 2021 8:28 pm
Mehrab4226 wrote:
Sun Mar 21, 2021 8:19 pm
Let,
$d_1,d_2,d_3 \cdots d_k$ be the divisiors of $n$ not greater than $\sqrt{n}$.
$\therefore \frac{n}{d_1},\frac{n}{d_2},\cdots \frac{n}{d_k}$ are the other divisors.

$\therefore \tau (n) \leq 2k$ [Less is when n is a square number]
But, $k \leq \sqrt{n}$ because by defination k cannot exceed $\sqrt{n}$
$\therefore \tau(n) \leq 2\sqrt{n}$

I probably read the solution before in a book. Probably :|
From here, we can easily see that the equality never holds. Cause if $n$ is a perfect square, then $\tau(n)$ is odd and $2\sqrt{n}$ is even. So it must always be the case that $\tau(n)<2\sqrt{n}$
Ahh!!. yes, yes. Clever one!
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

~Aurn0b~
Posts:46
Joined:Thu Dec 03, 2020 8:30 pm

Re: Problem:3

Unread post by ~Aurn0b~ » Sun Mar 21, 2021 10:35 pm

Mehrab4226 wrote:
Sun Mar 21, 2021 8:25 pm
Let $n$ be a positive integer and let $a_1,a_2,a_3,\cdots ,a_k$($k\geq 2)$ be distinct integers in the set $1,2,\cdots , n$ such that $n$ divides $a_i(a_{i+1}-1)$ for $i=1,2,\cdots , k-1$. Prove that $n$ does not divide $a_k(a_1-1).$

Source:
IMO SL 2009, N1
$\textbf{Solution 3}$
We have, $ a_{i-1}(a_i-1)\equiv 0\pmod{n}\Rightarrow a_ia_{i-1}\equiv a_{i-1}\pmod{n}$

So, $a_ka_{k-1}a_{k-2}\cdots a_1\equiv a_{k-1}a_{k-2}\cdots a_1\equiv a_{k-2}a_{k-3}\cdots a_1\equiv\cdots \equiv a_1 \pmod{n}$

Assume that $n$ divides $a_k(a_1-1)\Rightarrow a_ka_1\equiv a_k\pmod{n}$
$\Rightarrow a_ka_{k-1}a_1\equiv a_ka_{k-1}\equiv a_{k-1}\pmod{n}$

$\Rightarrow a_ka_{k-1}a_{k-2}a_1\equiv a_{k-1}a_{k-2}\equiv a_{k-2}\pmod{n}$

Going on like this at point we'll have $a_ka_{k-1}a_{k-2}\cdots a_2 a_1\equiv a_2 \pmod{n}$
Therefore, $a_1\equiv a_2\pmod{n}$, but this cannot be possible as both of them are smaller than $n$, so they cannot have same remainder upon dividing by $n$, Contradiction.$\blacksquare$

~Aurn0b~
Posts:46
Joined:Thu Dec 03, 2020 8:30 pm

Re: NT marathon!!!!!!!

Unread post by ~Aurn0b~ » Sun Mar 21, 2021 10:48 pm

$\textbf{Problem 4}$

Solve the equation
\[ 3^x - 5^y = z^2.\]
in positive integers.

Dustan
Posts:71
Joined:Mon Aug 17, 2020 10:02 pm

Re: NT marathon!!!!!!!

Unread post by Dustan » Mon Mar 22, 2021 1:14 pm

Solution 4: taking mod 4
$(-1)^x-1\cong 0/1(mod4)$
In R.H.S. $z^2$ should be $\cong$to 0. Otherwise
$(-1)^x=1+1\cong 2$ contradiction.Since L.H.S. can be 3 or 1 only.
So,$x$ is even. Hence $z$ also.
Let, $x=2k$
$(3^k+z)(3^k-z)=5^y$,where
$(3^k+z,3^k-z)=(3^k-z,2z)=(3^k,z)=1$
So, $(3^k-z)=1 $ and $(3^k+z)=5^a $ for some a
Now, $a=1$ gives $(x,y,z)=(2,1,2)$
$a=2$ has no integer soln.
For $3\leq a$ according to the zsigmondy theorem
There will exist atleast a prime factor $p≠2,13$
which doesn't divide $5^2+1$
And we are done.


(Is there any mistake?):(

Asif Hossain
Posts:194
Joined:Sat Jan 02, 2021 9:28 pm

Re: NT marathon!!!!!!!

Unread post by Asif Hossain » Tue Mar 23, 2021 8:33 pm

Sorry for my wrong solu of prob 1 here is my another elementary solu:(pls confirm)
Taking mod $4$ it is clear that $x$ must be odd.
Case 1: $y$ is odd.
We can rewrite the equation as $(x-1)(x^2+x+1)=2y^2$ now since $x^2+x+1$ is odd then $(x^2+x+1)|y^2$ now by little modular arithmetic it is easy to see $x \equiv 1 (mod 4)$ or $(x-1) \equiv 0 (mod4)$ but $(x-1) \equiv 0 (mod2)$ which implies $y^2$ is even which contradicts that $y$ is odd,
Case2: $y$ is even.
.Let $x=2k_1 +1$ and $y=2k_2$
Plugging it into the original equation
$\Rightarrow 8k_{1}^{3}+12k_{1}^{2}+6k_1=8k_{2}^{2}$
Now taking mod 4 both side implies $6k_1 \equiv 0 \Rightarrow 2k_1 \equiv 0 (mod 4)$ which implies $k_1$ is even since all positive integer
Then also taking modulo 8 implies $k_1(12k_1+6) \equiv 0 (mod 8)$ one case is $12k_1+6 \equiv 0 (mod 8)$ which implies $k_1$ is odd so contradiction
the other case is $k_1 \equiv 0 (mod 8)$ or $(mod4)$ WLOG that is not possible since iterating the process avoiding odd value of $k_1$ would then mean $k_1$ is divisible by any power of $2$ so then it would have no solution.$\square$
Last edited by Asif Hossain on Wed Mar 24, 2021 9:33 pm, edited 7 times in total.
Hmm..Hammer...Treat everything as nail

Post Reply