Teoria Sumy Kwadratów pozwala stwierdzić kiedy liczbę całkowitą większą od 1 można zapisać jako sumę kwadratów dwóch liczb. Wykorzystuje ona do tego rozkład liczby na czynniki pierwsze. Poniższy artykuł przedstawio sposób implementacji algorytmu rozwiązującego zagadnienie.
Nieparzysta liczba pierwsza p może zostać wyrażona jako suma dwóch kwadratów wtedy i tylko wtedy, gdy p mod 4 = 1.
Dowolna liczba całkowita większa od 1 może zostać zapisana jaok suma dwóch kwadratów wtedy i tylko wtedy, gdy w jej rozkładzie na czynniki pierwsze nie ma czynnika pierwszego p, który jest podniesiony do nie parzystej potęgi, a on sam spełnia warunek p mod 4 == 3.
Teoria Fermata ogranicza się jedynie do liczb pierwszych, ale biorąc pod uwagę też uzupełnienie jesteśmy w stanie odpowiedzieć dla dowolnej liczby całkowitej n czy uda się ją zapisać w postaci n = a2 + b2. Przykładowo liczba 13 jest pierwsza i spełnia warunek 13 mod 4 == 1. Można ją zapisać jako: 13 = 32 + 22. Weźmy przykładowo liczbę 1234. Nie jest to liczba pierwsza, więc musimy odwołać się do uzupełnienia teorii. Pierwszy krok polega na rozkładzie na czynniki pierwsze czyli 1234 = 2·617. Obydwie liczby są pierwsze i 2 mod 4 = 2, a 617 mod 4 = 1, więc istnieje rozkład: 1234 = 32 + 352.
W celu znalezienia rozkładu pewnej liczby sprawdzamy kolejne potęgi. Na ich podstawie obliczamy obydwa składniki i sprawdzamy czy suma ich kwadratów daje liczbę wejsciową. Oto przykładowa funkcja SzukajRozkladu():
Poszukiwania ograniczamy do wartości, których kwadrat jest nie większy od liczby wejściowej. Do sprawdzenia czy drugi obliczony składnik ma pierwiastek należy wpierw go obliczyć, zaokrąglić do liczby całkowitej, a następnie podnieść ponownie do kwadratu. Należy tutaj pamiętać, że dużą rolę odgrywa przybliżona postać wyniku operacji pierwiastka.
Do sprawdzenia warunków teorii jak również jej uzupełniania potrzebna jest metoda do sprawdzenia czy dana liczba jest pierwsza. Następnie można napisać poniższą funkcję, która zwraca informację czy według teorii rozkład istnieje:
Powyższa implementacja wpierw sprawdza warunek dla liczb pierwszych, a następnie dotyczący rozkładu na czynniki pierwsze. Nie jest ona optymalna, ponieważ wpierw należałoby wyznaczyć tablicę liczb pierwszych, a nie przechodzić po kolejnych wartościach i sprawdzać czy są one pierwsze. Powyższy kod ma jedynie zastosowanie demonstracyjne.
Do przetestowania kodu można uruchomić poniższy fragment kodu. Wypisze on dla wpisanej liczby jaki ma rozkład lub, że nie ma oraz co orzeka toeria dla danej liczby.