Problem 218 : Perfect right-angled triangles (55%)

Description

original

Consider the right angled triangle with sides a=7, b=24 and c=25. The area of this triangle is 84, which is divisible by the perfect numbers 6 and 28. Moreover it is a primitive right angled triangle as gcd(a,b)=1 and gcd(b,c)=1. Also c is a perfect square.

We will call a right angled triangle perfect if -it is a primitive right angled triangle -its hypotenuse is a perfect square

We will call a right angled triangle super-perfect if -it is a perfect right angled triangle and -its area is a multiple of the perfect numbers 6 and 28.

How many perfect right-angled triangles with c≤$10^{16}$ exist that are not super-perfect?

간략해석

직각삼각형 중에 세 변의 길이가 자연수이고, 각 수는 서로소인 세 수를 primitive right angled triangle 라고 한다.

직각삼각형 중 다음 조건을 만족하면 perfect 라고 하는데

primitive right angled triangle 이고
빗변의 길이가 제곱수여야한다.

또한 직각삼각형 중 세 다음 조건을 만족하면 super-perfect 라고 하는데

perfect 를 만족하고
면적이 완전수인 6과 28의 배수여야한다.

빗변의 길이가 $10^{12}$를 만족하는 perfect이고 super-perfect가 아닌 직각삼각형은 몇 개인가.

Idea & Algorithm

naive idea

모든 직각삼각형을 조사하는 방법이 있으나 범위를 봐서는 바로 무리임을 알 수 있다.

우선 다음 조건을 만족하는 직각삼각형이 얼마나 있는지 수식으로 확인을 해보자.

advanced idea

perfect 조건

우선 세 변의 길이를 $a, b, c$라 하고, 빗변을 $c$라고 하자. 그렇다면 $c = r^2$이어야

또한 직각 삼각형의 세변은 다음 성질을 가지는데, 성질은 well-known인데 링크를 참조하자. (Pythagorean_triple)

\[a = u^2 - v^2\] \[b = 2uv\] \[c = u^2 + v^2\]

그리고 $c = r^2$이고 그렇다면 ${u, v, r}$도 피타고라스 정리를 만족하는 쌍이며, 다음과 같이 서술할 수 있다.

\[u = m^2 - n^2\] \[v = 2mn\] \[r = m^2 + n^2\]

그럼 위에 식에 아래 식을 대입하면 $a$와 $b$를 $m$과 $n$에 관한 식으로 표현할 수 있다.

\[a = m^4 + n^4 - 6m^2n^2\] \[b = 4mn(m^2-n^2)\]

그렇다면 삼각형의 넓이는 $ab/2$이므로 다음과 같은 식이 나온다.

\[Area = 2mn(m^2-n^2)(m^4+n^4-6m^2n^2)\]

다음 면적은 perfect일때 면적이다. 그렇다면 이 조건에서 어떤 경우 super-perfect가 되는지 체크해보도록하자.

super-perfect 조건

2 없애기

6과 28의 배수이면 super-perfect고 $lcm(6,28)=84$이니 84의 배수가 되는지를 체크해보면 다음과 같다. 우선 인수인 2를 양변에 취해주면

\[42 | mn(m^2-n^2)(m^4+n^4-6m^2n^2)\]

여기서 $m \equiv 0 (mod2)$ 또는 $n \equiv 0 (mod2)$이면 $mn$에서 2의 배수이고, 이를 제외한 케이스는 $m \equiv n \equiv 1 (mod2)$인데 이때는 $m^2-n^2$에서 2의 배수가 된다. 그렇기에 다음 수식은 2의 배수이고 또 다시 인수를 제외하면

\[21 | mn(m^2-n^2)(m^4+n^4-6m^2n^2)\]

이 된다.

3 없애기

수식 중 일부인 $mn(m^2-n^2)$을 보자.

$m \equiv 0 (mod3)$ 또는 $n \equiv 0 (mod3)$이면 $mn$에서 3의 배수이고, 이를 제외한 케이스에서 $1^2 \equiv 2^2 \equiv 1 (mod3)$이므로 이 경우에는 $m^2-n^2$에서 3의 배수가 된다.

그렇기에 마지만 7의 배수만 체크하면 된다.

7 없애기

\[7 | mn(m^2-n^2)(m^4+n^4-6m^2n^2)\]

$mn$에서 각 수가 7의 배수인 경우는 제외하면 모든 식은 $m^2$, $n^2$으로 표현이 되는데, 7의 배수가 아닌 어떤 수 $k$에 대해서 $k^2 \equiv 1,2,4 (mod7)$이고 $m^2\equiv n^2$인 경우를 제외하고, 각 쌍은 대칭성을 가지니 각 제곱의 나머지 쌍은 $(1,2), (1,4), (2,4)$가 존재한다.

이 쌍들에 대해 $(m^4+n^4-6m^2n^2)$에 대입해보면 모든 쌍이 $mod7$에 대해 0이 나옴을 알 수 있다.

마무리

따라서 perfect이면 반드시 super-perfect이고, 따라서 조건을 만족하는 삼각형의 개수는 0이다.

source code

이 문제의 경우에는 소스코드는 없다.

Problem 218