Prove that there are not intgers $a$ and $b$ with conditions, i) $16a-9b$ is a prime number. ii) $ab$ is a perfect square. iii) $a+b$ is also perfect square.
Problem
Source: AZE JBMO TST
Tags: number theory, prime numbers, AZE JBMO TST
tchebytchev
02.05.2015 19:48
First $ab \geq 0$ and $a+b\geq 0$ leads to $a$ and $b$ are nonnegative integers. Let $d=\gcd(a,b)$ so $a=dx, b=dy$ and $16a-9b=d(16x-9y)$ is prime so $d=1$ or $16x-9y=1$ -If $16x-9y=1$ then $x=9n+4$ and $y=16n+7$ for some integer $n$ thus $ab=d^2(9n+4)(16n+7)$ is a perfect square so $(9n+4)(16n+7)=\frac{(127+288 n)^2-1}{576}=m^2$. This gives us $(127+288 n)^2-1=(24m)^2$ which it is a contradiction. -If $d=1$, since $ab$ is a perfect square then both $a$ and $b$ are perfect squares. Let $a=m^2, b=n^2$ for non negative integers $m,n$. Hence $16a-9b=(4m-3n)(4m+3n)$ is a prime thus $4m-3n=1$ so $m=3k+1$ and $n=4k+1$ for some integer $k$ and in this case $a+b=(3k+1)^2+(4k+1)^2=\frac{(7+25k)^2+1}{25}$ cannot be a perfect square. By the same way if $4m-3n=-1$ then $m=3k+2, n=4k+3$ and in this case $a+b=\frac{(18+25k)^2+1}{25}$ cannot be a perfect square.
Tan
02.05.2015 20:06
This was a very nice problem For this problem, a useful property is a perfect square is congruent to 0 or 1 mod 4.
Assume for the sake of contradiction there exists such integers $a$ and $b$. From our important property, $a \equiv 0 (mod 4)$ and $b \equiv 1 (mod 4)$. (using the 3 conditions). Let $a=4m$ and $b=4n+1$. Then, using property 2, we have $m(4n+1)$ is a perfect square. This means $(m,4n+1) > 1$ or both $m$ and $4n+1$ are perfect squares. (Note: $(m,4n+1)$ denotes the greatest common divisor of $m$ and $4n+1$)
Case 1: $(m,4n+1) > 1$
We have $64a-9b=16(4m)-9(4n+1)$. Note that $(m,4n+1) | 16(4m)-9(4n+1)$. Since $(m,4n+1)>1$, $16a-9b$ is not prime - a contradiction.
Case 2: $m,4n+1$ are both perfect squares
Let $m=p^2$, $4n+1=q^2$ and $a+b=r^2$. Then, we get $a+b=4p^2+q^2=r^2$.From Case 1, we saw $16a-9b=64m-9(4n+1)=64p^2-9q^2=16(4p^2+q^2)-25q^2=16r^2-25q^2=(4r-5q)(4r+5q)$ by difference of squares. However, we also have $16a-9b=64p^2-9q^2=(8p-3q)(8p+3q)$ by difference of squares.
Since $16a-9b$ is prime, we have $4r-5q=8p-3q=1$ and $4r+5q,8p+3q$ are prime numbers. From $4r-5q=8p-3q$, we get $r=\frac{2p+q}{2}$, so $r^2=\frac{4p^2+4pq+q^2}{4}=4p^2+q^2$. Simplying we get $0=12p^2-4pq+3q^2=(2p-q)^2+8p^2+2q^2=(2p-q)^2+2r^2$. We get $2p-q=r=0$ - a contradiction.
Thus, our claim is proven.
EDIT: Sniped :p (by longer than I thought)
hypogean
02.05.2015 20:11
Again, noting the first solution from $ab \ge 0$ and $a+b \ge 0$ we have that $a$ and $b$ are non-negative integers. We proceed by contradiction. Assume there is such a solution. Then we have that $a+2\sqrt{ab}+b = (\sqrt{a}+\sqrt{b})^2$ must be an integer and similarly $a-2\sqrt{ab}+b = (\sqrt{a}-\sqrt{b})^2$ must also be an integer. Thus for 2 non-negative integers $c$ and $d$ we must have $\sqrt{a}+\sqrt{b} = \sqrt{c}$ and $\sqrt{a}-\sqrt{b} = \sqrt{d}$. Thus $\sqrt{a} = \frac{\sqrt{c}+\sqrt{d}}{2}$ and $\sqrt{b} = \frac{\sqrt{c}-\sqrt{d}}{2}$. This implies $a=\frac{c+d+2\sqrt{cd}}{4}$ and $b=\frac{c+d-2\sqrt{cd}}{4}$. Replacing this into i we get that $16a-9b = \frac{7c+7d+14\sqrt{cd}}{4} = 7(\frac{c+d+2\sqrt{cd}}{4}) = 7a$. This implies that $a=b=1$. But this doesn't satisfy the third equation. Thus, there are no solutions.
neverlose
31.05.2015 15:32
hypogean wrote: Again, noting the first solution from $ab \ge 0$ and $a+b \ge 0$ we have that $a$ and $b$ are non-negative integers. We proceed by contradiction. Assume there is such a solution. Then we have that $a+2\sqrt{ab}+b = (\sqrt{a}+\sqrt{b})^2$ must be an integer and similarly $a-2\sqrt{ab}+b = (\sqrt{a}-\sqrt{b})^2$ must also be an integer. Thus for 2 non-negative integers $c$ and $d$ we must have $\sqrt{a}+\sqrt{b} = \sqrt{c}$ and $\sqrt{a}-\sqrt{b} = \sqrt{d}$. Thus $\sqrt{a} = \frac{\sqrt{c}+\sqrt{d}}{2}$ and $\sqrt{b} = \frac{\sqrt{c}-\sqrt{d}}{2}$. This implies $a=\frac{c+d+2\sqrt{cd}}{4}$ and $b=\frac{c+d-2\sqrt{cd}}{4}$. Replacing this into i we get that $16a-9b = \frac{7c+7d+14\sqrt{cd}}{4} = 7(\frac{c+d+2\sqrt{cd}}{4}) = 7a$. This implies that $a=b=1$. But this doesn't satisfy the third equation. Thus, there are no solutions. you have a mistake,$16a - 9b = \frac{7c+7d+50\sqrt{cd}}{4}$.
Taha1381
18.06.2018 10:01
Here's a sketch of my solution: 1.Show $gcd (a,b)=1$ so we have $a=x^2,b=y^2$ and $x,y$ are coprime. 2.Use pytagorean(wrong spelling I think) triple to use the condition $a+b$ is a perfect square. 3.put $a,b$ in the first condition and factorize one sentence has to be $1$ use quadric formula to get a contradiction here too.
Devastator
18.06.2018 11:21
I have a "not quadratic equation element stuff" solution that involves bounding because I am bad at discriminant bashing
Suppose such a,b exists
Since $ab$ and $a+b$ are squares, then they must both be nonnegative. Checking, $a=0$ and $b=0$ both don't work, so $ab$ must be positive and thus, a and b have the same sign. Since $a+b$ is nonnegative, then a and b must both be positive.
Let the gcd of a,b be d, and let $a=dm$, $b=dn$. Then $16a-9b=d(16m-9n)$ Thus, either $d=1$ or $16m-9n=1$
Case 1:$d=1$
Since their gcd is 1, then a and b must be relatively prime
Since their product $ab$ is a square and they are relatively prime, then a and b themselves must be squares.
Let $a=x^2$ and $b=y^2$, whe x and y are positive integers
Then we have that $16a-9b=16x^2-9y^2=(4x+3y)(4x-3y)$
Clearly, this can only be prime if we have $4x-3y=1$ Since $4x+3y>1$
Checking this equation $\mod 3$, we have that $x=1 \mod 3$ (how do u type the congruent symbol?)
Let $x=3k-2$, where n is a positive integer. Plugging this in $4x-3y=1$ gives us $y=4k-3$
Therefore, we get that $a+b=x^2+y^2=(3k-2)^2+(4k-3)^2=25k^2-36k+13$ must be a perfect square.
But it is easy to see that $(5k-4)^2 < 25k^2-36k+13 < (5k-3)^2$ for all positive integers k (this part is left as an exercise to the reader ), a contradiction!
Case 2:$16m-9n=1$
The solutions to this equation are of the form $m=9k-5$, $n=16k-9$, where k is a positive integer.
Then $ab=d^2mn=d^2(144k^2-161k+45)$ must be a perfect square, so $144k^2-161k+45$ is a square
But then $(12k-7)^2<144k^2-161k+45<(12k-6)^2$ for all positive integers k (another exercise ), a contradiction!
Therefore, no such a,b exists
Edit:Hole patched
Taha1381
18.06.2018 11:23
Devastator wrote: I have a no too long and "nearly bash free" solution that involves bounding
Suppose such a,b exists
Clearly, if the gcd of a and b is greater than 1, then that gcd will divide $16a-9b$, hence, thier gcd is 1 and they are relatively prime
Since their product $ab$ is a square and they are relatively prime, then a and b themselves must be squares.
Brb First the gcd can be the prime itself second it asked us to show there are no solutions.
Devastator
18.06.2018 11:37
Taha1381 wrote: First the gcd can be the prime itself second it asked us to show there are no solutions. Brb means be right back, sorry. Also, tnx for pointing that out, I'll try patching that hole up