Derek's prime-tuple

How many distinct 4 4 -tuples of (positive) primes ( p 1 , p 2 , p 3 , p 4 ) (p_1, p_2, p_3, p_4) are there such that p 1 < p 2 < p 3 < p 4 p_1 < p_2 < p_3 < p_4 and

p 1 2 + p 2 2 + p 3 2 + p 4 2 = 2223 ? p_1^2 + p_2^2 + p_3^2 + p_4^2 = 2223?

This problem is posed by Derek K.


The answer is 3.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

26 solutions

If all primes p 1 , p 2 , p 3 , p 4 p_1,p_2,p_3,p_4 are odd, then the sum p 1 2 + p 2 2 + p 3 2 + p 4 2 p_1^2+p_2^2+p_3^2+p_4^2 is even, which is a contradiction. This implies p 1 = 2. p_1= 2. We have p 2 2 + p 3 2 + p 4 2 = 2223 4 = 2219 p_2^2+p_3^2+p_4^2 = 2223-4 = 2219 . If p 2 3 p_2 \neq 3 , then by Fermat's Little Theorem , we have that p 2 2 + p 3 2 + p 4 2 1 + 1 + 1 0 ( m o d 3 ) , p_2^2 +p_3^2+p_4^2 \equiv 1 + 1 + 1 \equiv 0 \pmod{3}, which is a contradiction to the fact that 3 3 does not divide 2219 2219 . Hence p 2 = 3 p_2 =3 . Now we have p 3 2 + p 4 2 = 2219 9 = 2210 p_3^2+p_4^2 = 2219-9 = 2210 . Since p 4 2 < p 3 2 + p 4 2 < 2 p 4 2 p_4^2<p_3^2+p_4^2 < 2p_4^2 , it follows that 1105 = 2210 2 < p 4 2 < 2210. 1105 = \frac{2210}{2} < p_4^2 < 2210. This implies p 4 p_4 is a member of the set { 37 , 41 , 43 , 47 } \{37,41,43,47\} . Running through all the cases, we find ( p 3 , p 4 ) = ( 29 , 37 ) , ( 23 , 41 ) , (p_3,p_4)=(29,37),(23,41), and ( 19 , 43 ) . (19,43). Hence there are 3 3 distinct 4-tuples ( p 1 , p 2 , p 3 , p 4 ) (p_1,p_2,p_3,p_4) of primes satisfying the given condition, namely ( 2 , 3 , 29 , 37 ) , ( 2 , 3 , 23 , 41 ) , and ( 2 , 3 , 19 , 43 ) . (2,3,29,37),\quad (2,3,23,41) ,\quad \text{and} \quad (2,3,19,43).

Moderator note:

Bounding p 4 p_4 is the best way to solve this problem without going through many cases. A 5-vote boost from Brilliant to promote visibility.

awesome!

Kishan k - 7 years, 10 months ago

NICE!

Joshua Richard Theodoroes - 7 years, 10 months ago

Did the same! Nice!

Kartik Sharma - 6 years, 6 months ago

Very good solution!!!!

Rindell Mabunga - 5 years, 4 months ago

awesome solution!

Hamza A - 5 years, 4 months ago

Brilliant thinking! Same way

Joshua Chin - 5 years, 1 month ago
Mark Hennings
Jul 22, 2013

Squares are congruent to 0 or 1 modulo 4. 2223 is congruent to 3 modulo 4. Thus one of the primes is even, so p 1 = 2 p_1=2 . Thus p 2 2 + p 3 2 + p 4 2 = 2219 p_2^2+p_3^2+p_4^2=2219 . Squares are congruent to 0 or 1 modulo 3. 2219 is congruent to 2 modulo 3. Thus one of the primes is a multiple of 3, and hence p 2 = 3 p_2=3 . Thus p 3 2 + p 4 2 = 2210 p_3^2+p_4^2=2210 . (It would be easy to solve this last equation by testing possible primes, but the following is more fun!) Factorising 2210 into primes over the Gaussian integers, we have ( p 3 + i p 4 ) ( p 3 i p 4 ) = 2 × 5 × 13 × 17 = ( 1 + i ) ( 1 i ) ( 2 + i ) ( 2 i ) ( 3 + 2 i ) ( 3 2 i ) ( 4 + i ) ( 4 i ) (p_3+ip_4)(p_3-ip_4)=2\times5\times13\times17=(1+i)(1-i)(2+i)(2-i)(3+2i)(3-2i)(4+i)(4-i) To within association, this means that p 3 + i p 4 = ( 1 + a i ) ( 2 + b i ) ( 3 + 2 c i ) ( 4 + d i ) p_3+ip_4=(1+ai)(2+bi)(3+2ci)(4+di) where a , b , c , d = ± 1 a,b,c,d = \pm1 . Running through the options (and ignoring signs and ordering), we obtain the options ( p 3 , p 4 ) = ( 1 , 47 ) , ( 19 , 43 ) , ( 23 , 41 ) , ( 29 , 37 ) (p_3,p_4)=(1,47), (19,43), (23,41), (29,37) . The first is not allowable (1 is not prime), so we have 3 solutions.

Moderator note:

As noted in the solution, "It would be easy to solve this last equation by testing possible primes, but the following is more fun!" Gaussian Integers are beautiful, and are useful for many purposes.

A 3-vote boost from the Brilliant to promote visibility :)

The Gaussian integers (the integers with i i added on) form a Euclidean domain, and its primes are:

(i) odd integer primes congruent to 3 3 modulo 4 4 ,

(ii) 1 + i 1+i and 1 i 1-i ,

(iii) numbers of the form a + b i a+bi where a a and b b are integers and a 2 + b 2 a^2+b^2 is congruent to 1 1 modulo 4 4 .

