Find all prime numbers $a,b,c$ and positive integers $k$ satisfying the equation \[a^2+b^2+16c^2 = 9k^2 + 1.\] Proposed by Moldova
Problem
Source:
Tags: number theory, prime numbers
djmathman
26.06.2015 16:26
Taking the equation modulo $3$ yields $a^2+b^2+c^2\equiv 1\pmod 3$. Now note that the set of quadratic residues modulo $3$ is $\{0,1\}$, so exactly two of $\{a,b,c\}$ must be divisible by $3$. However, it is given that $a$, $b$, and $c$ are primes; thus, two of them must equal exactly $3$. We now split the problem into two cases.
CASE 1: $a=b=3$
In this case, the equation becomes \[18+16c^2=9k^2+1\implies 17=9k^2-16c^2=(3k-4c)(3k+4c).\] We must then have $3k-4c=1$ and $3k+4c=17$ - solving yields $k=3$ and $c=2$. Thus $(a,b,c,k)=\boxed{(3,3,2,3)}$ is a solution.
CASE 2: $c=3$
WLOG let $a=3$ as well. Then \[3^2+b^2+16\cdot 3^2=9k^2+1\implies 152=9k^2-b^2=(3k-b)(3k+b).\] The prime factorization of $152$ is $2^3\cdot 19$. Combining this with the fact that $3k-b$ and $3k+b$ must have the same parity yields only two cases to check.
If $3k-b=2$ and $3k+b=76$, then $k=13$ and $b=37$. As $37$ is prime, the triples $(a,b,c,k)=\boxed{(3,37,3,13),(37,3,3,13)}$ work.
If $3k-b=4$ and $3k+b=38$, then $k=7$ and $b=17$. As $17$ is prime, the triples $(a,b,c,k)=\boxed{(3,17,3,7),(17,3,3,7)}$ both work.
We have thus found all quadruples of positive integers $(a,b,c,k)$ that work subject to $a,b,c$ being prime.
individ
26.06.2015 16:27
Under this condition, we should think that there would be a brute-force options. The task is more interesting if you want to solve this equation. Interesting formula better in what form to write it down?
IstekOlympiadTeam
26.06.2015 16:31
djmathman wrote:
Taking the equation modulo $3$ yields $a^2+b^2+c^2\equiv 1\pmod 3$. Now note that the set of quadratic residues modulo $3$ is $\{0,1\}$, so exactly two of $\{a,b,c\}$ must be divisible by $3$. However, it is given that $a$, $b$, and $c$ are primes; thus, two of them must equal exactly $3$. We now split the problem into two cases.
CASE 1: $a=b=3$
In this case, the equation becomes \[18+16c^2=9k^2+1\implies 17=9k^2-16c^2=(3k-4c)(3k+4c).\] We must then have $3k-4c=1$ and $3k+4c=17$ - solving yields $k=3$ and $c=2$. Thus $(a,b,c,k)=\boxed{(3,3,2,3)}$ is a solution.
CASE 2: $c=3$
WLOG let $a=3$ as well. Then \[3^2+b^2+16\cdot 3^2=9k^2+1\implies 152=9k^2-b^2=(3k-b)(3k+b).\] The prime factorization of $152$ is $2^3\cdot 19$. Combining this with the fact that $3k-b$ and $3k+b$ must have the same parity yields only two cases to check.
If $3k-b=2$ and $3k+b=76$, then $k=13$ and $b=37$. As $37$ is prime, the triples $(a,b,c,k)=\boxed{(3,37,3,13),(37,3,3,13)}$ work.
If $3k-b=4$ and $3k+b=38$, then $k=7$ and $b=17$. As $17$ is prime, the triples $(a,b,c,k)=\boxed{(3,17,3,7),(17,3,3,7)}$ both work.
We have thus found all quadruples of positive integers $(a,b,c,k)$ that work subject to $a,b,c$ being prime.
My solution at exam
Arslan
16.12.2015 06:10
Where is going to be held JBMO 2016?
IstekOlympiadTeam
16.12.2015 17:15
Arslan wrote: Where is going to be held JBMO 2016? I think it will be in Bulgaria or Cyprus
tenplusten
23.04.2016 17:59
Arslan wrote: Where is going to be held JBMO 2016? Romania See here:http://www.massee-org.eu/index.php/mathematical/jbmo/item/55-jbmo2016
perenyilmaz
18.11.2018 14:30
IstekOlympiadTeam wrote: djmathman wrote:
Taking the equation modulo $3$ yields $a^2+b^2+c^2\equiv 1\pmod 3$. Now note that the set of quadratic residues modulo $3$ is $\{0,1\}$, so exactly two of $\{a,b,c\}$ must be divisible by $3$. However, it is given that $a$, $b$, and $c$ are primes; thus, two of them must equal exactly $3$. We now split the problem into two cases.
CASE 1: $a=b=3$
In this case, the equation becomes \[18+16c^2=9k^2+1\implies 17=9k^2-16c^2=(3k-4c)(3k+4c).\]We must then have $3k-4c=1$ and $3k+4c=17$ - solving yields $k=3$ and $c=2$. Thus $(a,b,c,k)=\boxed{(3,3,2,3)}$ is a solution.
CASE 2: $c=3$
WLOG let $a=3$ as well. Then \[3^2+b^2+16\cdot 3^2=9k^2+1\implies 152=9k^2-b^2=(3k-b)(3k+b).\]The prime factorization of $152$ is $2^3\cdot 19$. Combining this with the fact that $3k-b$ and $3k+b$ must have the same parity yields only two cases to check.
If $3k-b=2$ and $3k+b=76$, then $k=13$ and $b=37$. As $37$ is prime, the triples $(a,b,c,k)=\boxed{(3,37,3,13),(37,3,3,13)}$ work.
If $3k-b=4$ and $3k+b=38$, then $k=7$ and $b=17$. As $17$ is prime, the triples $(a,b,c,k)=\boxed{(3,17,3,7),(17,3,3,7)}$ both work.
We have thus found all quadruples of positive integers $(a,b,c,k)$ that work subject to $a,b,c$ being prime.
My solution at exam Well done.
Rodymaths
04.05.2024 10:59
from (mod 3) we get RHS is 1(mod 3) and LHS is a^2+b^2+c^2(mod 3) But x^2 is 1 or 0 (mod 3), so the only configuration is two of a^2,b^2,c^2 to be 0(mod 3) and one of them to be 1(mod 3) Now we have two cases 1)a^2 and b^2 are 0(mod 3) => a=b=3 (because they are prime) we have 18+16c^2=9k^2+1 17=(3k-4c)(3k+4c) so 3k-4c=1 and 3k+4c=17 so k=3, c=2 and we have the solution (a,b,c,k)=(3,3,2,3) 2)a^2 and c^2 are 0(mod 3) => a=c=3 (because they are prime) we have 153+b^2=9k^2+1 152=(3k-b)(3k+b) and we have the cases 3k-b=1,2,4,8 if 3k-b=1 then 3k+b=152 then 6k-1=152 no solution in positive integers if 3k-b=2 then 3k+b=76 then 6k-2=76, k=13, b=37 and we get the solution (a,b,c,k)=(3,37,3,13) if 3k-b=4 then 3k+b=38 then 6k-4=38, k=7, b=17 and we get the solution (a,b,c,k)=(3,17,3,7) if 3k-b=8 then 3k+b=19 then 6k-8=19 no solution in positive integers All the solutions are (a,b,c,k)=(3,3,2,3),(3,37,3,13),(3,17,3,7)
EVKV
27.11.2024 16:41
Take mod 3 Making 2 primes 3 Then cases and we are done