Inspired in Chat
True or False?
In a primitive pythagorean triplet, at least one of the three integers must be a prime.
Note: A primitive pythagorean triplet is one in which the GCD of all three terms is 1. In particular,
(
6
,
8
,
1
0
)
is
not
a primitive pythagorean triplet because they have a common divisor of 2.
Examples of primitive pythagorean triplets are:
(
3
,
4
,
5
)
,
(
5
,
1
2
,
1
3
)
,
(
7
,
3
4
,
2
5
)
,
(
8
,
1
5
,
1
7
)
,
(
9
,
4
0
,
4
1
)
,
(
1
2
,
3
5
,
3
7
)
.
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.
10 solutions
Ah! Too much of haste :/
Quite an odd place to get inspired :P With whom were you chatting? Indeed nice problem.
Log in to reply
maybe he was chatting on Slack :)
Log in to reply
Obviously! -_- But with whom?
Log in to reply
@Nihar Mahajan – The community maybe! -_-
And That's not an"of course" thing. :3
A few more examples: ( 3 3 , 5 6 , 6 5 ) , ( 3 6 , 7 7 , 8 5 ) , ( 4 4 , 1 1 7 , 1 2 5 ) , ( 2 4 , 1 4 3 , 1 4 5 ) ,
( 5 7 , 1 7 6 , 1 8 5 ) , ( 2 1 , 2 2 0 , 2 2 1 ) , ( 1 1 9 , 1 2 0 , 1 6 9 ) , . . . .
They seem to be quite common. No primitive triple can have all elements prime, but it would appear that the respective sets of primitive triples with zero, one or two primes are each infinite.
Is this a SAT problem?
Can you mathematically prove the above result?
Log in to reply
If you're referring to my comment, then I'm working on it. I may post a note on the subject if I can come up with some proofs, (or even if not so that others can provide some input into the matter).
Log in to reply
I think using the paramitization of primitive solutions would help(pretty sure u already thought of that): ( 2 a b , a 2 − b 2 , a 2 + b 2 ) , ( a , b ) = 1 .
For zero prime simply make sure that a 2 + b 2 is composite and a − b = 1 . e.g. a ≡ 1 , b ≡ 2 ( m o d 5 ) .
For one prime consider a 2 + b 2 = p where p ≡ 1 ( m o d 4 ) is a prime.(try to prove that there exists an infinite number of such primes such that a − b = 1 ?)
Most importantly is the case of two primes, where one can deduce that 2 b + 1 , 2 b 2 + 2 b + 1 must both be pirme. This, if I recall correctly, is at the difficulty of proving there exists an infinite number of primes of the form n 2 + 1 , an unsolved problem atm. But who knows I could be wrong and u seem to know more than me. (not sure if n 2 + 1 = 2 p is approachable tho.)
Log in to reply
@Xuming Liang – Great analysis. Your suggestion for zero primes can be used to create families of (infinite) solution sets. For one prime, Fermat's theorem on the sums of two squares is a good starting point. For many primes this only works with a and b differing by 1 , though, so it's not immediately obvious that there will be an infinite number of primes where a − b > 1 . This might be tractable though.
What probably isn't tractable is the two prime case, since as you point out, it would appear to depend on the Sierpinski/Schnizel Hypothesis H being true, and that proof remains elusive.
People don't seem to know the definition of "primitive" when applied to the phrase"pythagorean triad". Probably should include what it means in the question (but then again, some pretentious smug zombiehead will ignore that and write down the answer with incorrect reasoning as many others have already done so)
Log in to reply
The definition has been included in the problem.
Let me explicitly state that (6,8,10) is not a PPT.
Every primitive Pythagorean triplet can be generated by the following formulas
a
=
p
q
b
=
2
1
(
p
2
−
q
2
)
c
=
2
1
(
p
2
+
q
2
)
if p , q are odd numbers with no common factors. We can immediately see that if q > 1 and p , q differ by more than 2 , then it leaves c to be prime. If this were always true, then we've found a way to generate infinitely many prime numbers with a fairly simple algebraic method. So, it was a good guess to say the answer is "False", and that there will quickly be a counterexample found.
Moderator note:
Note: The other solutions below this do not correctly identify that a primitive pythagorean triplet has no common divisors. Thus, they are not correct solutions.
nice observation sir
I don't believe your formulas are correct. For instance, what are p and q for (4, 3, 5)? Regardless, a always has to be even, so p and q can't both be odd.
The basic observation stands, though.
Log in to reply
I don't see why a has to be even in this representation. With p = 3 , q = 1 , we have that a = 3 , b = 4 , c = 5 .
Log in to reply
Nevermind, I need to take another look at this but can't do so right now.
Log in to reply
@Paul Hartzer – Michael's formulae are from Euclid's Elements. A proof can be found here .
Log in to reply
@Brian Charlesworth – Oh, really? The Greeks thought of this first? Is there anything they haven't thought of first?
@Brian Charlesworth – Thanks. I knew all that, but was distracted this morning and probably shouldn't have been posting. Apologies to Michael.
Log in to reply
@Paul Hartzer – It's okay, Paul, otherwise we wouldn't be having this lively conversation about this somewhat alternative set of formulas for generating "only" primitive Pythagorean triplets. I think it's an interesting subject.
(4,3,5) is the same as (3,4,5), if we disregard ordering. So, for p =3, q = 1, we have (3,4,5).
I've come across these formulae before, and while I see that a 2 + b 2 = c 2 I can't form a proof as to why they generate all and only primitive triples. Do you know of a proof? Also, with p > q > 1 and p = q + 2 k for some k ≥ 1 we would have
b = 2 1 ( ( q + 2 k ) 2 − q 2 ) = 2 1 ( 4 q k + 4 k 2 ) = 2 k ( q + k ) ,
which is composite for any positive integer k . So I'm just wondering if the " p , q differ by more than 2 " condition is necessary. Regardless, the observation that this would have otherwise "established" a simple prime number generator is clever and amusing. :)
Log in to reply
The "differ by more than 2" condition is to force c be prime, if it's hypothesized that it is always prime. The only condition that the formula generate a primitive triplet is that p, q be odd numbers with no common factor.
Instinct just told me to click on "False" simply because I knew it implied an easy algebraic way to generate infinitely many primes. I didn't lose any time trying to think about this before deciding.
Log in to reply
O.k., got it; these are from Euclid's Elements.
It is false.Example is 24^{2}+10^{2}=26^{2}. None of the numbers are prime
(6,8,10), (60,80,100) ,etc
6 square + 8 square = 10 square....
gcd (6,8,10) = 2, not a primitive triple.
Counterexample: 6 , 8 , 10 - they're triplets, but none of them is a prime.
gcd (6,8,10) = 2, not a primitive triple.
Maybe the most famous example would be 10^2=8^2 + 6^2 (notice that this is the old 3,4,5 triplet just with the integers scaled by 2).
6,8,10 is simplest example.
let's take (3^2+4^2=5^2) multiplying each term by a^2, we see that 3a,4a,5a is a pythagorean triplet. a can be any natural no. Therefore not necessary any no. is prime. eg 6,8,10
False. If ( a , b , c ) is a primitive Pythagorean Triplet, then ( k a , k b , k c ) is also a Pythagorean Triplet with GCD k .
But then ( k a , k b , k c ) with k > 1 would not be a primitive triple.
False. A counter example is 1 6 2 + 6 3 2 = 6 5 2 , and none of these terms are prime.
If you got this problem wrong, practice here to get a perfect score on the SAT .