Thus ( 1 + i ) ( 1 i ) ( 2 + i ) ( 2 i ) ( 3 + 2 i ) ( 3 2 i ) ( 4 + i ) ( 4 i ) = 2210 (1+i)(1-i)(2+i)(2-i)(3+2i)(3-2i)(4+i)(4-i) = 2210 factorises 2010 2010 over the Gaussian integers as a product of eight distinct primes, and this must equal p 3 2 + p 4 2 = ( p 3 + i p 4 ) ( p 3 i p 4 ) p_3^2+p_4^2 = (p_3+ip_4)(p_3-ip_4) . Each of the eight primes in the factorisation of 2210 2210 must divide one of p 3 + i p 4 p_3+ip_4 and p 3 i p 4 p_3-ip_4 . Note that the eight prime factors come in four complex conjugate pairs. If (for example) 1 + i 1+i divides p 3 + i p 4 p_3+ip_4 , then (taking complex conjugates) 1 i 1-i must divide p 3 i p 4 p_3-ip_4 and hence (since it only appears once in the prime factorisation of 2210 2210 ) does not divide p 3 + i p 4 p_3+ip_4 . Thus one of each complex conjugate pair divides p 3 + i p 4 p_3+ip_4 , with the other half of each pair dividing p 3 i p 4 p_3-ip_4 . Thus we can find a , b , c , d = ± 1 a,b,c,d = \pm1 such that 1 + a i 1+ai , 2 + b i 2+bi , 3 + 2 c i 3+2ci , 4 + d i 4+di all divide p 3 + i p 4 p_3+ip_4 , with 1 a i 1-ai , 2 b i 2-bi , 3 2 c i 3-2ci , 4 d i 4-di all dividing p 3 i p 4 p_3-ip_4 . Apart from these four factors, p 3 + i p 4 p_3+ip_4 has no prime factors. Thus p 3 + i p 4 = u ( 1 + a i ) ( 2 + b i ) ( 3 + 2 c i ) ( 4 + d i ) p_3+ip_4 = u(1+ai)(2+bi)(3+2ci)(4+di) where u u is a unit in the Gaussian integers (a number whose inverse is a Gaussian integer), namely one of ± 1 \pm1 , ± i \pm i . The phrase to within association means multiplying by a unit if necessary . When we run through the options for a , b , c , d a,b,c,d , there will be cases where p 3 , p 4 p_3,p_4 appear to be negative. Choosing a suitable unit can make both of them positive. For example, ( 1 + i ) ( 2 + i ) ( 3 + 2 i ) ( 4 + i ) = 23 + 41 i (1+i)(2+i)(3+2i)(4+i) = -23+41i but i ( 1 + i ) ( 2 + i ) ( 3 + 2 i ) ( 4 + i ) = 41 + 23 i -i(1+i)(2+i)(3+2i)(4+i) = 41+23i Note that the real reason why 1 1 is not a prime in the integers is because it is a unit! A unit in an integral domain is a number which has a multiplicative inverse in the domain, and primes/irreducibles are explicitly required to be non-units. This non-unit requirement for primes guarantees the uniqueness of prime factorisation (when it occurs - it does in the Gaussian integers).

Mark Hennings - 7 years, 10 months ago

Nice solution, but how do you get the equation after "To within association, this means that?"

Aradhya Kasera - 7 years, 10 months ago
Tim Vermeulen
Jul 24, 2013

Consider parity. The left hand side needs to be odd, so p 1 p_1 is even, and 2 2 is the only even prime, so p 1 = 2 p_1=2 . The equation then becomes

p 2 2 + p 3 2 + p 4 2 = 2219. p_2^2 + p_3^2 + p_4^2 = 2219.

We know that 2219 2 ( m o d 3 ) 2219 \equiv 2 \pmod{3} , and 0 0 and 1 1 are the only quadratic residues ( m o d 3 ) \pmod{3} , so one of the primes has to be divisible by 3 3 , and 3 3 is the only prime with that property, so p 2 = 3 p_2=3 . The equation then becomes

p 3 2 + p 4 2 = 2210. p_3^2+p_4^2 = 2210.

We know that 2210 0 ( m o d 5 ) 2210 \equiv 0 \pmod{5} , so none is divisible by 5 5 , i.e. p 3 5 p_3 \not = 5 . Since both of these primes have to be odd and less than 2210 = 48 \left \lceil \sqrt{2210} \right \rceil = 48 , we know that

p 3 , p 4 { 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 } . p_3,p_4 \in \{ 7,11,13,17,19,23,29,31,37,41,43,47\}.

Also, as p 3 < p 4 p_3 < p_4 , we know that p 3 2210 2 = 33 p_3 \leq \left \lfloor \sqrt{\frac{2210}{2}} \right \rfloor = 33 , so

p 3 { 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 } . p_3 \in \{ 7,11,13,17,19,23,29,31 \}.

Simply checking those cases leads to

( p 1 , p 2 , p 3 , p 4 ) { ( 2 , 3 , 19 , 43 ) , ( 2 , 3 , 23 , 41 ) , ( 2 , 3 , 29 , 37 ) } , (p_1,p_2,p_3,p_4) \in \{ (2,3,19,43),(2,3,23,41),(2,3,29,37) \},

which is a total of 3 \boxed{3} solutions.

Moderator note:

This solution is very similar to most other correct solutions: find p 1 = 2 , p_1=2, p 2 = 3 , p_2=3, bound the other primes, then go through the cases. The divisibility argument to rule out p 3 = 5 p_3=5 is nice, but not crucial.

Zi Song Yeoh
Jul 22, 2013

