Liczba jako suma kwadratów dwóch innych liczb

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
tytus
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 13 lut 2005, o 13:53
Płeć: Mężczyzna
Lokalizacja: Bajtlandia

Liczba jako suma kwadratów dwóch innych liczb

Post autor: tytus »

W jaki sposób sprawdzić, czy zadana liczba całkowita n może być przedstawiona w postaci sumy dwóch kwadratów liczb całkowitych??
Wszystko co znalazłem to:
a) Liczba n może zostać przedstawiona w postaci sumy dwóch kwadratów liczb całkowitych, jeżeli wszystkie dzielące ją liczby pierwsze postaci 4*k+3 dzielą ją parzystą ilość razy
(ang. Those numbers n whose prime divisors of the form 4*m+3 divide n an even number of times can be written as the sum of two squares.)
b) Liczba reprezentacji dodatniej liczby całkowitej jako sumy kwadratów dwóch liczb całkowitych równa jest 4 razy różnicy (d1-d3), gdzie d1 oznacza liczbę dzielników dających resztę 1 przy dzieleniu przez 4, a d3 liczbę dzielników dających resztę 3 przy dzieleniu przez 4. (ang. Jacobi's Two Square Theorem: The number of representations of a positive integer as the sum of two squares is equal to four times the difference of the numbers of divisors congruent to 1 and 3 modulo 4.)

Np. Jeżeli n=75, to (b) dzielnikami są 1,3,5,15,25 i 75, z czego do d1 należą (1,5,25) a do d3 (3,15,75), z czego wynika, że liczby 75 nie można przedstawić jako sumy dwóch kwadratów.
Korzystając z (a) dostajemy: dzielniki pierwsze postaci 4*m+3 to 3, czyli istnieje tylko jeden taki dzielnik - liczba jest więc nieparzysta - liczby 75 nie da się przedstawić jako sumy dwóch kwadratów.

Ale np. n=2888 można zapisać jako 2888=38^2 + 38^2.

Problem pojawia się, gdy n jest duże, np. rzędu 10^12 - w jaki sposób wtedy określić, czy liczbę n da się przedstawić jako sumę dwóch kwadratów czy nie?? Nie chodzi o podanie dokładnej reprezentacji liczby n, a jedynie stwierdzenie, czy reprezentacja taka jest możliwa. Czy istnieje jakiś algorytm pozwalający odpowiedzieć na to pytanie?? :?: :?: :?:
_el_doopa
Użytkownik
Użytkownik
Posty: 453
Rejestracja: 22 sie 2004, o 23:09
Płeć: Mężczyzna
Pomógł: 16 razy

Liczba jako suma kwadratów dwóch innych liczb

Post autor: _el_doopa »

Liczba n może zostać przedstawiona w postaci sumy dwóch kwadratów liczb całkowitych, jeżeli wszystkie dzielące ją liczby pierwsze postaci 4*k+3 dzielą ją parzystą ilość razy

to jest WKW
tytus
Użytkownik
Użytkownik
Posty: 2
Rejestracja: 13 lut 2005, o 13:53
Płeć: Mężczyzna
Lokalizacja: Bajtlandia

Liczba jako suma kwadratów dwóch innych liczb

Post autor: tytus »

Nie wiem o co Ci chodzi _el_doopa, ale jeśli masz coś do tłumaczenia, to zauważ, że poniżej jest angielska wersja, która został tam umieszczona, żeby każdy zrozumiał o co chodzi, nawet jeżeli moje tłumaczenie okaże się bezsensowne...

A tak btw: jak nie masz nic do powiedzenia w temacie, to daruj sobie pisanie....
Rogal
Użytkownik
Użytkownik
Posty: 5405
Rejestracja: 11 sty 2005, o 22:21
Płeć: Mężczyzna
Lokalizacja: a z Limanowej
Podziękował: 1 raz
Pomógł: 422 razy

Liczba jako suma kwadratów dwóch innych liczb

Post autor: Rogal »

Algorytm dałoby się znaleźć, ale nie będzie on za piękny.

Masz daną liczbę n, znajdujesz najbliższy kwadrat liczby naturalnej niewiększy od n, a następnie odejmujesz od n ten kwadrat i sprawdzasz, czy wyszedł Ci kwadrat. Jeżeli tak, no to masz szczęście , a jeżeli nie, to bierzesz kwadrat liczby naturalnej mniejszej o 1 od poprzedniej i zabawa zaczyna się od początku.

Jest to jednak dobre dla niezbyt wielkich liczb i tylko w przypadku, gdy napiszesz program.
W główce raczej się nie uda .
TomciO
Użytkownik
Użytkownik
Posty: 289
Rejestracja: 16 paź 2004, o 23:38
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 38 razy

Liczba jako suma kwadratów dwóch innych liczb

Post autor: TomciO »

Nie wiem o co Ci chodzi _el_doopa, ale jeśli masz coś do tłumaczenia, to zauważ, że poniżej jest angielska wersja, która został tam umieszczona, żeby każdy zrozumiał o co chodzi, nawet jeżeli moje tłumaczenie okaże się bezsensowne...

A tak btw: jak nie masz nic do powiedzenia w temacie, to daruj sobie pisanie....
Skoro "nie wiesz o co mu chodzi" to moze lepiej nic nie pisz? Bo niepotrzebnie robisz z siebie barana...
mirkaluk
Użytkownik
Użytkownik
Posty: 39
Rejestracja: 24 kwie 2012, o 15:15
Płeć: Kobieta
Lokalizacja: Katowice

Liczba jako suma kwadratów dwóch innych liczb

Post autor: mirkaluk »

Mogę prosić o przedstawienie algorytmu Fermata? Muszę go użyć dla liczby 8089.
Awatar użytkownika
Asakura
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 4 maja 2014, o 13:37
Płeć: Mężczyzna
Lokalizacja: Tarnów
Podziękował: 12 razy

Liczba jako suma kwadratów dwóch innych liczb

Post autor: Asakura »

"Liczba \(\displaystyle{ n}\) może zostać przedstawiona w postaci sumy dwóch kwadratów liczb całkowitych, jeżeli wszystkie dzielące ją liczby pierwsze postaci \(\displaystyle{ 4k+3}\) dzielą ją parzystą ilość razy "

Ten warunek wystarcza. Dzieje się tak dlatego, że każdą liczbę pierwszą postaci \(\displaystyle{ 4k+1}\) możemy przedstawić w postaci sumy dwóch kwadratów (tzw. Bożonarodzeniowe twierdzenie Fermata - tw. Fermata o sumie dwóch kwadratów) oraz dlatego że iloczyn sum kwadratów jest sumą kwadratów.
\(\displaystyle{ ( a^{2}+ b^{2} )( c^{2}+ d^{2} )=(ac+bd )^{2}+(ad-bc)^{2}}\)

I oczywiście \(\displaystyle{ 2= 1^{2}+ 1^{2}}\)
Czyli np. liczbę \(\displaystyle{ 10^{12}}\) da się przedstawić w postaci sumy dwóch kwadratów bo jedynymi jej dzielnikami pierwszymi są \(\displaystyle{ 2}\) i \(\displaystyle{ 5= 2^{2} + 1^{2}}\).
mirkaluk
Użytkownik
Użytkownik
Posty: 39
Rejestracja: 24 kwie 2012, o 15:15
Płeć: Kobieta
Lokalizacja: Katowice

Liczba jako suma kwadratów dwóch innych liczb

Post autor: mirkaluk »

Rozumiem, tyle, że mi chodzi o dokładny przykład. Ja muszę zrobić dla 8089.
Awatar użytkownika
Asakura
Użytkownik
Użytkownik
Posty: 21
Rejestracja: 4 maja 2014, o 13:37
Płeć: Mężczyzna
Lokalizacja: Tarnów
Podziękował: 12 razy

Liczba jako suma kwadratów dwóch innych liczb

Post autor: Asakura »

\(\displaystyle{ 8089= 60^{2}+67^{2}}\) - tak jakby co, ale to znaleziony przy pomocy komputera (algorytmem Rogala)
a algorytmu Fermata nie znam
mirkaluk
Użytkownik
Użytkownik
Posty: 39
Rejestracja: 24 kwie 2012, o 15:15
Płeć: Kobieta
Lokalizacja: Katowice

Liczba jako suma kwadratów dwóch innych liczb

Post autor: mirkaluk »

Dzięki Też to znalazłam programowo, ale polecenie mówi wyraźnie, żeby użyć metody Fermata. Jeszcze jutro poproszę prowadzącego o wytłumaczenie, bo nie ruszę tego
ODPOWIEDZ