A primitive right-angled triangle has integer sides \((a,b,c)\), satisfies \(a^2+b^2=c^2\), and has \(\gcd(a,b,c)=1\). In this problem such a triangle is called perfect when the hypotenuse \(c\) is itself a perfect square, and super-perfect when its area is divisible by \(84\).
The task is to count perfect primitive right triangles under the problem's bound \(c \le 10^{16}\) whose area is not divisible by \(84\). The striking point is that the final answer does not come from a large search at all: the mathematics shows that every perfect primitive right triangle is automatically super-perfect, so the required count is zero.
The whole solution is a short chain of structural facts about primitive Pythagorean triples. The key move is that a square hypotenuse creates a second primitive triple hidden inside the first one.
Every primitive right triangle can be written in Euclid's form
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
with integers \(m>n>0\), \(\gcd(m,n)=1\), and opposite parity. Those conditions are exactly what make the triple primitive.
For Problem 218 we additionally require \(c\) to be a square, so there is an integer \(r\) such that
$$m^2+n^2=r^2.$$
That means \((m,n,r)\) is itself a primitive Pythagorean triple: \(m\) and \(n\) are coprime and of opposite parity already, so no common factor can appear in the new triple either.
Since \((m,n,r)\) is primitive, its two legs must again have Euclidean form. Reordering the two legs of this auxiliary triple if necessary, there exist coprime integers \(u>v>0\) of opposite parity such that
$$\{m,n\}=\{u^2-v^2,\ 2uv\},\qquad r=u^2+v^2.$$
This is the main structural fact behind the theorem. A perfect triangle is not an arbitrary primitive triple with a square hypotenuse; it is a primitive triple whose Euclid parameters are themselves the two legs of another primitive triple.
The area of the original triangle is
$$A=\frac{ab}{2}=mn(m^2-n^2).$$
Because the auxiliary parameterization may swap the roles of \(m\) and \(n\), it is cleaner to write
$$A=mn\,|m^2-n^2|.$$
Now substitute \(\{m,n\}=\{u^2-v^2,\ 2uv\}\):
$$A=2uv(u^2-v^2)\left|(u^2-v^2)^2-(2uv)^2\right|.$$
Expanding the last factor gives
$$A=2uv(u^2-v^2)\left|u^4-6u^2v^2+v^4\right|.$$
For divisibility arguments the sign is irrelevant, so the whole problem is reduced to proving that the product above is always divisible by \(4\), by \(3\), and by \(7\).
Factor \(4\). Because \(u\) and \(v\) have opposite parity, exactly one of them is even, so \(uv\) is even. The factor \(2uv\) therefore contributes at least two powers of 2, which proves \(4 \mid A\).
Factor \(3\). If \(3\mid u\) or \(3\mid v\), then \(3\mid A\) immediately. Otherwise \(u\not\equiv 0\) and \(v\not\equiv 0\pmod 3\), so
$$u^2\equiv v^2\equiv 1 \pmod 3,$$
and therefore
$$u^2-v^2\equiv 0 \pmod 3.$$
In either case, \(3\mid uv(u^2-v^2)\), hence \(3\mid A\).
Factor \(7\). If \(7\mid u\) or \(7\mid v\), there is nothing to prove. Otherwise Fermat's little theorem gives
$$u^6\equiv v^6\equiv 1 \pmod 7.$$
Modulo \(7\), the quartic factor simplifies because \(-6\equiv 1\):
$$u^4-6u^2v^2+v^4\equiv u^4+u^2v^2+v^4 \pmod 7.$$
Now use the identity
$$(u^2-v^2)(u^4+u^2v^2+v^4)=u^6-v^6.$$
The right-hand side is \(0 \pmod 7\), so
$$7\mid (u^2-v^2)(u^4-6u^2v^2+v^4).$$
Thus \(7\mid A\) as well.
Combining the three parts yields
$$4\mid A,\qquad 3\mid A,\qquad 7\mid A,$$
hence
$$84=4\cdot 3\cdot 7 \mid A.$$
So every perfect primitive right triangle is automatically super-perfect. There are no counterexamples to count.
The smallest familiar example already illustrates the theorem. Taking Euclid parameters \(m=4\) and \(n=3\) gives
$$a=4^2-3^2=7,\qquad b=2\cdot 4\cdot 3=24,\qquad c=4^2+3^2=25=5^2.$$
So \((7,24,25)\) is perfect. The hidden auxiliary triple is \((3,4,5)\), which corresponds to \(u=2\), \(v=1\). The factorized area formula becomes
$$A=2\cdot 2\cdot 1\cdot (2^2-1^2)\cdot \left|2^4-6\cdot 2^2\cdot 1^2+1^4\right|=4\cdot 3\cdot 7=84.$$
The first perfect primitive triangle is already super-perfect, and the proof above shows that this is not a coincidence but a universal fact.
The implementation uses the theorem in its strongest possible form. Once the mathematics proves that every perfect primitive right triangle is super-perfect, the count of non-super-perfect triangles below any bound is identically zero. The final solver therefore returns \(0\) directly instead of trying to enumerate triangles up to \(10^{16}\).
The C++, Python, and Java implementations all embody that same conclusion. The Python version is the distilled theorem-only form. The C++ and Java versions additionally keep a bounded brute-force checkpoint: they loop over Euclid parameters, enforce coprimality and opposite parity, test whether \(m^2+n^2\) is a square, compute the corresponding area, and verify on a small range that no counterexample with area not divisible by \(84\) appears.
That checkpoint is a sanity test, not the real method. The real method is the proof above, which collapses the search space completely.
For the actual solution, the time complexity is \(O(1)\) and the memory usage is \(O(1)\): the program returns the theorem's conclusion immediately.
The auxiliary checkpoint enumeration used for validation on small ranges is much slower, roughly quadratic in the chosen Euclid-parameter cutoff, but it is intentionally kept far below the true problem bound. It does not change the complexity of the final solver, whose whole point is to avoid any large-scale search.
Ein primitives rechtwinkliges Dreieck besitzt ganzzahlige Seiten \((a,b,c)\), erfüllt \(a^2+b^2=c^2\) und hat \(\gcd(a,b,c)=1\). In dieser Aufgabe heißt ein solches Dreieck perfekt, wenn die Hypotenuse \(c\) selbst ein Quadrat ist, und super-perfekt, wenn seine Fläche durch \(84\) teilbar ist.
Gesucht ist die Anzahl perfekter primitiver rechtwinkliger Dreiecke unter der Schranke \(c \le 10^{16}\), deren Fläche nicht durch \(84\) teilbar ist. Der entscheidende Punkt ist: Die Antwort entsteht nicht durch eine große Suche. Die Zahl ist null, weil sich beweisen lässt, dass jedes perfekte primitive rechtwinklige Dreieck automatisch super-perfekt ist.
Die gesamte Lösung besteht aus einer Kette klassischer Eigenschaften primitiver pythagoreischer Tripel. Die Bedingung „quadratische Hypotenuse“ zwingt eine zweite Pythagoras-Struktur in die Parameter der ersten.
Jedes primitive rechtwinklige Dreieck lässt sich in Euclid-Form schreiben als
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
wobei \(m>n>0\), \(\gcd(m,n)=1\) und \(m,n\) verschiedene Parität haben. Genau diese Bedingungen sichern die Primitivität.
Für Problem 218 kommt nun die Zusatzbedingung hinzu, dass \(c\) ein Quadrat ist. Es gibt also ein \(r\) mit
$$m^2+n^2=r^2.$$
Damit ist \((m,n,r)\) selbst wieder ein primitives pythagoreisches Tripel: \(m\) und \(n\) sind schon teilerfremd und von entgegengesetzter Parität.
Weil \((m,n,r)\) primitiv ist, müssen seine beiden Katheten erneut Euclid-Form besitzen. Nach eventuell vertauschter Reihenfolge der beiden Katheten gibt es also teilerfremde Zahlen \(u>v>0\) verschiedener Parität mit
$$\{m,n\}=\{u^2-v^2,\ 2uv\},\qquad r=u^2+v^2.$$
Das ist die zentrale Struktur der Aufgabe. Ein perfektes Dreieck ist also nicht nur ein primitives pythagoreisches Tripel mit quadratischer Hypotenuse; seine Euclid-Parameter sind selbst die beiden Katheten eines weiteren primitiven Tripels.
Die Fläche des ursprünglichen Dreiecks ist
$$A=\frac{ab}{2}=mn(m^2-n^2).$$
Da die Hilfsparametrisierung die Rollen von \(m\) und \(n\) vertauschen kann, ist die symmetrische Schreibweise
$$A=mn\,|m^2-n^2|$$
am saubersten. Setzt man \(\{m,n\}=\{u^2-v^2,\ 2uv\}\) ein, erhält man
$$A=2uv(u^2-v^2)\left|(u^2-v^2)^2-(2uv)^2\right|,$$
also nach Ausmultiplizieren
$$A=2uv(u^2-v^2)\left|u^4-6u^2v^2+v^4\right|.$$
Für Teilbarkeitsaussagen spielt das Vorzeichen keine Rolle. Es genügt also zu zeigen, dass dieses Produkt immer durch \(4\), durch \(3\) und durch \(7\) teilbar ist.
Faktor \(4\). Da \(u\) und \(v\) entgegengesetzte Parität haben, ist genau eine der beiden Zahlen gerade. Also ist \(uv\) gerade, und der Faktor \(2uv\) ist bereits durch \(4\) teilbar. Damit gilt \(4\mid A\).
Faktor \(3\). Falls \(3\mid u\) oder \(3\mid v\), ist die Sache sofort erledigt. Andernfalls sind beide Zahlen modulo \(3\) von null verschieden, also
$$u^2\equiv v^2\equiv 1 \pmod 3,$$
und damit
$$u^2-v^2\equiv 0 \pmod 3.$$
Somit teilt \(3\) stets das Produkt \(uv(u^2-v^2)\), also auch \(A\).
Faktor \(7\). Falls \(7\mid u\) oder \(7\mid v\), ist wieder nichts weiter zu zeigen. Sonst liefert der kleine Satz von Fermat
$$u^6\equiv v^6\equiv 1 \pmod 7.$$
Modulo \(7\) gilt außerdem \(-6\equiv 1\), also
$$u^4-6u^2v^2+v^4\equiv u^4+u^2v^2+v^4 \pmod 7.$$
Nun verwendet man die Identität
$$(u^2-v^2)(u^4+u^2v^2+v^4)=u^6-v^6.$$
Die rechte Seite ist \(0 \pmod 7\), daher gilt
$$7\mid (u^2-v^2)(u^4-6u^2v^2+v^4).$$
Also teilt \(7\) ebenfalls die Fläche \(A\).
Zusammen ergibt das
$$4\mid A,\qquad 3\mid A,\qquad 7\mid A,$$
und damit
$$84=4\cdot 3\cdot 7 \mid A.$$
Jedes perfekte primitive rechtwinklige Dreieck ist also automatisch super-perfekt. Es gibt keine Gegenbeispiele zu zählen.
Schon das kleinste bekannte Beispiel zeigt den Mechanismus. Für \(m=4\) und \(n=3\) erhält man
$$a=4^2-3^2=7,\qquad b=2\cdot 4\cdot 3=24,\qquad c=4^2+3^2=25=5^2.$$
Also ist \((7,24,25)\) perfekt. Das verborgene Hilfstripel ist \((3,4,5)\), also \(u=2\) und \(v=1\). Die faktorisierte Flächenformel liefert
$$A=2\cdot 2\cdot 1\cdot (2^2-1^2)\cdot \left|2^4-6\cdot 2^2\cdot 1^2+1^4\right|=4\cdot 3\cdot 7=84.$$
Bereits das erste perfekte primitive Dreieck ist also super-perfekt, und der Beweis zeigt, dass dies ausnahmslos immer so ist.
Die Implementierung verwendet das Theorem in seiner stärksten Form. Sobald gezeigt ist, dass jedes perfekte primitive rechtwinklige Dreieck super-perfekt ist, ist die Anzahl der nicht super-perfekten Dreiecke unter jeder Schranke identisch null. Der eigentliche Solver gibt daher direkt \(0\) zurück, anstatt Dreiecke bis \(10^{16}\) zu enumerieren.
Die Implementierungen in C++, Python und Java bilden genau diese Aussage ab. Die Python-Version ist die reinste Form des Theorems und gibt unmittelbar \(0\) aus. Die C++- und Java-Versionen enthalten zusätzlich einen kleinen Brute-Force-Kontrolllauf: Sie iterieren über Euclid-Parameter, prüfen Teilerfremdheit und Parität, testen, ob \(m^2+n^2\) ein Quadrat ist, berechnen die Fläche und bestätigen auf kleinem Bereich, dass kein Gegenbeispiel mit \(84\nmid A\) auftaucht.
Dieser Kontrolllauf ist nur eine Plausibilitätsprüfung. Die eigentliche Methode ist der mathematische Beweis, der die gesamte Suche überflüssig macht.
Für die eigentliche Lösung sind Laufzeit und Speicherbedarf jeweils \(O(1)\): Das Programm gibt unmittelbar das theoretische Ergebnis zurück.
Die zusätzliche Test-Enumeration auf kleinen Bereichen ist deutlich teurer, ungefähr quadratisch in der gewählten Schranke für die Euclid-Parameter. Sie ist aber bewusst nur als Validierung gedacht und verändert die Komplexität des finalen Lösers nicht. Genau darin liegt der Nutzen des Beweises: Er vermeidet jede großskalige Suche.
İlkel bir dik üçgenin kenarları \((a,b,c)\) tam sayıdır, \(a^2+b^2=c^2\) koşulunu sağlar ve \(\gcd(a,b,c)=1\) olur. Bu problemde böyle bir üçgenin hipotenüsü \(c\) tam kare ise üçgen perfect, alanı \(84\)'e bölünüyorsa super-perfect olarak adlandırılır.
İstenen şey, \(c \le 10^{16}\) sınırı altında kalan perfect ilkel dik üçgenler arasında alanı \(84\)'e bölünmeyen kaç tane üçgen olduğunu bulmaktır. Çarpıcı nokta şudur: cevap büyük bir aramadan çıkmaz. Matematiksel ispat, her perfect ilkel dik üçgenin zaten super-perfect olduğunu gösterir; dolayısıyla aranan sayı sıfırdır.
Çözüm, ilkel Pisagor üçlülerinin klasik yapısal özelliklerinin kısa ama güçlü bir zincirinden oluşur. Kare hipotenüs koşulu, ilk parametrelemenin içinde ikinci bir Pisagor üçlüsü saklar.
Her ilkel dik üçgen Euclid formunda yazılabilir:
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
burada \(m>n>0\), \(\gcd(m,n)=1\) ve \(m\) ile \(n\) zıt parity'ye sahiptir. Üçgenin ilkel olmasını sağlayan koşullar tam olarak bunlardır.
Problem 218'de ek olarak \(c\)'nin tam kare olması istenir. Yani bir \(r\) tam sayısı için
$$m^2+n^2=r^2$$
olur. Böylece \((m,n,r)\) üçlüsü de ilkel bir Pisagor üçlüsüdür; çünkü \(m\) ile \(n\) zaten aralarında asal ve zıt parity'lidir.
\((m,n,r)\) ilkel olduğu için, bu yardımcı üçlünün iki dik kenarı da yine Euclid biçiminde yazılmalıdır. Gerekirse bu yardımcı üçlünün iki dik kenarını yer değiştirerek, aralarında asal ve zıt parity'li \(u>v>0\) tam sayıları için
$$\{m,n\}=\{u^2-v^2,\ 2uv\},\qquad r=u^2+v^2$$
yazabiliriz. Asıl yapısal gerçek budur: perfect bir üçgen, sadece kare hipotenüslü bir ilkel Pisagor üçlüsü değildir; aynı zamanda Euclid parametreleri başka bir ilkel Pisagor üçlüsünün dik kenarlarıdır.
İlk üçgenin alanı
$$A=\frac{ab}{2}=mn(m^2-n^2)$$
şeklindedir. Yardımcı parametreleme \(m\) ile \(n\)'nin rollerini değiştirebileceği için daha simetrik olan
$$A=mn\,|m^2-n^2|$$
yazımı daha güvenlidir. Şimdi \(\{m,n\}=\{u^2-v^2,\ 2uv\}\) yerleştirelim:
$$A=2uv(u^2-v^2)\left|(u^2-v^2)^2-(2uv)^2\right|.$$
Son çarpanı açarsak
$$A=2uv(u^2-v^2)\left|u^4-6u^2v^2+v^4\right|$$
elde edilir. Bölünebilirlik tartışmalarında işaret önemli olmadığı için, artık yapılması gereken şey bu ifadenin her zaman \(4\), \(3\) ve \(7\)'ye bölündüğünü göstermektir.
\(4\) çarpanı. \(u\) ile \(v\) zıt parity'li olduğundan bunlardan tam biri çifttir. O halde \(uv\) çifttir; dolayısıyla \(2uv\) en az iki tane 2 çarpanı içerir. Bu da \(4\mid A\) demektir.
\(3\) çarpanı. Eğer \(3\mid u\) veya \(3\mid v\) ise iş hemen biter. Aksi halde her ikisi de mod 3'te sıfırdan farklıdır, yani
$$u^2\equiv v^2\equiv 1 \pmod 3,$$
ve buradan
$$u^2-v^2\equiv 0 \pmod 3$$
çıkar. Böylece \(3\), her durumda \(uv(u^2-v^2)\) ifadesini; dolayısıyla alanı böler.
\(7\) çarpanı. Eğer \(7\mid u\) veya \(7\mid v\) ise yine doğrudan biter. Aksi halde Fermat'ın küçük teoreminden
$$u^6\equiv v^6\equiv 1 \pmod 7$$
elde edilir. Ayrıca mod 7'de \(-6\equiv 1\) olduğu için
$$u^4-6u^2v^2+v^4\equiv u^4+u^2v^2+v^4 \pmod 7.$$
Şimdi şu özdeşliği kullanalım:
$$(u^2-v^2)(u^4+u^2v^2+v^4)=u^6-v^6.$$
Sağ taraf mod 7'de sıfırdır. O halde
$$7\mid (u^2-v^2)(u^4-6u^2v^2+v^4)$$
olur ve sonuç olarak \(7\mid A\).
Üç parçayı birleştirince
$$4\mid A,\qquad 3\mid A,\qquad 7\mid A,$$
dolayısıyla
$$84=4\cdot 3\cdot 7 \mid A$$
elde edilir. Yani her perfect ilkel dik üçgen otomatik olarak super-perfect'tir. Sayılacak hiçbir karşı örnek yoktur.
En bilinen küçük örnek bile teoremi açıkça gösterir. \(m=4\) ve \(n=3\) alırsak
$$a=4^2-3^2=7,\qquad b=2\cdot 4\cdot 3=24,\qquad c=4^2+3^2=25=5^2$$
olur. Demek ki \((7,24,25)\) perfect bir üçgendir. Bunun içindeki gizli yardımcı üçlü \((3,4,5)\) olduğundan \(u=2\), \(v=1\) seçilebilir. Alanın çarpanlı biçimi
$$A=2\cdot 2\cdot 1\cdot (2^2-1^2)\cdot \left|2^4-6\cdot 2^2\cdot 1^2+1^4\right|=4\cdot 3\cdot 7=84$$
verir. İlk perfect ilkel üçgen bile super-perfect'tir; yukarıdaki ispat bunun tekil bir tesadüf değil, genel bir zorunluluk olduğunu gösterir.
Uygulama, teoremi mümkün olan en güçlü biçimde kullanır. Her perfect ilkel dik üçgenin super-perfect olduğu ispatlandıktan sonra, herhangi bir sınır altında super-perfect olmayan perfect üçgen sayısı özdeş olarak sıfırdır. Bu yüzden asıl çözücü, \(10^{16}\)'ya kadar arama yapmak yerine doğrudan \(0\) döndürür.
C++, Python ve Java uygulamalarının ortak fikri budur. Python sürümü teoremin damıtılmış hâlidir ve doğrudan \(0\) üretir. C++ ve Java sürümleri ise buna ek olarak küçük bir brute-force kontrolü tutar: Euclid parametreleri üzerinde döner, aralarında asallık ve parity koşullarını kontrol eder, \(m^2+n^2\)'nin kare olup olmadığını test eder, alanı hesaplar ve küçük bir aralıkta \(84\)'e bölünmeyen hiçbir karşı örnek çıkmadığını doğrular.
Bu kontrol yalnızca mantık testi içindir. Gerçek yöntem arama yapmak değil, yukarıdaki ispatı kullanarak aramayı tamamen ortadan kaldırmaktır.
Nihai çözüm için zaman karmaşıklığı \(O(1)\), bellek kullanımı da \(O(1)\)'dir; program teoremin sonucunu doğrudan verir.
Küçük aralık doğrulaması için kullanılan yardımcı brute-force taraması ise seçilen Euclid-parametre sınırına göre yaklaşık karesel maliyete sahiptir. Ancak bu kısım bilinçli olarak gerçek problem sınırının çok altında tutulur ve nihai çözücünün karmaşıklığını değiştirmez. İspatın değeri tam da burada yatar: büyük bir taramayı gereksiz kılar.
Un triángulo rectángulo primitivo tiene lados enteros \((a,b,c)\), satisface \(a^2+b^2=c^2\) y cumple \(\gcd(a,b,c)=1\). En este problema se llama perfecto cuando la hipotenusa \(c\) es además un cuadrado perfecto, y super-perfecto cuando su área es divisible por \(84\).
La tarea consiste en contar los triángulos rectángulos primitivos perfectos con \(c \le 10^{16}\) cuya área no sea divisible por \(84\). Lo sorprendente es que la respuesta no requiere una búsqueda masiva: la demostración muestra que todo triángulo perfecto primitivo es automáticamente super-perfecto, así que el conteo pedido es cero.
La solución se apoya en una cadena breve de hechos estructurales sobre ternas pitagóricas primitivas. La condición de que la hipotenusa sea cuadrada obliga a que aparezca una segunda terna pitagórica dentro de los parámetros de la primera.
Todo triángulo rectángulo primitivo puede escribirse en la forma de Euclides
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
con \(m>n>0\), \(\gcd(m,n)=1\) y paridades opuestas. Esas son precisamente las condiciones que garantizan que la terna sea primitiva.
En el Problema 218 además pedimos que \(c\) sea un cuadrado, así que existe un entero \(r\) tal que
$$m^2+n^2=r^2.$$
Por tanto \((m,n,r)\) es a su vez una terna pitagórica primitiva: \(m\) y \(n\) ya eran coprimos y de paridad opuesta.
Como \((m,n,r)\) es primitiva, sus dos catetos vuelven a tener forma euclidiana. Reordenando esos dos catetos auxiliares si hace falta, existen enteros coprimos \(u>v>0\) de paridad opuesta tales que
$$\{m,n\}=\{u^2-v^2,\ 2uv\},\qquad r=u^2+v^2.$$
Éste es el hecho estructural decisivo. Un triángulo perfecto no es simplemente una terna pitagórica primitiva cuya hipotenusa sea cuadrada; sus propios parámetros de Euclides son los dos catetos de otra terna pitagórica primitiva.
El área del triángulo original vale
$$A=\frac{ab}{2}=mn(m^2-n^2).$$
Como la parametrización auxiliar puede intercambiar los papeles de \(m\) y \(n\), conviene escribirla de forma simétrica:
$$A=mn\,|m^2-n^2|.$$
Sustituyendo \(\{m,n\}=\{u^2-v^2,\ 2uv\}\), obtenemos
$$A=2uv(u^2-v^2)\left|(u^2-v^2)^2-(2uv)^2\right|,$$
y al expandir el último factor,
$$A=2uv(u^2-v^2)\left|u^4-6u^2v^2+v^4\right|.$$
Como sólo nos interesa la divisibilidad, el signo es irrelevante. Todo queda reducido a demostrar que este producto siempre es divisible por \(4\), por \(3\) y por \(7\).
Factor \(4\). \(u\) y \(v\) tienen paridad opuesta, así que exactamente uno de ellos es par. Entonces \(uv\) es par, y el factor \(2uv\) aporta al menos dos potencias de 2. Por tanto \(4\mid A\).
Factor \(3\). Si \(3\mid u\) o \(3\mid v\), ya está. En caso contrario, ambos son no nulos módulo 3, luego
$$u^2\equiv v^2\equiv 1 \pmod 3,$$
y por ello
$$u^2-v^2\equiv 0 \pmod 3.$$
En cualquiera de los dos casos, \(3\mid uv(u^2-v^2)\), y en consecuencia \(3\mid A\).
Factor \(7\). Si \(7\mid u\) o \(7\mid v\), no hace falta más. Si no, el pequeño teorema de Fermat da
$$u^6\equiv v^6\equiv 1 \pmod 7.$$
Además, como \(-6\equiv 1 \pmod 7\), el factor cuártico satisface
$$u^4-6u^2v^2+v^4\equiv u^4+u^2v^2+v^4 \pmod 7.$$
Usamos ahora la identidad
$$(u^2-v^2)(u^4+u^2v^2+v^4)=u^6-v^6.$$
El lado derecho es \(0 \pmod 7\), así que
$$7\mid (u^2-v^2)(u^4-6u^2v^2+v^4).$$
Con ello también \(7\mid A\).
Uniendo las tres partes se obtiene
$$4\mid A,\qquad 3\mid A,\qquad 7\mid A,$$
y por tanto
$$84=4\cdot 3\cdot 7 \mid A.$$
Todo triángulo perfecto primitivo es, pues, super-perfecto. No hay ejemplos que contar.
El ejemplo más pequeño ya muestra el fenómeno. Con \(m=4\) y \(n=3\) se obtiene
$$a=4^2-3^2=7,\qquad b=2\cdot 4\cdot 3=24,\qquad c=4^2+3^2=25=5^2.$$
Así, \((7,24,25)\) es perfecto. La terna auxiliar escondida es \((3,4,5)\), que corresponde a \(u=2\), \(v=1\). La fórmula factorizada del área da
$$A=2\cdot 2\cdot 1\cdot (2^2-1^2)\cdot \left|2^4-6\cdot 2^2\cdot 1^2+1^4\right|=4\cdot 3\cdot 7=84.$$
El primer triángulo perfecto primitivo ya es super-perfecto, y la demostración anterior explica por qué eso ocurre siempre.
La implementación usa el teorema en su forma más fuerte. Una vez demostrado que todo triángulo rectángulo primitivo perfecto es super-perfecto, el número de triángulos perfectos no super-perfectos bajo cualquier cota es exactamente cero. Por eso el solucionador final devuelve \(0\) de manera directa en vez de intentar enumerar triángulos hasta \(10^{16}\).
Las implementaciones en C++, Python y Java expresan esa misma idea. La versión en Python es la forma mínima basada sólo en el teorema. Las versiones en C++ y Java conservan además una comprobación exhaustiva acotada: recorren parámetros de Euclides, exigen coprimalidad y paridad opuesta, prueban si \(m^2+n^2\) es cuadrado, calculan el área y verifican en un rango pequeño que no aparece ningún contraejemplo con \(84\nmid A\).
Esa comprobación es sólo un control de coherencia. El método real es la demostración matemática, que elimina por completo la necesidad de una búsqueda grande.
Para la solución auténtica, el tiempo es \(O(1)\) y la memoria también es \(O(1)\): el programa devuelve inmediatamente la conclusión del teorema.
La enumeración auxiliar de validación, usada sólo en rangos pequeños, es bastante más costosa y crece aproximadamente de forma cuadrática con el corte elegido para los parámetros de Euclides. Pero eso no cambia la complejidad del solucionador final. Precisamente ése es el valor del argumento matemático: evitar toda búsqueda de gran escala.
一个原始直角三角形具有整数边 \((a,b,c)\)，满足 \(a^2+b^2=c^2\)，并且 \(\gcd(a,b,c)=1\)。在本题里，如果斜边 \(c\) 本身还是完全平方数，这样的三角形就称为 perfect；如果它的面积能被 \(84\) 整除，就称为 super-perfect。
题目要求统计所有满足 \(c \le 10^{16}\) 的 perfect 原始直角三角形中，面积不能被 \(84\) 整除的个数。真正关键的地方在于：答案并不是通过大规模枚举得到的。数学上可以证明，任何 perfect 原始直角三角形都会自动满足 super-perfect 条件，因此所求个数恒为 0。
整个解法建立在原始勾股三元组的几个标准结构事实上。最关键的一步是：当斜边本身是平方数时，第一层参数中的两项又会组成第二个原始勾股三元组。
任意一个原始直角三角形都可以写成
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
其中 \(m>n>0\)、\(\gcd(m,n)=1\)，并且 \(m,n\) 一奇一偶。这正是 Euclid 参数化，也是三元组原始性的标准刻画。
现在题目额外要求 \(c\) 是完全平方数，因此存在整数 \(r\) 使得
$$m^2+n^2=r^2.$$
于是 \((m,n,r)\) 本身又是一个原始勾股三元组：因为 \(m,n\) 已经互素且奇偶性相反，所以这里不会引入额外公因子。
既然 \((m,n,r)\) 也是原始勾股三元组，它的两条直角边就必须再次来自 Euclid 公式。必要时交换这两个辅助直角边的顺序，就存在互素、奇偶性相反且满足 \(u>v>0\) 的整数 \(u,v\)，使得
$$\{m,n\}=\{u^2-v^2,\ 2uv\},\qquad r=u^2+v^2.$$
这一步是整道题的核心结构。也就是说，perfect 三角形并不只是“斜边恰好是平方数”的原始勾股三元组；它的 Euclid 参数本身，正好又是另一个原始勾股三元组的两条直角边。
原三角形的面积为
$$A=\frac{ab}{2}=mn(m^2-n^2).$$
由于辅助参数化里 \(m\) 和 \(n\) 的角色可能交换，更稳妥的写法是
$$A=mn\,|m^2-n^2|.$$
把 \(\{m,n\}=\{u^2-v^2,\ 2uv\}\) 代入，得到
$$A=2uv(u^2-v^2)\left|(u^2-v^2)^2-(2uv)^2\right|.$$
将最后一个因子展开后变成
$$A=2uv(u^2-v^2)\left|u^4-6u^2v^2+v^4\right|.$$
接下来只需证明这个乘积一定同时被 \(4\)、\(3\)、\(7\) 整除。由于这里只关心整除性，绝对值中的正负号不会影响结论。
\(4\) 的因子。 因为 \(u\) 与 \(v\) 一奇一偶，所以二者中恰有一个是偶数，从而 \(uv\) 是偶数。这样 \(2uv\) 至少包含两个 2 的因子，因此 \(4\mid A\)。
\(3\) 的因子。 如果 \(3\mid u\) 或 \(3\mid v\)，那么 \(3\mid A\) 立即成立。否则 \(u,v\) 在模 3 意义下都不是 0，于是
$$u^2\equiv v^2\equiv 1 \pmod 3,$$
所以
$$u^2-v^2\equiv 0 \pmod 3.$$
无论哪一种情况，\(3\) 都整除 \(uv(u^2-v^2)\)，因此也整除面积 \(A\)。
\(7\) 的因子。 如果 \(7\mid u\) 或 \(7\mid v\)，同样直接成立。否则由费马小定理可得
$$u^6\equiv v^6\equiv 1 \pmod 7.$$
另一方面，在模 7 下有 \(-6\equiv 1\)，所以四次因子满足
$$u^4-6u^2v^2+v^4\equiv u^4+u^2v^2+v^4 \pmod 7.$$
现在利用恒等式
$$(u^2-v^2)(u^4+u^2v^2+v^4)=u^6-v^6.$$
右边在模 7 下等于 0，因此
$$7\mid (u^2-v^2)(u^4-6u^2v^2+v^4).$$
于是 \(7\mid A\) 也成立。
把三部分合起来，得到
$$4\mid A,\qquad 3\mid A,\qquad 7\mid A,$$
也就是
$$84=4\cdot 3\cdot 7 \mid A.$$
因此每一个 perfect 原始直角三角形都会自动成为 super-perfect。题目要求统计的反例根本不存在。
最经典的最小例子已经能把整个机制说明白。取 \(m=4\)、\(n=3\)，则
$$a=4^2-3^2=7,\qquad b=2\cdot 4\cdot 3=24,\qquad c=4^2+3^2=25=5^2.$$
因此 \((7,24,25)\) 是一个 perfect 三角形。它内部隐藏的辅助三元组是 \((3,4,5)\)，对应 \(u=2\)、\(v=1\)。代入面积分解式可得
$$A=2\cdot 2\cdot 1\cdot (2^2-1^2)\cdot \left|2^4-6\cdot 2^2\cdot 1^2+1^4\right|=4\cdot 3\cdot 7=84.$$
也就是说，第一个 perfect 原始直角三角形本身就已经是 super-perfect，而前面的证明说明这并不是巧合，而是普遍规律。
实现采用了这个定理的最强形式。一旦证明“所有 perfect 原始直角三角形都必然 super-perfect”，那么无论上界是多少，non-super-perfect 的数量都恒等于 0。因此最终求解程序根本不需要枚举到 \(10^{16}\)，而是直接返回 \(0\)。
C++、Python 和 Java 三个实现都体现了同样的结论。Python 版本是最精炼的定理版，直接输出 0。C++ 和 Java 版本额外保留了一个受限范围内的暴力校验：它们遍历 Euclid 参数，检查互素与奇偶条件，测试 \(m^2+n^2\) 是否为平方数，计算相应面积，并在小范围内确认不存在任何面积不被 \(84\) 整除的反例。
这个暴力部分只是验证思路正确性的辅助检查，不是正式算法。真正的算法就是上面的数学证明，它把原本看似庞大的搜索空间完全压缩掉了。
对最终解法而言，时间复杂度是 \(O(1)\)，空间复杂度也是 \(O(1)\)：程序直接输出定理结论。
用于小范围验证的辅助枚举明显更慢，大致会随所选 Euclid 参数截断呈二次增长。但它只服务于局部 sanity check，不影响最终求解器的渐近复杂度。证明的价值就在于彻底避免对真实问题范围做大规模遍历。
Примитивный прямоугольный треугольник имеет целочисленные стороны \((a,b,c)\), удовлетворяет равенству \(a^2+b^2=c^2\) и условию \(\gcd(a,b,c)=1\). В этой задаче такой треугольник называется perfect, если гипотенуза \(c\) сама является полным квадратом, и super-perfect, если его площадь делится на \(84\).
Нужно посчитать, сколько perfect примитивных прямоугольных треугольников при \(c \le 10^{16}\) имеют площадь, не делящуюся на \(84\). Главный вывод состоит в том, что никакого большого перебора не требуется: математика показывает, что любой perfect примитивный прямоугольный треугольник автоматически является super-perfect, поэтому искомое количество равно нулю.
Решение опирается на несколько стандартных структурных фактов о примитивных пифагоровых тройках. Условие квадрата на гипотенузе заставляет параметры первой тройки образовать вторую примитивную тройку.
Любой примитивный прямоугольный треугольник можно записать в форме Евклида:
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
где \(m>n>0\), \(\gcd(m,n)=1\), а \(m\) и \(n\) имеют разную четность. Именно эти условия обеспечивают примитивность.
В задаче 218 дополнительно требуется, чтобы \(c\) было квадратом, то есть существовало целое число \(r\) такое, что
$$m^2+n^2=r^2.$$
Следовательно, \((m,n,r)\) тоже является примитивной пифагоровой тройкой: числа \(m\) и \(n\) уже взаимно просты и имеют разную четность.
Раз тройка \((m,n,r)\) примитивна, ее катеты снова должны иметь евклидов вид. При необходимости меняя местами эти два вспомогательных катета, получаем взаимно простые числа \(u>v>0\) разной четности, для которых
$$\{m,n\}=\{u^2-v^2,\ 2uv\},\qquad r=u^2+v^2.$$
Это и есть ключевая структура задачи. Perfect-треугольник не просто имеет квадратную гипотенузу; его евклидовы параметры сами являются двумя катетами другой примитивной пифагоровой тройки.
Площадь исходного треугольника равна
$$A=\frac{ab}{2}=mn(m^2-n^2).$$
Поскольку во вспомогательной параметризации роли \(m\) и \(n\) могут поменяться местами, удобнее записать симметрично:
$$A=mn\,|m^2-n^2|.$$
Подставляя \(\{m,n\}=\{u^2-v^2,\ 2uv\}\), получаем
$$A=2uv(u^2-v^2)\left|(u^2-v^2)^2-(2uv)^2\right|,$$
а после раскрытия скобок
$$A=2uv(u^2-v^2)\left|u^4-6u^2v^2+v^4\right|.$$
Для вопросов делимости знак не играет роли, поэтому теперь достаточно доказать, что это произведение всегда делится на \(4\), на \(3\) и на \(7\).
Множитель \(4\). Числа \(u\) и \(v\) имеют разную четность, значит ровно одно из них четно. Тогда \(uv\) четно, а множитель \(2uv\) уже содержит по меньшей мере две двойки. Следовательно, \(4\mid A\).
Множитель \(3\). Если \(3\mid u\) или \(3\mid v\), то всё доказано сразу. Иначе оба числа ненулевые по модулю \(3\), а потому
$$u^2\equiv v^2\equiv 1 \pmod 3,$$
откуда
$$u^2-v^2\equiv 0 \pmod 3.$$
Значит, в любом случае \(3\mid uv(u^2-v^2)\), и тем самым \(3\mid A\).
Множитель \(7\). Если \(7\mid u\) или \(7\mid v\), дополнительной работы не требуется. Иначе по малой теореме Ферма
$$u^6\equiv v^6\equiv 1 \pmod 7.$$
Кроме того, по модулю \(7\) имеем \(-6\equiv 1\), поэтому
$$u^4-6u^2v^2+v^4\equiv u^4+u^2v^2+v^4 \pmod 7.$$
Теперь используется тождество
$$(u^2-v^2)(u^4+u^2v^2+v^4)=u^6-v^6.$$
Правая часть равна \(0 \pmod 7\), следовательно,
$$7\mid (u^2-v^2)(u^4-6u^2v^2+v^4).$$
Значит, и \(7\mid A\).
Объединяя три результата, получаем
$$4\mid A,\qquad 3\mid A,\qquad 7\mid A,$$
то есть
$$84=4\cdot 3\cdot 7 \mid A.$$
Таким образом, любой perfect примитивный прямоугольный треугольник автоматически является super-perfect. Считать просто нечего.
Даже самый маленький известный пример полностью отражает доказательство. При \(m=4\) и \(n=3\) имеем
$$a=4^2-3^2=7,\qquad b=2\cdot 4\cdot 3=24,\qquad c=4^2+3^2=25=5^2.$$
Значит, \((7,24,25)\) является perfect-треугольником. Внутри него скрыта вспомогательная тройка \((3,4,5)\), то есть можно взять \(u=2\), \(v=1\). Факторизованная формула площади дает
$$A=2\cdot 2\cdot 1\cdot (2^2-1^2)\cdot \left|2^4-6\cdot 2^2\cdot 1^2+1^4\right|=4\cdot 3\cdot 7=84.$$
Первый perfect примитивный треугольник уже оказывается super-perfect, а общий аргумент объясняет, почему это неизбежно всегда.
Реализация использует теорему в максимально прямой форме. После доказательства того, что любой perfect примитивный прямоугольный треугольник обязан быть super-perfect, число non-super-perfect треугольников под любой границей становится тождественно равным нулю. Поэтому итоговый решатель просто возвращает \(0\), не пытаясь перечислять треугольники до \(10^{16}\).
Именно так устроены реализации на C++, Python и Java. Версия на Python представляет собой чистую теорему без дополнительных деталей. Версии на C++ и Java дополнительно сохраняют небольшой контрольный перебор: они проходят по параметрам Евклида, проверяют взаимную простоту и разную четность, тестируют, является ли \(m^2+n^2\) квадратом, вычисляют площадь и убеждаются на малом диапазоне, что примеров с \(84\nmid A\) не возникает.
Этот контрольный перебор служит лишь проверкой здравого смысла. Настоящий метод решения - это доказательство выше, полностью устраняющее необходимость большого поиска.
Для окончательного решения время работы равно \(O(1)\), а потребление памяти тоже равно \(O(1)\): программа немедленно выводит следствие теоремы.
Вспомогательный перебор для проверки на малых диапазонах заметно дороже и растет примерно квадратично по выбранному пределу для параметров Евклида. Но он не влияет на асимптотику конечного решателя. Смысл доказательства как раз в том, чтобы полностью избежать масштабного перебора.
المثلث القائم البدائي له أضلاع صحيحة \((a,b,c)\)، ويحقق \(a^2+b^2=c^2\)، كما أن \(\gcd(a,b,c)=1\). في هذه المسألة يسمى المثلث perfect إذا كان الوتر \(c\) مربعًا كاملًا، ويسمى super-perfect إذا كانت مساحته قابلة للقسمة على \(84\).
المطلوب هو عدّ المثلثات القائمة البدائية perfect التي تحقق \(c \le 10^{16}\) وتكون مساحتها غير قابلة للقسمة على \(84\). الفكرة الحاسمة هي أن الجواب لا يحتاج إلى تعداد ضخم أصلًا؛ فالبرهان يثبت أن كل مثلث perfect بدائي هو بالضرورة super-perfect، ولذلك يكون العدد المطلوب مساويًا للصفر.
الحل كله يعتمد على سلسلة قصيرة من الحقائق البنيوية المعروفة عن ثلاثيات فيثاغورس البدائية. الشرط الإضافي بأن يكون الوتر مربعًا كاملًا يخلق ثلاثية فيثاغورس ثانية مختبئة داخل معاملات الثلاثية الأولى.
يمكن كتابة أي مثلث قائم بدائي على الصورة
$$a=m^2-n^2,\qquad b=2mn,\qquad c=m^2+n^2,$$
حيث \(m>n>0\)، و\(\gcd(m,n)=1\)، و\(m,n\) مختلفا الزوجية. هذه هي بالضبط شروط بدائية الثلاثية.
في المسألة الحالية نطلب فوق ذلك أن يكون \(c\) مربعًا كاملًا، أي توجد قيمة صحيحة \(r\) تحقق
$$m^2+n^2=r^2.$$
وهذا يعني أن \((m,n,r)\) نفسها ثلاثية فيثاغورس بدائية، لأن \(m\) و\(n\) متباينان أوليًا ومختلفا الزوجية أصلًا.
بما أن \((m,n,r)\) ثلاثية بدائية، فلا بد أن يكون ضلعاها القائمان من الشكل الإقليدي مرة أخرى. وبعد تبديل هذين الضلعين المساعدين عند الحاجة، توجد أعداد صحيحة \(u>v>0\) متباينة أوليًا ومختلفة الزوجية بحيث
$$\{m,n\}=\{u^2-v^2,\ 2uv\},\qquad r=u^2+v^2.$$
هذه هي البنية الأساسية في المسألة. فالمثلث perfect ليس مجرد ثلاثية بدائية ذات وتر مربع؛ بل إن معاملي إقليدس فيها هما نفسيهما الضلعين القائمين لثلاثية بدائية أخرى.
مساحة المثلث الأصلي تساوي
$$A=\frac{ab}{2}=mn(m^2-n^2).$$
ولأن التمثيل المساعد قد يبدّل دوري \(m\) و\(n\)، فمن الأنظف كتابتها بشكل متناظر:
$$A=mn\,|m^2-n^2|.$$
وبالتعويض \(\{m,n\}=\{u^2-v^2,\ 2uv\}\) نحصل على
$$A=2uv(u^2-v^2)\left|(u^2-v^2)^2-(2uv)^2\right|,$$
ثم بعد التوسيع يصبح
$$A=2uv(u^2-v^2)\left|u^4-6u^2v^2+v^4\right|.$$
وبما أننا نهتم فقط بالقابلية للقسمة، فالإشارة داخل القيمة المطلقة لا تؤثر. إذن يكفي إثبات أن هذا المقدار يقبل القسمة دائمًا على \(4\) وعلى \(3\) وعلى \(7\).
عامل \(4\). لأن \(u\) و\(v\) مختلفا الزوجية، فإن واحدًا منهما فقط زوجي، ومن ثم يكون \(uv\) عددًا زوجيًا. إذًا العامل \(2uv\) يحتوي على عاملين من 2 على الأقل، وهذا يعطي \(4\mid A\).
عامل \(3\). إذا كان \(3\mid u\) أو \(3\mid v\) فالأمر محسوم مباشرة. وإلا فإن كلاهما غير صفري modulo 3، وبالتالي
$$u^2\equiv v^2\equiv 1 \pmod 3,$$
ومن ثم
$$u^2-v^2\equiv 0 \pmod 3.$$
إذن في جميع الحالات يكون \(3\mid uv(u^2-v^2)\)، وبالتالي \(3\mid A\).
عامل \(7\). إذا كان \(7\mid u\) أو \(7\mid v\) فلا شيء إضافيًا لإثباته. وإذا لم يحدث ذلك، فإن مبرهنة فيرما الصغرى تعطي
$$u^6\equiv v^6\equiv 1 \pmod 7.$$
وكذلك لأن \(-6\equiv 1 \pmod 7\) فإن العامل من الدرجة الرابعة يحقق
$$u^4-6u^2v^2+v^4\equiv u^4+u^2v^2+v^4 \pmod 7.$$
والآن نستخدم المتطابقة
$$(u^2-v^2)(u^4+u^2v^2+v^4)=u^6-v^6.$$
الطرف الأيمن يساوي \(0 \pmod 7\)، ولذلك
$$7\mid (u^2-v^2)(u^4-6u^2v^2+v^4).$$
ومن ثم نحصل أيضًا على \(7\mid A\).
بجمع النتائج الثلاث نحصل على
$$4\mid A,\qquad 3\mid A,\qquad 7\mid A,$$
أي
$$84=4\cdot 3\cdot 7 \mid A.$$
إذن كل مثلث perfect بدائي هو تلقائيًا super-perfect، ولا توجد أي أمثلة مضادة ليتم عدّها.
أصغر مثال مألوف يوضح الفكرة كاملة. عند أخذ \(m=4\) و\(n=3\) نحصل على
$$a=4^2-3^2=7,\qquad b=2\cdot 4\cdot 3=24,\qquad c=4^2+3^2=25=5^2.$$
إذن \((7,24,25)\) مثلث perfect. والثلاثية المساعدة المختبئة داخله هي \((3,4,5)\)، أي يمكن أخذ \(u=2\) و\(v=1\). وعند التعويض في صيغة المساحة المفككة نجد
$$A=2\cdot 2\cdot 1\cdot (2^2-1^2)\cdot \left|2^4-6\cdot 2^2\cdot 1^2+1^4\right|=4\cdot 3\cdot 7=84.$$
حتى أول مثلث perfect بدائي هو بالفعل super-perfect، والبرهان السابق يوضح أن هذا الأمر قاعدة عامة لا استثناء لها.
التنفيذ يستخدم هذه النتيجة الرياضية في أقوى صورة ممكنة. فبعد إثبات أن كل مثلث قائم بدائي perfect هو بالضرورة super-perfect، يصبح عدد المثلثات perfect غير super-perfect تحت أي حد مساويًا للصفر دائمًا. ولهذا فإن الحل النهائي يعيد \(0\) مباشرة بدلًا من محاولة تعداد المثلثات حتى \(10^{16}\).
تطبيقات C++ وPython وJava كلها تعكس هذه الفكرة نفسها. نسخة Python هي الشكل المختصر المعتمد على البرهان فقط. أما نسختا C++ وJava فتحتفظان أيضًا بفحص brute-force محدود: تمران على معاملات إقليدس، وتتحققان من التباين الأولي واختلاف الزوجية، وتختبران ما إذا كان \(m^2+n^2\) مربعًا كاملًا، وتحسبان المساحة، ثم تؤكدان على مجال صغير أنه لا يظهر أي مثال معاكس تكون فيه \(84\nmid A\).
هذا الفحص الإضافي ليس هو المنهج الحقيقي للحل، بل مجرد اختبار صحة. المنهج الحقيقي هو البرهان أعلاه، لأنه يزيل الحاجة إلى أي بحث واسع النطاق.
بالنسبة للحل الفعلي، فإن الزمن \(O(1)\) والذاكرة \(O(1)\)، لأن البرنامج يعيد نتيجة البرهان مباشرة.
أما التعداد المساعد المستخدم للتحقق على مجالات صغيرة فهو أبطأ بكثير، ويزداد تقريبًا تربيعيًا مع حد معاملات إقليدس المختار. لكنه لا يغير تعقيد الحل النهائي إطلاقًا. وهنا تظهر قيمة البرهان: تجنب أي تعداد ضخم على مجال المسألة الحقيقي.