First, note that the sum if four odd numbers can't be odd, so p 1 = 2 p_{1} = 2 . Next, if a prime p p is not 3 3 , then it leaves a remainder of 1 1 when divided by 3 3 . So, if p 2 3 p_{2} \ne 3 , then the sum of the last three will be a multiple of 3 3 . But 3 2223 2 2 = 2219 3 \nmid 2223 - 2^{2} = 2219 , so p 2 = 3 p_{2} = 3 . Now, p 3 2 + p 4 2 = 2210 p_{3}^{2} + p_{4}^{2} = 2210 . Testing all cases less than 47 47 , we find that there are 3 3 solutions, namely ( p 3 , p 4 ) = ( 19 , 43 ) , ( 23 , 41 ) , ( 29 , 37 ) (p_{3}, p_{4}) = (19 , 43), (23 , 41), (29 , 37) .

Michael Tang
Jul 24, 2013

First, note that if all of p 1 , p 2 , p 3 , p 4 p_1,p_2,p_3,p_4 are odd, then the left-hand side will be even, which is a contradiction. So, we must have p 1 = 2. p_1 = 2. Then we simplify to get p 2 2 + p 3 2 + p 4 2 = 2219. p_2^2+p_3^2+p_4^2=2219. Note that all primes greater than 3 3 are equivalent to ± 1 , \pm 1, modulo 6 , 6, so the squares of all primes greater than 3 3 are equivalent to 1 ( m o d 6 ) . 1 \pmod{6}. Considering the equation modulo 6 , 6, we see that if p 2 3 , p_2 \neq 3, then p 2 2 + p 3 2 + p 4 2 1 + 1 + 1 = 3 , p_2^2+p_3^2+p_4^2 \equiv 1 + 1 + 1 = 3, which contradicts the fact that 2219 5 ( m o d 6 ) . 2219 \equiv 5 \pmod{6}. Therefore, p 2 = 3. p_2 = 3. Simplifying the equation again, we have p 3 2 + p 4 2 = 2210. p_3^2 + p_4^2 = 2210. Because 2210 = 47 , \lfloor \sqrt{2210} \rfloor = 47, we need only consider the primes from 5 5 to 47. 47. After checking all cases, we find that ( p 3 , p 4 ) = ( 19 , 43 ) , ( 23 , 41 ) , ( 29 , 37 ) . (p_3,p_4) = (19, 43), (23,41), (29, 37). There are 3 \boxed{3} solutions to the given equation.

Gino Pagano
Jul 22, 2013

In python:

listofprimes = {3,5,7,11,13,17,19,23,29,31,37,41,43,47}. [[x,y,z] for x in listofprimes for y in listofprimes for z in listofprimes if x 2+ y 2+ z**2==2219 if x < y if y < z]

Can't get the formatting to work properly since these boards use ** for bold

Moderator note:

While a computer is a very helpful tool, our Algebra/Number Theory solvables are meant to be done by hand. We just started the Computer Science weekly challenge series on Brilliant, you may want to check it out for more appropriate programming challenges.

Let ( p 1 , p 2 , p 3 , p 4 ) (p_1,p_2,p_3,p_4) be those primes,supose all of them are odd primes, then by checking (mod 4) 2223 = 3 ( m o d 4 ) 2223=3 (mod4) , but p 1 2 + p 2 2 + p 3 2 + p 4 2 = 1 + 1 + 1 + 1 = 0 ( m o d 4 ) p_1^2+p_2^2+p_3^2+p_4^2=1+1+1+1=0 (mod4) ,which is impossible.So at least one of the 4 primes must be even.Thus p 1 = 2 p_1=2 (the smallest and only even prime). In a simillar manner, using ( m o d 3 ) (mod3) , 2223 2 2 = 2219 = 2 ( m o d 3 ) 2223-2^2=2219=2 (mod3) ,but again, p 2 2 + p 3 2 + p 4 2 = 1 + 1 + 1 = 0 ( m o d 3 ) p_2^2+p_3^2+p_4^2=1+1+1=0 (mod3) ,which is impossible.So at least one of the 3 primes must divisible by 3.Thus p 2 = 3 p_2=3 (the smallest and only prime that divisible by 3). Now, p 3 2 + p 4 2 = 2210 p_3^2+p_4^2=2210 .Notice that p 4 > 33 p_4>33 .If p 4 < 33 p_4<33 ,then p 3 > 33 p_3>33 .Thus the possible values for p 4 p_4 are 37 , 41 , 43 , 47 37,41,43,47 . Only p 4 = 37 , 41 , 43 p_4=37,41,43 give prime solutions to p 3 p_3 which correspond to p 3 = 19 , 23 , 29 p_3=19,23,29 .Thus the only pairs possible are ( 2 , 3 , 29 , 37 ) , ( 2 , 3 , 23 , 43 ) , ( 2 , 3 , 19 , 47 ) (2,3,29,37),(2,3,23,43),(2,3,19,47)

Moderator note:

The final list contains some misprints, but an excellent proof otherwise. A 3-vote boost from Brilliant to promote visibility.

Can you please confirm the quadruplets given in the end of your solution?

Vicky Bro - 7 years, 10 months ago

Log in to reply

I think I misprinted it . It should be ( 2 , 3 , 29 , 37 ) ( 2 , 3 , 23 , 41 ) ( 2 , 3 , 19 , 43 ) (2,3,29,37)(2,3,23,41)(2,3,19,43)

Ivan, Kai Chin Chan - 7 years, 10 months ago
Debjit Mandal
Jul 24, 2013

p 1 2 p^2_1 + p 2 2 p^2_{2} + p 3 2 p^2_{3} + p 4 2 p ^2_{4} = 2223 2223 .
Sum of squares of four odd primes is always even but given sum is odd ⇒ 2 2 must a any one prime say p 1 p_{1}

Now, 4 4 + p 2 2 p^2_{2} + p 3 2 p^2_{3} + p 4 2 p^2_{4} = 2223 2223
p 2 2 p^2_{2} + p 3 2 p^2_{3} + p 4 2 p^2_{4} = 2219 2219

