WisFaq!

Re: Re: 2de graads 2onbekenden

Hans,

Toch maar je antwoorden nader bestudeerd. Bij het laatste deel van je antwoord, struikel ik over deze twee stukken:

Na drie stappen krijg je hetzelfde rijtje resten terug (immers (oneven-2)+oneven+(oneven+2)=3*oneven)
Wat gebeurd hier?

Conclusie 1) d=1 mod 2 2) d=0 of d=2 mod 3

1) is het oneven deel en 2) de repeat van de mod3 sequence

Samengenomen levert dit d=3 of d=5 (mod 6)
Hoe doe je dat nou ineens? Waar komt die mod 6 vandaan?

Voor grotere problemen kun je nog andere getallen dan 4 of 3 eerst uitzoeken.

Weet je toevallig of het uitmaakt welke mod's je probeert? (Even getallen lijkt me op het 1ste gezicht niet echt voor de hand liggend)

Ik heb over dergelijke methodes waarbij een matrix ontstaat met mogelijke waarden, die dan oplosbaar zou zijn met de CRT (chinese remainder theorm) is dat wat je bedoelt?

David

David
15-4-2006

Antwoord

Wat gebeurt hier:
Even terug naar waar we mee bezig waren: We zochten d's waarvoor d²+34d+30 een kwadraat is.
Als je gevonden hebt dat d²+34d+30 geen kwadraat modulo n is, dan is d+k.n dat ook niet, immers d²=(d+k.n)² (mod n) en 34d=34(d+k.n)(mod n)

waar komt die 6 vandaan: kgv(2,3)=6

Maakt het uit welke "mod's" je probeert:

• kies ze relatief priem anders krijg je geen extra informatie
  
• machten van 2, b.v. 16 zijn erg efficient; Je zou b.v. 9 en 16 (of zelfs 64) kunnen nemen, eventueel aangevuld met een paar andere priemgetallen

Uiteindelijk kom je inderdaad uit bij de Chinese Reststelling, zie bijvoorbeeld Chinese Remainder Theorem en dan met name het gedeelte over Simultaneous Congruences

hk
16-4-2006