Liczba jako suma kwadratów dwóch innych liczb
Liczba jako suma kwadratów dwóch innych liczb
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??
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??
Liczba jako suma kwadratów dwóch innych liczb
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
to jest WKW
Liczba jako suma kwadratów dwóch innych liczb
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....
A tak btw: jak nie masz nic do powiedzenia w temacie, to daruj sobie pisanie....
-
- 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
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 .
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 .
-
- 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
Skoro "nie wiesz o co mu chodzi" to moze lepiej nic nie pisz? Bo niepotrzebnie robisz z siebie barana...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....
-
- 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
Mogę prosić o przedstawienie algorytmu Fermata? Muszę go użyć dla liczby 8089.
- Asakura
- 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
"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}}\).
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}}\).
-
- 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
Rozumiem, tyle, że mi chodzi o dokładny przykład. Ja muszę zrobić dla 8089.
- Asakura
- 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
\(\displaystyle{ 8089= 60^{2}+67^{2}}\) - tak jakby co, ale to znaleziony przy pomocy komputera (algorytmem Rogala)
a algorytmu Fermata nie znam
a algorytmu Fermata nie znam
-
- 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
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