Now using modular arithmetic, Note that, 2219 2 ( m o d 3 ) 2219 \equiv 2 \pmod{3} , so if none of three terms divided evenly into 3 3 they would give a total remainder greater than 2 2 .which means that terms must be divisible by 3 3 , and the only prime divisible by 3 3 is only 3 3 say p 2 p_{2} = 3 3
Now p 3 2 p^2_{3} + p 4 2 p^2_{4} = 2210 2210

Now if we see 2210 > 47 \sqrt{2210}> 47 ; means primes less than 47 47 will satisfy the condition. Now primes are that can satisfy the condition is are ( 5 5 , 7 7 , 11 11 , 13 13 , 15 15 , 17 17 , 19 19 , 23 23 , 29 29 , 31 31 , 37 37 , 41 41 , 43 43 , 47 47 )

Now p 4 2 p^2_{4} = 2210 2210 p 3 2 p^2_{3} , now checking cases on p 3 p_{3} we get the following solutions ( 19 19 , 43 43 ),( 23 23 , 41 41 ),( 29 29 , 37 37 ).

So, the number of distinct 4 4 -tuples is ' 3 3 ' [ANSWER]

Lily Ye
Jul 24, 2013

p 1 2 + p 2 2 + p 3 2 + p 4 2 = 2223 p_{1} ^ {2} + p_{2} ^ {2} + p_{3} ^ {2} + p_{4} ^ {2} = 2223

2223 is odd. Odd + odd + odd + odd = even, so the only way you could get an odd answer is if one of the terms was even. The only even prime is 2. It is also the smallest prime, so it must be p 1 p_{1} .

2 2 + p 2 2 + p 3 2 + p 4 2 = 2223 2 ^ {2} + p_{2} ^ {2} + p_{3} ^ {2} + p_{4} ^ {2} = 2223

p 2 2 + p 3 2 + p 4 2 = 2219 p_{2} ^ {2} + p_{3} ^ {2} + p_{4} ^ {2} = 2219

Note that 2219 m o d 3 = 2 2219 \bmod 3 = 2 so if none of three terms divided evenly into 3 they would leave a total remainder greater than 2. Thus one of the terms must be divisible by 3, and the only prime divisible by 3 is 3. It is also the next greatest prime, and thus must be p 2 p_{2} .

3 2 + p 3 2 + p 4 2 = 2219 3 ^ {2} + p_{3} ^ {2} + p_{4} ^ {2} = 2219

p 3 2 + p 4 2 = 2210 p_{3} ^ {2} + p_{4} ^ {2} = 2210

4 7 2 = 2209 47^ {2} = 2209 and 1 is not a prime number, so the greatest value for either of the two terms is the next prime, 43. Check primes below 43 as p 4 p_{4} .

Option 1 where p 4 = 43 p_{4} =43 :

p 3 2 + 4 3 2 = 2210 p_{3} ^ {2} + 43 ^{2} = 2210

p 3 = 19 p_{3} = 19

Option 2 where p 4 = 41 p_{4} =41 :

p 3 2 + 4 1 2 = 2210 p_{3} ^ {2} + 41 ^{2} = 2210

p 3 = 13 p_{3} = 13

Option 3 where p 4 = 37 p_{4} = 37 :

p 3 2 + 3 7 2 = 2210 p_{3} ^ {2} + 37 ^{2} = 2210

p 3 = 29 p_{3} = 29

The next prime down is 29, so you know you've got all your options.

There are a total of 3 \textbf 3 possibilities.

Kishan K
Jul 23, 2013

Easiest method: We will use the fact that p 2 1 ( m o d 24 ) p^{2}\equiv1(mod 24) for p 5. p\ge5. . Proof: We know that every prime p 5 p\ge5 can be represented as 6 n ± 1. 6n\pm1. So, p 2 = 36 n 2 + 12 n + 1 p 2 1 = 36 n 2 + 12 n 0 ( m o d 24 ) . p^{2}= 36n^{2} + 12n +1 \Rightarrow p^{2} -1= 36n^{2} + 12n \equiv0(mod24). By taking n n as even or odd, and checking gives us the result.Similarly we can prove it for 6 n 1 6n-1 . But one must note that this is only for p 5 p\ge5 . Let the four primes be x , y , z , p x,y,z,p as given in problem respectively. x 2 1 ( m o d 24 ) , x^{2}\equiv1(mod24), y 2 1 ( m o d 24 ) , y^{2}\equiv1(mod24), Similar for z z and p p . So x 2 + y 2 + z 2 + p 2 4 ( m o d 24 ) . x^{2}+y^{2}+z^{2}+p^{2}\equiv4(mod24). But 2223 ≢ 4 ( m o d 24 ) 2223\not\equiv4(mod24) Which shows that x x must be 2 or 3.But after putting x=2,3,and again checking mod24 none of them satisfies. So another possible case will be x = 2 x=2 , y = 3 y=3 .Again checking the resultant we get 0 ( m o d 24 ) \equiv0(mod24) . Which gives z 2 + p 2 = 2210 z^{2}+p^{2}=2210 . This will be quite easy to solve by case checking or putting values of all primes till 47. We get ( z , p ) = ( 19 , 43 ) , ( 23 , 41 ) , ( 29 , 37 ) . (z,p)= (19,43),(23,41),(29,37). So values of x x =2 and y y =3 which are fix.So there will be 3 solutions.

First we note that the maximum value of any p i p_i is 43 43 .
Then we consider the squares of all these primes, and note that 2 2 2^2 is the only one that is even.
But since 2223 2223 is odd and the sum of 4 4 odd numbers is even, p 1 = 2 p_1 = 2 .
So now we need three primes from our list that sum to 2219 2219 .
We note that of the values in our list of square primes, each has a 1 1 or 9 9 as its one's digit with the exception of 5 2 = 25 5^2 = 25 .
By trial, we can eliminate 5 5 as a possibility. Next we note that the only way to get a 9 9 in the one's digit of 2219 2219 is to use two squares that end in 9 9 and one sqaure that ends in 1 1 .
The final answer from here is just trial and error.





