How many distinct 4 -tuples of (positive) primes ( p 1 , p 2 , p 3 , p 4 ) are there such that p 1 < p 2 < p 3 < p 4 and
p 1 2 + p 2 2 + p 3 2 + p 4 2 = 2 2 2 3 ?
This problem is posed by Derek K.
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.
Bounding 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!
NICE!
Did the same! Nice!
Very good solution!!!!
awesome solution!
Brilliant thinking! Same way
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 . Thus p 2 2 + p 3 2 + p 4 2 = 2 2 1 9 . 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 . Thus p 3 2 + p 4 2 = 2 2 1 0 . (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 × 1 3 × 1 7 = ( 1 + i ) ( 1 − i ) ( 2 + i ) ( 2 − i ) ( 3 + 2 i ) ( 3 − 2 i ) ( 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 ) where a , b , c , d = ± 1 . Running through the options (and ignoring signs and ordering), we obtain the options ( p 3 , p 4 ) = ( 1 , 4 7 ) , ( 1 9 , 4 3 ) , ( 2 3 , 4 1 ) , ( 2 9 , 3 7 ) . The first is not allowable (1 is not prime), so we have 3 solutions.
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 added on) form a Euclidean domain, and its primes are:
(i) odd integer primes congruent to 3 modulo 4 ,
(ii) 1 + i and 1 − i ,
(iii) numbers of the form a + b i where a and b are integers and a 2 + b 2 is congruent to 1 modulo 4 .
Thus
(
1
+
i
)
(
1
−
i
)
(
2
+
i
)
(
2
−
i
)
(
3
+
2
i
)
(
3
−
2
i
)
(
4
+
i
)
(
4
−
i
)
=
2
2
1
0
factorises
2
0
1
0
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
)
. Each of the eight primes in the factorisation of
2
2
1
0
must divide one of
p
3
+
i
p
4
and
p
3
−
i
p
4
. Note that the eight prime factors come in four complex conjugate pairs. If (for example)
1
+
i
divides
p
3
+
i
p
4
, then (taking complex conjugates)
1
−
i
must divide
p
3
−
i
p
4
and hence (since it only appears once in the prime factorisation of
2
2
1
0
) does not divide
p
3
+
i
p
4
. Thus one of each complex conjugate pair divides
p
3
+
i
p
4
, with the other half of each pair dividing
p
3
−
i
p
4
. Thus we can find
a
,
b
,
c
,
d
=
±
1
such that
1
+
a
i
,
2
+
b
i
,
3
+
2
c
i
,
4
+
d
i
all divide
p
3
+
i
p
4
, with
1
−
a
i
,
2
−
b
i
,
3
−
2
c
i
,
4
−
d
i
all dividing
p
3
−
i
p
4
. Apart from these four factors,
p
3
+
i
p
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
)
where
u
is a unit in the Gaussian integers (a number whose inverse is a Gaussian integer), namely one of
±
1
,
±
i
. The phrase
to within association
means
multiplying by a unit if necessary
. When we run through the options for
a
,
b
,
c
,
d
, there will be cases where
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
)
=
−
2
3
+
4
1
i
but
−
i
(
1
+
i
)
(
2
+
i
)
(
3
+
2
i
)
(
4
+
i
)
=
4
1
+
2
3
i
Note that the real reason why
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).
Nice solution, but how do you get the equation after "To within association, this means that?"
Consider parity. The left hand side needs to be odd, so p 1 is even, and 2 is the only even prime, so p 1 = 2 . The equation then becomes
p 2 2 + p 3 2 + p 4 2 = 2 2 1 9 .
We know that 2 2 1 9 ≡ 2 ( m o d 3 ) , and 0 and 1 are the only quadratic residues ( m o d 3 ) , so one of the primes has to be divisible by 3 , and 3 is the only prime with that property, so p 2 = 3 . The equation then becomes
p 3 2 + p 4 2 = 2 2 1 0 .
We know that 2 2 1 0 ≡ 0 ( m o d 5 ) , so none is divisible by 5 , i.e. p 3 = 5 . Since both of these primes have to be odd and less than ⌈ 2 2 1 0 ⌉ = 4 8 , we know that
p 3 , p 4 ∈ { 7 , 1 1 , 1 3 , 1 7 , 1 9 , 2 3 , 2 9 , 3 1 , 3 7 , 4 1 , 4 3 , 4 7 } .
Also, as p 3 < p 4 , we know that p 3 ≤ ⌊ 2 2 2 1 0 ⌋ = 3 3 , so
p 3 ∈ { 7 , 1 1 , 1 3 , 1 7 , 1 9 , 2 3 , 2 9 , 3 1 } .
Simply checking those cases leads to
( p 1 , p 2 , p 3 , p 4 ) ∈ { ( 2 , 3 , 1 9 , 4 3 ) , ( 2 , 3 , 2 3 , 4 1 ) , ( 2 , 3 , 2 9 , 3 7 ) } ,
which is a total of 3 solutions.
This solution is very similar to most other correct solutions: find p 1 = 2 , p 2 = 3 , bound the other primes, then go through the cases. The divisibility argument to rule out p 3 = 5 is nice, but not crucial.
First, note that the sum if four odd numbers can't be odd, so p 1 = 2 . Next, if a prime p is not 3 , then it leaves a remainder of 1 when divided by 3 . So, if p 2 = 3 , then the sum of the last three will be a multiple of 3 . But 3 ∤ 2 2 2 3 − 2 2 = 2 2 1 9 , so p 2 = 3 . Now, p 3 2 + p 4 2 = 2 2 1 0 . Testing all cases less than 4 7 , we find that there are 3 solutions, namely ( p 3 , p 4 ) = ( 1 9 , 4 3 ) , ( 2 3 , 4 1 ) , ( 2 9 , 3 7 ) .
First, note that if all of 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 . Then we simplify to get p 2 2 + p 3 2 + p 4 2 = 2 2 1 9 . Note that all primes greater than 3 are equivalent to ± 1 , modulo 6 , so the squares of all primes greater than 3 are equivalent to 1 ( m o d 6 ) . Considering the equation modulo 6 , we see that if p 2 = 3 , then p 2 2 + p 3 2 + p 4 2 ≡ 1 + 1 + 1 = 3 , which contradicts the fact that 2 2 1 9 ≡ 5 ( m o d 6 ) . Therefore, p 2 = 3 . Simplifying the equation again, we have p 3 2 + p 4 2 = 2 2 1 0 . Because ⌊ 2 2 1 0 ⌋ = 4 7 , we need only consider the primes from 5 to 4 7 . After checking all cases, we find that ( p 3 , p 4 ) = ( 1 9 , 4 3 ) , ( 2 3 , 4 1 ) , ( 2 9 , 3 7 ) . There are 3 solutions to the given equation.
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
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 ) be those primes,supose all of them are odd primes, then by checking (mod 4) 2 2 2 3 = 3 ( m o d 4 ) , but p 1 2 + p 2 2 + p 3 2 + p 4 2 = 1 + 1 + 1 + 1 = 0 ( m o d 4 ) ,which is impossible.So at least one of the 4 primes must be even.Thus p 1 = 2 (the smallest and only even prime). In a simillar manner, using ( m o d 3 ) , 2 2 2 3 − 2 2 = 2 2 1 9 = 2 ( m o d 3 ) ,but again, p 2 2 + p 3 2 + p 4 2 = 1 + 1 + 1 = 0 ( m o d 3 ) ,which is impossible.So at least one of the 3 primes must divisible by 3.Thus p 2 = 3 (the smallest and only prime that divisible by 3). Now, p 3 2 + p 4 2 = 2 2 1 0 .Notice that p 4 > 3 3 .If p 4 < 3 3 ,then p 3 > 3 3 .Thus the possible values for p 4 are 3 7 , 4 1 , 4 3 , 4 7 . Only p 4 = 3 7 , 4 1 , 4 3 give prime solutions to p 3 which correspond to p 3 = 1 9 , 2 3 , 2 9 .Thus the only pairs possible are ( 2 , 3 , 2 9 , 3 7 ) , ( 2 , 3 , 2 3 , 4 3 ) , ( 2 , 3 , 1 9 , 4 7 )
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?
Log in to reply
I think I misprinted it . It should be ( 2 , 3 , 2 9 , 3 7 ) ( 2 , 3 , 2 3 , 4 1 ) ( 2 , 3 , 1 9 , 4 3 )
p
1
2
+
p
2
2
+
p
3
2
+
p
4
2
=
2
2
2
3
.
Sum of squares of four odd primes is always even but given sum is odd ⇒
2
must a any one prime say
p
1
Now,
4
+
p
2
2
+
p
3
2
+
p
4
2
=
2
2
2
3
⇒
p
2
2
+
p
3
2
+
p
4
2
=
2
2
1
9
Now using modular arithmetic,
Note that,
2
2
1
9
≡
2
(
m
o
d
3
)
, so if none of three terms divided evenly into
3
they would give a total remainder greater than
2
.which means that terms must be divisible by
3
, and the only prime divisible by
3
is only
3
say
p
2
=
3
Now
p
3
2
+
p
4
2
=
2
2
1
0
Now if we see 2 2 1 0 > 4 7 ; means primes less than 4 7 will satisfy the condition. Now primes are that can satisfy the condition is are ( 5 , 7 , 1 1 , 1 3 , 1 5 , 1 7 , 1 9 , 2 3 , 2 9 , 3 1 , 3 7 , 4 1 , 4 3 , 4 7 )
Now p 4 2 = 2 2 1 0 − p 3 2 , now checking cases on p 3 we get the following solutions ( 1 9 , 4 3 ),( 2 3 , 4 1 ),( 2 9 , 3 7 ).
So, the number of distinct 4 -tuples is ' 3 ' [ANSWER]
p 1 2 + p 2 2 + p 3 2 + p 4 2 = 2 2 2 3
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 .
2 2 + p 2 2 + p 3 2 + p 4 2 = 2 2 2 3
p 2 2 + p 3 2 + p 4 2 = 2 2 1 9
Note that 2 2 1 9 m o d 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 .
3 2 + p 3 2 + p 4 2 = 2 2 1 9
p 3 2 + p 4 2 = 2 2 1 0
4 7 2 = 2 2 0 9 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 .
Option 1 where p 4 = 4 3 :
p 3 2 + 4 3 2 = 2 2 1 0
p 3 = 1 9
Option 2 where p 4 = 4 1 :
p 3 2 + 4 1 2 = 2 2 1 0
p 3 = 1 3
Option 3 where p 4 = 3 7 :
p 3 2 + 3 7 2 = 2 2 1 0
p 3 = 2 9
The next prime down is 29, so you know you've got all your options.
There are a total of 3 possibilities.
Easiest method: We will use the fact that p 2 ≡ 1 ( m o d 2 4 ) for p ≥ 5 . . Proof: We know that every prime p ≥ 5 can be represented as 6 n ± 1 . So, p 2 = 3 6 n 2 + 1 2 n + 1 ⇒ p 2 − 1 = 3 6 n 2 + 1 2 n ≡ 0 ( m o d 2 4 ) . By taking n as even or odd, and checking gives us the result.Similarly we can prove it for 6 n − 1 . But one must note that this is only for p ≥ 5 . Let the four primes be x , y , z , p as given in problem respectively. x 2 ≡ 1 ( m o d 2 4 ) , y 2 ≡ 1 ( m o d 2 4 ) , Similar for z and p . So x 2 + y 2 + z 2 + p 2 ≡ 4 ( m o d 2 4 ) . But 2 2 2 3 ≡ 4 ( m o d 2 4 ) Which shows that 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 , y = 3 .Again checking the resultant we get ≡ 0 ( m o d 2 4 ) . Which gives z 2 + p 2 = 2 2 1 0 . This will be quite easy to solve by case checking or putting values of all primes till 47. We get ( z , p ) = ( 1 9 , 4 3 ) , ( 2 3 , 4 1 ) , ( 2 9 , 3 7 ) . So values of x =2 and y =3 which are fix.So there will be 3 solutions.
First we note that the maximum value of any
p
i
is
4
3
.
Then we consider the squares of all these primes, and note that
2
2
is the only one that is even.
But since
2
2
2
3
is odd and the sum of
4
odd numbers is even,
p
1
=
2
.
So now we need three primes from our list that sum to
2
2
1
9
.
We note that of the values in our list of square primes, each has a
1
or
9
as its one's digit with the exception of
5
2
=
2
5
.
By trial, we can eliminate
5
as a possibility.
Next we note that the only way to get a
9
in the one's digit of
2
2
1
9
is to use two squares that end in
9
and one sqaure that ends in
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
,
4
0
,
1
6
0
,
2
8
0
,
5
2
0
,
1
3
6
0
,
1
8
4
0
}
L
1
=
{
1
2
0
,
3
6
0
,
8
4
0
,
9
6
0
,
1
6
8
0
}
Pick two values from
L
9
and pick one from
L
1
and try to sum to
2
2
0
0
.
I get
{
1
8
4
0
,
3
6
0
,
0
}
,
{
1
6
8
0
,
5
2
0
,
0
}
, and
{
1
3
6
0
,
8
4
0
,
0
}
.
Looking at this answer, there might be a way to confirm that 3 must be one of the
p
i
used earlier on.
First, we suppose that all primes listed are odd. Then take m o d 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 , while R H S m o d 4 = 3 which is a contradiction.
So p 1 = 2 . Simplify the equation, we have p 2 2 + p 3 2 + p 4 2 = 2 2 1 9
Now suppose that primes p 2 , p 3 , p 4 are in the form of 6 n ± 1 . Take m o d 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 , while R H S m o d 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 .
Simplify the equation again, we are left with p 3 2 + p 4 2 = 2 2 1 0
Trial and error shows that there's 3 solutions: ( p 3 , p 4 ) = ( 1 9 , 4 3 ) , ( 2 9 , 3 7 ) , ( 2 3 , 4 1 ) .
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).
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
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.
Check the equation by modulo 4 , we get R H S ≡ 3 ( m o d 4 ) .If p 1 , p 2 , p 3 , p 4 are odd, there is no solutions. Therefore, we must have exactly 1 even prime number as the solution. Since the only one even prime and the smallest prime is 2 , we can conclude that p 1 = 2 . Then, the equation become p 2 2 + p 3 2 + p 4 2 = 2 2 1 9 . . ∗ ) Now, check ∗ ) with modulo 3 , then we have R H S ≡ 2 ( m o d 3 ) . If p 2 , p 3 , p 4 are not multiple of 3 , then there is no solution. Therefore, we must have exactly 1 prime number which can divide by 3 . From here, we can conclude that p 2 = 3 . Then, the equation become p 3 2 + p 4 2 = 2 2 1 0 which equivalent with p 3 2 + p 4 2 − 2 2 1 0 = 0 . . ∗ ∗ ) By solving ∗ ∗ ) in p 4 using quadratic roots formula, we get that 0 < p 4 < 4 7 because p 4 > 0 . All possible values of p 4 should be replaced in p 4 2 − 2 2 1 0 and the result should be the negative of a perfect square. Thus, we get the possible values of p 4 are 1 9 , 2 3 , 2 9 , 3 7 , 4 1 , 4 3 , 4 7 . After checking all possible values of p 4 , we get 3 pairs ( p 3 , p 4 ) which satisfied. They are ( 2 3 , 4 1 ) ; ( 2 9 , 3 7 ) ; ( 1 9 , 4 3 ) . So, the number of distinct tuples ( p 1 , p 2 , p 3 , p 4 ) which satisfies the equation is 3 .
N B : The solutions are ( 2 , 3 , 2 3 , 4 1 ) ; ( 2 , 3 , 2 9 , 3 7 ) ; ( 2 , 3 , 1 9 , 4 3 ) and easy to check that all tuples satisfy the equation above.
Firstly, note that 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 = 2 2 1 9 .
Secondly, we will show that p 2 = 3 using modular arithmetic. Let, p > 3 be a prime number, then p 2 = 1 ( m o d 3 ) . If p 2 > 3 , then so would be p 3 and p 4 . So, we have p 2 2 + p 3 2 + p 4 2 = 1 + 1 + 1 = 0 = 2 2 1 9 . So, p 2 must be equal to 3 and p 3 2 + p 4 2 = 2 2 1 0 .
Finally, we try prime numbers below 2 2 2 1 0 ≈ 3 3 for possible values of p 3 and check if 2 2 1 0 − 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).
Squares are either 0 or 1, modulo both 3 and 4. Therefore, since 2 2 2 3 ≡ 3 ( m o d 4 ) , one of the squares is 0 modulo 4, and so p 1 = 2 . Now, p 2 2 + p 3 2 + p 4 2 = 2 2 1 9 Since 2 2 1 9 ≡ 2 ( m o d 3 ) , one of the squares is 0 modulo 3, and so p 2 = 3 . We now have p 3 2 + p 4 2 = 2 2 1 0 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 = 2 2 1 0 The answer is 3 .
Very nice!
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 = 2 2 1 9 ≡ 2 m o d 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 = 2 2 1 0 . We check the possibilities for p 3 < 1 1 0 5 = 3 3 . 2 and find that ( p 3 , p 4 ) could be ( 1 9 , 4 3 ) , ( 2 3 , 4 1 ) , or ( 2 9 , 3 7 ) .
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 2 2 1 0 = 2 × 5 × 1 3 × 1 7 . 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 ) = − 2 3 + 4 1 i ( 1 + i ) ( 2 + i ) ( 3 + 2 i ) ( 4 − i ) = − 1 + 4 1 i ( 1 + i ) ( 2 + i ) ( 3 − 2 i ) ( 4 + i ) = 2 9 + 3 7 i ( 1 + i ) ( 2 + i ) ( 3 − 2 i ) ( 4 − i ) = − 4 3 + 1 9 i
This still requires some enumeration to make sure there are no more combinations but it feels conceptually better (to me).
Log in to reply
(the 41 should be 47 in the second equation).
I don't think using mod 4 is overkill. Given that 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 . 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 2 2 1 0 − p r i m e ( n ) 2 is prime.
p 1 = 2 ,because de sum of them are odd. so p 2 2 + p 3 2 + p 4 2 = 2 2 1 9 but,is p is not 3, p 2 leaves rest 1 divided by 3,so p 2 = 3
Hence testing ,we have the solutions p 3 = 1 9 ; 2 3 ; 2 9
It is pretty obvious that ( p 1 , p 2 ) = ( 2 , 3 ) . Using ( m o d 6 ) we got 3 pairs of ( p 3 , p 4 ) satisfying the above equality.
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 . Therefore, p 2 + p 3 + p 4 = 2 2 1 9 . 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 (mod 3). However, 2 2 1 9 ≡ 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 .
We are left with p 3 + p 4 = 2 2 1 0 . We have that p 3 and 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 = 2 2 1 0 . Because ( 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 ) = 2 2 1 0
a 2 + b 2 = 1 1 0 5
( 2 r ) 2 + ( 2 k + 1 ) 2 ) = 1 1 0 5
4 r 2 + 4 k 2 + 4 k + 1 = 4 ( r 2 + k 2 + k ) + 1 = 1 1 0 5
4 ( r 2 + k 2 + k ) = 1 1 0 4
r 2 + k 2 + k = 2 7 6
Because k 2 and k have the same parity, k 2 + k is even. Therefore, 2 7 6 − ( k 2 + k ) = r 2 is even. If r 2 is even, r is even, so r 2 is divisible by 4. Therefore, 2 7 6 − r 2 = k 2 + k = k ( k + 1 ) is divisible by 4, so either k or k + 1 is divisible by 4. We now divide both sides of the equation by 4 to get 4 r 2 + 4 k ( k + 1 ) = 6 9 . Note that 4 k ( k + 1 ) > 4 k 2 = ( 2 k ) 2 . Since r 2 is always positive for real r , 4 k ( k + 1 ) < 6 9 , so ( 2 k ) 2 < 6 9 . We have that 9 2 = 8 1 > 6 9 , so 2 k < 9 , so k < 1 8 . However, we know that k or ( k + 1 ) is divisible by 4, so k ∈ { 3 , 4 , 7 , 8 , 1 1 , 1 2 , 1 5 , 1 6 } . We now plug in these values of k to find how many possible values of r there can be that follow the equation. We plug those values back in to solve for a and b , which we then plug back in to find p 3 and p 4 . We find that there are 3 solutions.
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).
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).
Problem Loading...
Note Loading...
Set Loading...
If all primes 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 is even, which is a contradiction. This implies p 1 = 2 . We have p 2 2 + p 3 2 + p 4 2 = 2 2 2 3 − 4 = 2 2 1 9 . If p 2 = 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 ) , which is a contradiction to the fact that 3 does not divide 2 2 1 9 . Hence p 2 = 3 . Now we have p 3 2 + p 4 2 = 2 2 1 9 − 9 = 2 2 1 0 . Since p 4 2 < p 3 2 + p 4 2 < 2 p 4 2 , it follows that 1 1 0 5 = 2 2 2 1 0 < p 4 2 < 2 2 1 0 . This implies p 4 is a member of the set { 3 7 , 4 1 , 4 3 , 4 7 } . Running through all the cases, we find ( p 3 , p 4 ) = ( 2 9 , 3 7 ) , ( 2 3 , 4 1 ) , and ( 1 9 , 4 3 ) . Hence there are 3 distinct 4-tuples ( p 1 , p 2 , p 3 , p 4 ) of primes satisfying the given condition, namely ( 2 , 3 , 2 9 , 3 7 ) , ( 2 , 3 , 2 3 , 4 1 ) , and ( 2 , 3 , 1 9 , 4 3 ) .