Convert Equilateral triangle to Isosceles triangle

Let an equilateral triangle have the length of each side an integer $N$. I need to find if it is possible to transform the triangle keeping two sides fixed and alter the third side such that it still remains a triangle, but the altered side will have its length as an even integer, and the line drawn from the opposite vertex to the mid-point of the altered side is of integral length, i.e. it becomes an isosceles triangle.

Example : If $N=5$ then the answer is YES while if $N=3$ answer is NO.

It's a computer graphics problem that is a sub-part of bigger problem, I have been racking brains about maths and the concept behind it, to solve my problem.

• Suppose that $a$ is half the altered side, and $b$ is the distance from the vertex to the midpoint of the altered side. By the Pythagorean Theorem we want $a^2+b^2=N^2$. This has a non-trivial solution precisely if $N$ is divisible by a prime of the form $4k+1$. (I am making this a comment since I think I have seen this question on MSE recently.) – André Nicolas Oct 3 '15 at 16:17
• @AndréNicolas: Programatically how to check it? Any logic? – cold_coder Oct 3 '15 at 18:40
• I don't know what you mean by programmatically. With a program? We can find the prime factorization of $N$, and see whether among the prime factors there is a prime of the shape $4k+1$. But factoring huge numbers appears to be computationally difficult. – André Nicolas Oct 3 '15 at 20:56

To restate your question more clearly, you are asking what kind of integer number $N$ can be the hypothenuse of a right-angled triangle, so that the other two sides are of integer length too.

The answer is well known: $N$ must be (the multiple of) the sum of two perfect squares: $N=a^2+b^2$ (or $N=k(a^2+b^2)$). If so, the other two sides (which in your problem are half the modified side and "the line drawn from the opposite vertex to the mid-point of the altered side") are given by $a^2-b^2$ and $2ab$ (multiplied by $k$ if needed).

Example: $5=2^2+1^2$, $3=2^2-1^2$, $4=2\cdot(2\cdot1)$.

• Then how to check that it is multiple of square of two numbers or not? – cold_coder Oct 3 '15 at 18:39
• But how to calculate a and b, as stated in your answer.... ??? – Lauren Oct 3 '15 at 19:53
• @cold_coder André Nicolas gave the answer in his comment: you must check that all prime factors of $N$ be of the form $4k+1$. – Aretino Oct 3 '15 at 20:01
• Ok got it! Thank you! – cold_coder Oct 3 '15 at 20:03
• @cold_coder I forgot to mention that is is valid for primitive triples: in general $N$ can be a product of prime factors of the form $4k+1$ times any positive integer number. In practice, only those numbers which don't have any prime factor of the form $4k+1$ must be discarded. – Aretino Oct 3 '15 at 20:09

This is a question from CodeChef October Challange. Please dude dont lie