It helps to separate them into two lists and remove the one's digits: L 9 = { 0 , 40 , 160 , 280 , 520 , 1360 , 1840 } L9 = \{0, 40, 160, 280, 520, 1360, 1840\}
L 1 = { 120 , 360 , 840 , 960 , 1680 } L1 = \{120, 360, 840, 960, 1680\}
Pick two values from L 9 L9 and pick one from L 1 L1 and try to sum to 2200 2200 .
I get { 1840 , 360 , 0 } \{1840, 360, 0\} , { 1680 , 520 , 0 } \{1680, 520, 0\} , and { 1360 , 840 , 0 } \{1360, 840, 0\} .
Looking at this answer, there might be a way to confirm that 3 must be one of the p i p_i used earlier on.



Pi Han Goh
Jul 21, 2013

First, we suppose that all primes listed are odd. Then take m o d 4 \bmod{4} to both sides of the equation.

L H S m o d 4 = ( p 1 2 + p 2 2 + p 3 2 + p 4 2 ) m o d 4 = ( 1 + 1 + 1 + 1 ) m o d 4 = 0 LHS \bmod{4} = (p_1 ^2 + p_2 ^2 + p_3 ^2 + p_4 ^2 ) \bmod{4} = (1+1+1+1) \bmod{4} = 0 , while R H S m o d 4 = 3 RHS \bmod{4} = 3 which is a contradiction.

So p 1 = 2 p_1 = 2 . Simplify the equation, we have p 2 2 + p 3 2 + p 4 2 = 2219 p_2 ^2 + p_3 ^2 + p_4 ^2 = 2219

Now suppose that primes p 2 , p 3 , p 4 p_2, p_3, p_4 are in the form of 6 n ± 1 6n \pm 1 . Take m o d 6 \bmod{6} to both sides of the equation.

L H S m o d 6 = ( p 2 2 + p 3 2 + p 4 2 ) m o d 6 = ( 1 + 1 + 1 ) = 3 LHS \bmod{6} = (p_2 ^2 + p_3 ^2 + p_4 ^2 ) \bmod{6} = (1+1+1) = 3 , while R H S m o d 6 = 1 RHS \bmod{6} = 1 which is a contradiction.

So there must be a odd prime that is not in the form of 6 n ± 1 p 2 = 3 6n \pm 1 \Rightarrow p_2 = 3 .

Simplify the equation again, we are left with p 3 2 + p 4 2 = 2210 p_3 ^2 + p_4 ^2 = 2210

Trial and error shows that there's 3 \boxed{3} solutions: ( p 3 , p 4 ) = ( 19 , 43 ) , ( 29 , 37 ) , ( 23 , 41 ) (p_3, p_4) = (19, 43), (29, 37), (23, 41) .

Harsa Mitra
Jul 23, 2013

First observation: At least one of these primes has to be even, because if they were all odd, then so would be their squares, hence the some of their squares would be even (since there are 4 summands) - but 2223 is not. So p1 has to be 2. Hence,

p2^2+p3^2+p4^2 = 2219.

Second, 2219 mod 3 = 2. If none of these 3 numbers were divisible by 3, then they would be congruent to 1 or 2 (mod 3), hence their square would be congruent to 1; so one of them has to be divisible by 3, hence must be equal to 3. Hence, p2=3. Hence,

p3^2 + p4^2 = 2210.

Now, 2210 mod 5 = 0. If p3 would be divisible by 5, so would p4 - contradiction.Since p3<p4, we have the inequality 2p3^2 < p3^2+p4^2=2210, hence p3 < sqrt(2210/2), hence p3 < 33,.... Since p3 is prime and greater that 5, the only possibilities are

7, 11, 13, 17, 19, 23, 29, 31.

Now 2210 - p3^2 has to be a square of an integer. Calculating the corresponding 8 numbers, you see that from that the only candidates who are left for p3 are

19, 23, 29.

It follows that there are 3 combinations:

(2,3,19,43), (2,3,23,41), (2,3,29,37).

Piyush Pandey
Jul 22, 2013

P^2 takes the form of 24k + 1 if P > 3. 2208 is the nearest multiple of 2223. Hence, P1 and P2 are 2 and 3 respectively. Also, if (P3)^2 = 24a + 1 and (P4)^2 = 24b + 1. Then 24a + 24b = 2208 and a + b = 92. (a,b) = (57,35), (70,22), (77,15). Three pairs. Hence, (2, 3, 19, 43); (2, 3, 23, 41); (2, 3, 29, 37)

because even prime only 2, so p1=2 (even+odd+odd+odd=even) p2^2 + p3^2 +p4^2=2219<47^2 primes less than 47 are 2,3,5,7,11,13,17,19,23,29,31,37,41,43 case 1 p4=43 p2^2+p3^2=370 only p2=3 and p3=19 case 2 p4=41 p2^2+p3^2=538 only p2=3 and p3=23 and case 3 p4=37 p2^2+p3^2=850 only p2=3 and p3=29 So there are 3 4-tuples

Mircea Digulescu
Jul 22, 2013

Since the primes are distinct, the largest one is <= Sqrt(2223 - 2^2 - 3^2 - 5^2) so p4<=43. Now write two lines one under the other: the first consists of the squared primes from 2 to 43 and the second of the sum of the largest two squared primes up until a specific index (it is actually the sum of the last two values in the first list). They are: 4 9 25 49 121 169 289 361 529 841 961 1369 1681 1849 AND 4 13 34 74 170 290 458 650 890 1370 1802

