Som van twee kwadraten

[efdee]

Stelling van Fermat zegt, dat ieder priemgetal van de vorm 4k+1 te schrijven is als de som van twee kwadraten.
Hoe kun je zonder te proberen de twee kwadraten berekenen? Bestaat er een rekenwijze voor?

[ukster]

Er bestaat een methode om de twee kwadraten te berekenen die de priemgetallen van de vorm 4k+1 vormen, zonder te proberen en gaat als volgt:

Stap 1: Schrijf het priemgetal p als 4k+1.

Stap 2: Bepaal de waarde van k.

Stap 3: Kies een willekeurig getal a tussen 1 en p-1.

Stap 4: Bereken a^(p-1)/2 (mod p).

Stap 5: Als de uitkomst gelijk is aan 1, dan is p de som van twee kwadraten. Als de uitkomst gelijk is aan -1, dan is p niet de som van twee kwadraten.

Stap 6: Als de uitkomst -1 is, kies dan een ander getal a tussen 1 en p-1 en herhaal stap 4 en 5 totdat je een uitkomst vindt die gelijk is aan 1.

Stap 7: Als je een uitkomst hebt gevonden die gelijk is aan 1, dan kun je de twee kwadraten berekenen met behulp van de formule a^((p-1)/2) = x^2 - y^2, waarbij x en y de twee kwadraten zijn.

Deze methode werkt alleeen voor priemgetallen van de vorm 4k+1 en niet voor andere priemgetallen. Ook kan het vinden van een geschikt getal a en het uitvoeren van de berekeningen flink wat tijd in beslag nemen, afhankelijk van de grootte van het priemgetal.

[efdee]

Het lijkt me, dat stap 7 één vergelijking geeft met 2 onbekenden.
En dan ben ik nog net zo ver. Ik moet nog proberen.

[CoenCo]

Het lijkt me, dat stap 7 één vergelijking geeft met 2 onbekenden.
En dan ben ik nog net zo ver. Ik moet nog proberen.

De tweede vergelijking is natuurlijk x^2+y^2=p

[efdee]

Warempel!

[ukster]

Het verband tussen kwadratensommen en priemontbinding is een zeer mysterieus gebied waar je je hoogstens over kunt verwonderen. Wiskundige reuzen zoals Fermat, Euler, Gauss en Brahmagupta zagen dit verband... misschien alsof ze vanaf een bergtop naar beneden keken. Ze hadden een vogelperspectief van alle omliggende wegen, rivieren, heuvels en valleien op de kaart van de wiskunde.
Voor mezelf vrees ik het ergste. Mijn perspectief is min of meer vanuit een putje in dat landschap en het onvermogen over de rand te kunnen kijken.

[RedCat]

Voorbeeld: p = 73:
Stap 1: Schrijf het priemgetal p als 4k+1.
73 = 4*18 + 1
Stap 2: Bepaal de waarde van k.
k = 18
Stap 3: Kies een willekeurig getal a tussen 1 en p-1.
kijk naar a = 5, a = 4 en a = 3
Stap 4: Bereken a^(p-1)/2 (mod p).
(73-1)/2 = 36
5^36 ≡ 72 ≡ -1 mod 73
4^36 ≡ 1 mod 73
3^36 ≡ 1 mod 73
Stap 5: Als de uitkomst gelijk is aan 1, dan is p de som van twee kwadraten. Als de uitkomst gelijk is aan -1, dan is p niet de som van twee kwadraten.
??? p = 73 is de som van 2 kwadraten, ongeacht de keuze van a
Stap 6: Als de uitkomst -1 is, kies dan een ander getal a tussen 1 en p-1 en herhaal stap 4 en 5 totdat je een uitkomst vindt die gelijk is aan 1.
zowel a = 4 als a = 3 geven uitkomst 1
Stap 7: Als je een uitkomst hebt gevonden die gelijk is aan 1, dan kun je de twee kwadraten berekenen met behulp van de formule a^((p-1)/2) = x^2 - y^2, waarbij x en y de twee kwadraten zijn.
???

Ik loop vast bij stap 7: zowel a=4 als a=3 voldoen aan de eerste 6 stappen, maar dan levert stap 7 voor deze waarden van a twee verschillende gelijkheden.
Indien je in stap 7 mod p werkt, dan zou het verschil van de kwadraten 1 zijn (1 ≡ x^2 - y^2 mod 73), en dat lijkt me ook niet mogelijk.

Aan de andere kant:
8^2 + 3^2 = 64 + 9 = 73
maar dan is
8^2 - 3^2 = 64 - 9 = 55
Hoe krijg ik de waarde 55 uit dit algoritme??

Zie ik iets over het hoofd, of klopt er iets niet (typefout of copy/paste-fout??) in bovenstaand rekenschema?

[ukster]

Nog veel erger...
Dit probleem heb ik opgegeven aan chatgpt met het idee: nu krijg ik een mooi uitgewerkt- en juist antwoord als resultaat. Inderdaad..een rekenschema. Echter tot mijn verbazing, genereert chatgtp verschillende werkwijzen en geeft(deels) onjuiste uitkomsten. Als hetzelfde probleem in iets andere bewoordingen wordt ingevoerd,weer een ander verhaal met weer andere antwoorden. Geen pijl op te trekken dus. Mijn verwachtingen van dit programma zijn duidelijk te hoog.