We'll start by picking a candidate p4 from the first list (starting from the end to the start). The sum of the remaining p1^2+p2^2+p3^2 must be 2223 - p4^2. So we then choose a candidate p3 for our candidate p4 such that: p3^2 < 2223 - p4^2 (otherwise we would exceed the target sum) and max(p1^2+p2^2) >= 2223 - p4^2 - p3^2 (otherwise the sum would be too low). For the second part it suffices to make sure value in the second list on the index of p3 minus 1 is larger than the sum 2223-p4^2-p3^2. For p4 and p3 we just try each p2 with p2^2 smaller than 2223-p4^2-p3^2 until we find a solution. So we just check: 1. p4 = 43, p3 = 19, p2 = 3, p1 = 2; 2. p4 = 43, p3 = 17, p2 = 7, p1 = X; 3. p4 = 43, p3 = 17, p2 = 5, p1 = X (no more checking for lower p2 because the sum would be underrun) 4. p4 = 43, p3 = 13, p2 = X (the sum is underrun so don't check any more options here) 5. p4 = 41, p3 = 23, p2 = 3, p1 = 2 6. p4 = 41, p3 = 19, p2 = 13, p1 = X 7. p4 = 41, p3 = 19, p2 = 11, p1 = X 8. p4 = 41, p3 = 19, p2 = 7, p1 = X (no more tries for lower p2 because the sum would be underrun) 9. p4 = 41, p3 = 17 (no solution here because the maximum sum with primes less than 17 is 290 - too low so no more tries for lower p3) 10. p4 = 37, p3 = 29, p2 = 3, p1 = 2 11. p4 = 37, p3 = 23, p2 = 17, p1 = X 12. p4 = 37, p3 = 23, p2 = 13, p1 = X 13. p4 = 37, p3 = 23, p2 = 11, p1 = X (no more tries for lower p2 since the sum would be underrun) 14. p4 = 31, p3 = 29, p2 = 19, p1 = X 15. p4 = 31, p3 = 29, p2 = 17, p1 = X 16. p4 = 31, p3 = 29, p2 = 13, p1 = X (stop checking lower p2) 17. p4 = 31, p3 = 23 (no solutions here since the maximum remaining sum is 650, too low) 18. p4 = 29, p3 = 23 (no solutions since the sum would be underrun; since there was no potential p3, don't check for lower p4 - the sum will always be underrun).

So we found 3 feasible choice in roughly 18 steps.

Albert Pranata
Jul 22, 2013

Check the equation by modulo 4 4 , we get R H S 3 ( m o d 4 ) RHS\equiv3(mod 4) .If p 1 , p 2 , p 3 , p 4 p_1,p_2,p_3,p_4 are odd, there is no solutions. Therefore, we must have exactly 1 1 even prime number as the solution. Since the only one even prime and the smallest prime is 2 2 , we can conclude that p 1 = 2 p_1=2 . Then, the equation become p 2 2 + p 3 2 + p 4 2 = 2219.. ) p_2^2+p_3^2+p_4^2=2219..*) Now, check ) *) with modulo 3 3 , then we have R H S 2 ( m o d 3 ) RHS\equiv2(mod 3) . If p 2 , p 3 , p 4 p_2,p_3,p_4 are not multiple of 3 3 , then there is no solution. Therefore, we must have exactly 1 1 prime number which can divide by 3 3 . From here, we can conclude that p 2 = 3 p_2=3 . Then, the equation become p 3 2 + p 4 2 = 2210 p_3^2+p_4^2=2210 which equivalent with p 3 2 + p 4 2 2210 = 0.. ) p_3^2+p_4^2-2210=0..**) By solving ) **) in p 4 p_4 using quadratic roots formula, we get that 0 < p 4 < 47 0 < p_4 < 47 because p 4 > 0 p_4 > 0 . All possible values of p 4 p_4 should be replaced in p 4 2 2210 p_4^2-2210 and the result should be the negative of a perfect square. Thus, we get the possible values of p 4 p_4 are 19 , 23 , 29 , 37 , 41 , 43 , 47 19,23,29,37,41,43,47 . After checking all possible values of p 4 p_4 , we get 3 3 pairs ( p 3 , p 4 ) (p_3,p_4) which satisfied. They are ( 23 , 41 ) ; ( 29 , 37 ) ; ( 19 , 43 ) (23,41);(29,37);(19,43) . So, the number of distinct tuples ( p 1 , p 2 , p 3 , p 4 ) (p_1,p_2,p_3,p_4) which satisfies the equation is 3 3 .

N B : NB: The solutions are ( 2 , 3 , 23 , 41 ) ; ( 2 , 3 , 29 , 37 ) ; ( 2 , 3 , 19 , 43 ) (2,3,23,41);(2,3,29,37);(2,3,19,43) and easy to check that all tuples satisfy the equation above.

Md. Imrul Hassan
Jul 22, 2013

Firstly, note that p 1 = 2 p_1 = 2 as otherwise the sum of squares of four odd primes would have been even. So, we have p 2 2 + p 3 2 + p 4 2 = 2219 p_2^2 + p_3^2 + p_4^2 = 2219 .

Secondly, we will show that p 2 = 3 p_2 = 3 using modular arithmetic. Let, p > 3 p > 3 be a prime number, then p 2 = 1 ( m o d 3 ) p^2 = 1 (mod 3) . If p 2 > 3 p_2 > 3 , then so would be p 3 p_3 and p 4 p_4 . So, we have p 2 2 + p 3 2 + p 4 2 = 1 + 1 + 1 = 0 2219 p_2^2 + p_3^2 + p_4^2 = 1+1+1 = 0 \neq 2219 . So, p 2 p_2 must be equal to 3 and p 3 2 + p 4 2 = 2210 p_3^2 + p_4^2 = 2210 .

Finally, we try prime numbers below 2210 2 33 \sqrt{ \frac{2210}{2} } \approx 33 for possible values of p 3 p_3 and check if 2210 p 3 2 2210 - p_3^2 is a square of a prime or not. Doing so gives us three set of values, namely - (2,3,19,43), (2,3,23,41), (2,3,29,37).

Daniel Chiu
Jul 21, 2013

Squares are either 0 or 1, modulo both 3 and 4. Therefore, since 2223 3 ( m o d 4 ) 2223\equiv 3\pmod 4 , one of the squares is 0 modulo 4, and so p 1 = 2 p_1=2 . Now, p 2 2 + p 3 2 + p 4 2 = 2219 p_2^2+p_3^2+p_4^2=2219 Since 2219 2 ( m o d 3 ) 2219\equiv 2\pmod 3 , one of the squares is 0 modulo 3, and so p 2 = 3 p_2=3 . We now have p 3 2 + p 4 2 = 2210 p_3^2+p_4^2=2210 It is easy to check squares of primes now. Checking, we find 1 9 2 + 4 3 2 = 2 3 2 + 4 1 2 = 2 9 2 + 3 7 2 = 2210 19^2+43^2=23^2+41^2=29^2+37^2=2210 The answer is 3 \boxed{3} .

Very nice!

Mircea Digulescu - 7 years, 10 months ago
Douglas Zare
Jul 21, 2013

Squares are either 0 or 1 mod 4. Since 2223 is 3 mod 4, it must be 0+1+1+1 mod 4. So, one of the primes has a square which is 0 mod 4, and that prime is 2.

Then p 2 2 + p 3 2 + p 4 2 = 2219 2 m o d 3 p_2^2+p_3^2+p_4^2 = 2219 \equiv 2 \mod 3 . Squares are 0 or 1 mod 3, so one of the primes must have a square which is 0 mod 3, and that prime is 3.

So, p 3 2 + p 4 2 = 2210 p_3^2+p_4^2 = 2210 . We check the possibilities for p 3 < 1105 = 33.2 p_3 < \sqrt{1105} = 33.2 and find that ( p 3 , p 4 ) (p_3,p_4) could be ( 19 , 43 ) (19,43) , ( 23 , 41 ) (23,41) , or ( 29 , 37 ) (29,37) .

Two quick comments:

  • In the first step you can just work mod 2 to observe that one of the primes must be even. Mod 4 is a slight overkill.

  • In the final step, all of the answers I've seen end up with some brute force enumeration. I think it is slightly more illuminating to factor 2210 = 2 × 5 × 13 × 17 2210=2\times 5\times 13\times 17 . Each of those primes is a sum of two squares in a unique way which is trivial to find. Two combine these into a representation of 2210 itself as a sum of two squares, we multiply together the corresponding gaussian integers:

( 1 + i ) ( 2 + i ) ( 3 + 2 i ) ( 4 + i ) = 23 + 41 i (1+i)(2+i)(3+2i)(4+i) = -23+41i ( 1 + i ) ( 2 + i ) ( 3 + 2 i ) ( 4 i ) = 1 + 41 i (1+i)(2+i)(3+2i)(4-i) = -1+41i ( 1 + i ) ( 2 + i ) ( 3 2 i ) ( 4 + i ) = 29 + 37 i (1+i)(2+i)(3-2i)(4+i) = 29+37i ( 1 + i ) ( 2 + i ) ( 3 2 i ) ( 4 i ) = 43 + 19 i (1+i)(2+i)(3-2i)(4-i) = -43+19i

This still requires some enumeration to make sure there are no more combinations but it feels conceptually better (to me).

Alon Amit - 7 years, 10 months ago

Log in to reply

(the 41 should be 47 in the second equation).

Alon Amit - 7 years, 10 months ago

I don't think using mod 4 is overkill. Given that p 1 < p 2 < p 3 < p 4 p_1 <p_2 < p_3 < p_4 , then knowing that there are an odd number of even primes you can conclude that there is just one two. However, without that artificial assumption you would have to rule out 2 2 + 2 2 + 2 2 + p 4 2 2^2+2^2+2^2+p_4^2 . It's common to use that squares are quite restricted mod 4 or mod 24.

It is a nice observation that we can use the prime factorization and then Gaussian integers to find the ways to write an integer as a sum of two squares. However, you end up checking primality of a large number of factors. It would take an extremely large replacement for 2210 for that method to be faster than checking whether 2210 prime ( n ) 2 \sqrt{2210-\operatorname{prime}(n)^2} is prime.

Douglas Zare - 7 years, 10 months ago
Daniel Viana
Jul 21, 2013

p 1 = 2 p_1=2 ,because de sum of them are odd. so p 2 2 + p 3 2 + p 4 2 = 2219 p^2_2+p^2_3+p^2_4=2219 but,is p p is not 3, p 2 p^2 leaves rest 1 divided by 3,so p 2 = 3 p_2=3

Hence testing ,we have the solutions p 3 = 19 ; 23 ; 29 p_3=19;23;29

Sarith Imaduwage
Apr 12, 2016

Billy Sugiarto
Sep 14, 2015

It is pretty obvious that ( p 1 , p 2 ) = ( 2 , 3 ) (p_{1}, p_{2}) = (2, 3) . Using ( m o d 6 ) (mod 6) we got 3 pairs of ( p 3 , p 4 ) (p_{3}, p_{4}) satisfying the above equality.

Mark Kong
Jun 3, 2014

For those of you who are worried about squaring numbers larger than 10:

If all of the primes are odd, then the sum is even. However, 2223 is odd, so at least one of the primes must be even. The only even prime is 2, so 2 must be p 1 {p}_{1} . Therefore, p 2 + p 3 + p 4 = 2219 { p }_{ 2 }+{ p }_{ 3 }+{ p }_{ 4 }=2219 . Suppose that none of the remaining primes is divisible by 3. If the prime is 1 mod 3, then its square is also 1 mod 3. Similarly, if the prime is 2 mod 3, its square is 1 mod 3. Therefore, the sum of the squares of the primes mod 3 is 1 + 1 + 1 0 1+1+1\equiv 0 (mod 3). However, 2219 2 2219\equiv 2 (mod 3), so one of the primes must be divisible by 3. The only prime that is divisible by 3 is 3, so p 2 = 3 p_2=3 .