[RedCat]

Gelukkig hoeven we chatgtp nog niet toe te voegen aan je rij met illustere wiskundige grootheden.

Een algoritme dat wel de oplossingen geeft kan je bv. hier vinden:
https://en.wikipedia.org/wiki/Fermat%27 ... #Algorithm
(Stan Wagon, 1990)

Voorbeeld:
p = 73:
q ≡ 5 is een non-residu, want 5^36 ≡ 72 ≡ -1 mod 73
(nagenoeg de helft van de getallen is non-residu mod p, dus een non-residu is statistisch gezien redelijk snel te vinden)
x ≡ 5^((73-1)/4) ≡ 5^18 ≡ 27 mod 73
Het algoritme van Euclides toegepast op p=73 en x=27:
73 = 2*27 + 19
27 = 1*19 + 8
19 = 2*8 + 3
en hier kunnen we stoppen: resten 8 en 3 zijn kleiner dan √73 en leveren het antwoord:
73 = 8^2 + 3^2

[wnvl1]

Dit staat in de inleiding van de paper waarnaar Redcat verwijst.

Wat houdt dat begrip <n> precies in?
Het residu van n modulo p snap ik wel. Maar die voorwaarde |<n>|< p/2 is iets merkwaardig.
Dus als niet aan die voorwaarde voldaan is, dan kan je die <n> niet berekenen? En daarom is dat algoritme van Gauss niet nuttig? Er wordt verwezen naar een boek dat ik niet heb.

[RedCat]

Je laat je residu systeem niet lopen van 0 t/m (p-1), maar van -(p-1)/2 t/m (p-1)/2
Dus als p=73 niet van 0 t/m 72, maar van -36 t/m 36:

\(\small \alpha = \left< \frac{1}{2}{36 \choose 18} \right> \equiv 4537567650 \equiv 70 \equiv -3 \mod 73 \)

\(\small \beta = \left< 36!\cdot(-3) \right> \equiv -1115979980369703652403998344452505600000000 \equiv 65 \equiv -8 \mod 73 \)

en 73 = (-3)^2 + (-8)^2 = 9 + 64

Voor grote getallen zal dit problemen geven (tenzij er een snelle methode bestaat om binomiaalcoefficienten modulo priem p te berekenen).

Voorbeeld via het eerdere algoritme:
p = 10^99 + 289:
q = 3 is een non-residu
x = 188076053837630988270047605443300107367818661345815100892035410291103004237033541235728198596018617
waardoor via het algoritme van Euclides op p en x onze resten worden:
r1 = 25487683179629814214159077941847650547481502674583
r2 = 18718386846489081032697054048851303459568883340420
waarmee
p = r1^2 + r2^2

Bovenstaande gaat zeer snel.
Via de formule van Gauss verwacht ik een veel langere rekentijd.


PS:
Ik heb dat artikel niet, en weet dus ook niet naar welk boek verwezen wordt.

[ukster]

ik vond nog een voorbeeld uit:
MATHEMATICS OF COMPUTATION, VOLUME 26, NUMBER 120, OCTOBER 1972
Note on Representing a Prime as a Sum of Two Squares
By John Brillhart

[wnvl1]

Ik heb dat artikel niet, en weet dus ook niet naar welk boek verwezen wordt.

Ik weet niet wat de policy is van het forum mbt links naar sci-hub, maar hier de link.

https://sci-hub.hkvisa.net/10.2307/2323912

[Nesciyolo]

De tweede vergelijking is natuurlijk x^2+y^2=p

Mijn middelbare school wiskunde is wat weggezakt. Dus misschien zeg ik nu iets heel doms.

Bovenstaande formule lijkt me een cirkel te beschrijven met straal √p (wortel p).
De opgave lijkt me dus: vind punten op de cirkel met middelpunt (0,0) en straal √p waarvoor geldt dat zowel x als y gehele getallen zijn.

2 is het enige even priemgetal en voldoet als ik het goed begrijp niet aan de p = 4k+1 voorwaarde (als k een geheel getal moet zijn). De som van de kwadraten moet dus oneven zijn. Dat betekent dat we altijd op zoek zijn naar één even en één oneven kwadraat, en dus naar één even en één oneven x en y.

Als iemand een methode weet om alle punten op een cirkel met een geheel en positieve x èn y te bepalen zonder proberen zal dat de oplossing van dit probleem zijn.

Werkt het ook de andere kant op? Kan je zeggen 1² + (2a)² is een priemgetal voor alle waardes van a?
In elk geval niet voor a = 4 (1 + 64 = 65 is geen priemgetal) en en a = 6 (145).
Misschien voor alle oneven waardes van a of als a een priemgetal is?

[Nesciyolo]

Misschien voor alle oneven waardes van a of als a een priemgetal is?

Nee ook niet. Alle waardes van a die eindigen op 1, 4, 6 en 9 behalve 1 zelf vallen sowieso af.