We are left with p 3 + p 4 = 2210 p_3+p_4=2210 . We have that p 3 p_3 and p 4 p_4 are odd. Therefore, they can be expressed as (a-b) and (a+b) where a and b are integers with different parity. We must now solve ( a b ) 2 + ( a + b ) 2 = 2210 (a-b)^2+(a+b)^2=2210 . Because ( a b ) 2 + ( a b ) 2 = ( b a ) 2 + ( b + a ) 2 (a-b)^2+(a-b)^2=(b-a)^2+(b+a)^2 , we can assume without loss of generality that a is even and b is odd. In other words, we can express a as 2r and we can express b as 2k+1 for integers r and k.

( a b ) 2 + ( a + b ) 2 = 2 a 2 + 2 b 2 = 2 ( a 2 + b 2 ) = 2210 (a-b)^2+(a+b)^2=2a^2+2b^2=2(a^2+b^2)=2210

a 2 + b 2 = 1105 a^2+b^2=1105

( 2 r ) 2 + ( 2 k + 1 ) 2 ) = 1105 (2r)^2+(2k+1)^2)=1105

4 r 2 + 4 k 2 + 4 k + 1 = 4 ( r 2 + k 2 + k ) + 1 = 1105 4r^2+4k^2+4k+1=4(r^2+k^2+k)+1=1105

4 ( r 2 + k 2 + k ) = 1104 4(r^2+k^2+k)=1104

r 2 + k 2 + k = 276 r^2+k^2+k=276

Because k 2 k^2 and k k have the same parity, k 2 + k k^2+k is even. Therefore, 276 ( k 2 + k ) = r 2 276-(k^2+k)=r^2 is even. If r 2 r^2 is even, r r is even, so r 2 r^2 is divisible by 4. Therefore, 276 r 2 = k 2 + k = k ( k + 1 ) 276-r^2=k^2+k=k(k+1) is divisible by 4, so either k k or k + 1 k+1 is divisible by 4. We now divide both sides of the equation by 4 to get r 2 4 + k ( k + 1 ) 4 = 69 \frac { { r }^{ 2 } }{ 4 } +\frac { k(k+1) }{ 4 } =69 . Note that k ( k + 1 ) 4 > k 2 4 = ( k 2 ) 2 \frac { k(k+1) }{ 4 } >{ { \frac { { k }^{ 2 } }{ 4 } }=\left( \frac { k }{ 2 } \right) }^{ 2 } . Since r 2 r^2 is always positive for real r r , k ( k + 1 ) 4 < 69 \frac { k(k+1) }{ 4 } <69 , so ( k 2 ) 2 < 69 {\left( \frac { k }{ 2 } \right) }^{ 2 }<69 . We have that 9 2 = 81 > 69 9^2=81>69 , so k 2 < 9 \frac { k }{ 2 } <9 , so k < 18 k<18 . However, we know that k k or ( k + 1 ) (k+1) is divisible by 4, so k { 3 , 4 , 7 , 8 , 11 , 12 , 15 , 16 } k\in \left\{ 3,4,7,8,11,12,15,16 \right\} . We now plug in these values of k to find how many possible values of r r there can be that follow the equation. We plug those values back in to solve for a a and b b , which we then plug back in to find p 3 p_3 and p 4 p_4 . We find that there are 3 solutions.

Evan Chien
Jul 25, 2013

First observation: At least one of these primes has to be even, because if they were all odd, then so would be their squares, hence the some of their squares would be even (since there are 4 summands) - but 2223 is not. So p1 has to be 2. Hence,

p2^2+p3^2+p4^2 = 2219.

Second, 2219 mod 3 = 2. If none of these 3 numbers were divisible by 3, then they would be congruent to 1 or 2 (mod 3), hence their square would be congruent to 1; so one of them has to be divisible by 3, hence must be equal to 3. Hence, p2=3. Hence,

p3^2 + p4^2 = 2210.

Now, 2210 mod 5 = 0. If p3 would be divisible by 5, so would p4 - contradiction.Since p3<p4, we have the inequality 2p3^2 < p3^2+p4^2=2210, hence p3 < sqrt(2210/2), hence p3 < 33,.... Since p3 is prime and greater that 5, the only possibilities are

7, 11, 13, 17, 19, 23, 29, 31.

Now 2210 - p3^2 has to be a square of an integer. Calculating the corresponding 8 numbers, you see that from that the only candidates who are left for p3 are

19, 23, 29.

It follows that there are 3 combinations:

(2,3,19,43), (2,3,23,41), (2,3,29,37).

Mharfe Micaroz
Jul 23, 2013

First observation: At least one of these primes has to be even, because if they were all odd, then so would be their squares, hence the some of their squares would be even (since there are 4 summands) - but 2223 is not. So p1 has to be 2. Hence,

p2^2+p3^2+p4^2 = 2219.

Second, 2219 mod 3 = 2. If none of these 3 numbers were divisible by 3, then they would be congruent to 1 or 2 (mod 3), hence their square would be congruent to 1; so one of them has to be divisible by 3, hence must be equal to 3. Hence, p2=3. Hence,

p3^2 + p4^2 = 2210.

Now, 2210 mod 5 = 0. If p3 would be divisible by 5, so would p4 - contradiction.Since p3<p4, we have the inequality 2p3^2 < p3^2+p4^2=2210, hence p3 < sqrt(2210/2), hence p3 < 33,.... Since p3 is prime and greater that 5, the only possibilities are

7, 11, 13, 17, 19, 23, 29, 31.

Now 2210 - p3^2 has to be a square of an integer. Calculating the corresponding 8 numbers, you see that from that the only candidates who are left for p3 are

19, 23, 29.

It follows that there are 3 combinations:

(2,3,19,43), (2,3,23,41), (2,3,29,37).

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...