Matematické Fórum

vytautas · 03. 08. 2015 22:35

zdravím

neviem si poradiť s príkladom
Dokážte: Ak $x^2 \equiv n \mod 65$ má riešenie, tak aj $x^2 \equiv (-n) \mod 65$ má riešenie.

ďakujem za každú pomoc.

vanok · 04. 08. 2015 04:25 — Editoval vanok (04. 08. 2015 07:06)

Ahoj ↑ vytautas:,
Toto cvicenie sa da riesit aj stredoskolskymi metodamy.
Napr. vysetrit nejaku vlastnost mod 65, staci vybrat po jednom vsetkych moznych representantov. To sa urobi napriklad vyberom
$-32,-31,...,-1,0, 1,...,31,32$ . Vyhoda tohto vyberu pre tvoje cvicenie je zrejma.
Teraz mozes uvazovavat o stvorcov vsetkych tychto representatov, a konstatovat, ze modulo 65
$(-32)^2=32^2=-16$
$(-31)^2=31^2=-14$
...
$(-1)=1^2=1$
$(-0)^2=0^2=0$

To ti umozni po vypoctoch konkretneho vycislenia kazdeho riadku aj tie z .... (ktore pochopitelne pre jasnost musia byt napisane ako representanty modulo 65 vybrane vyssie) dat odpoved na otazku tvojho cvicenia.

Tak po vypoctoch a uvahach, budes mat dokonale riesenie....

Urob to podrobne, potom mozme hladat ine moznosti dokazu....

vanok · 04. 08. 2015 06:29 — Editoval vanok (04. 08. 2015 09:58)

Pridam ti tu este malu poznamku. Ako postupovat ak by si chcel riesit take rovnice ( ak je to mozme)
Ukazem ti to na jednom priklade.
Riesenie rovnice $x^2 \equiv -1 \mod 65$
Ktora sa ekvivalentne pise $x^2 +1 \equiv 0 \mod 65$
ma riesenia $8,-8, 18, -18$ (Medzi representatmy co som napisal vyssie)
To jednoducho uvidis z vypoctov o ktorych som pisal v ↑ vanok:.
Tiez mozes konstatovat, ze $x^2+1\equiv (x-8)(x+8) \equiv (x-18)(x+18) \mod {65}$
co su 2 mozna faktorizacie ( v pripade ak by sa pracovalo modulo p, prvocislo je mozne len jedina faktorizacia)

Poznamka.

Autor skryl část textu. Zobrazit/skrýt!

vytautas

↑ vanok:
ďakujem za vyčerpávajúci príspevok

mám pár otázok naň:
v prvom rade, je mi jasné, že zvyšky po delení 65 môžu byť len $(-32,-31..0..31,32)$ ale prečo ma zaujímajú ich mocniny ? však v tej rovnici je zvyšok n a číslo x môže byť ľubovoľné, nie ?
uniká mi pointa
vopred ďakujem za ochotu a čas.

edit : práve som pochopil, tie čísla, tento príspevok teda ignorujte, ďakujem.

vytautas · 04. 08. 2015 16:37

↑ vanok:

keď som si prešiel všetky "representanty" tak každý má dvojicu s opačným znamienkom, takže to platí.
aká je teda iná možnosť riešenia ? hlavne elegantnejšia

čo sa týka poznámky, zvykol som si tieto čísla značiť $\mathbb{Z}^{zvysok}_{modulo}$ no vidím, že váš zápis je jednoduchší.

ešte jedna otázka, z čoho vyplýva, že $x^2+1 \equiv (x+8)(x-8) \equiv (x-18)(x+18) \mod 65$ ? vidím, že to platí, no chcel by som vedieť prečo.

ďakujem .

vanok · 04. 08. 2015 17:13

↑ vytautas:,
Pri beznom deleni cislom 65 sa uvazuju zvysky $0,1,2,...,63,64$
Tu som ti navrhol miesto klasickych zvyskov pouzitie ich representantov tak aby si mal bez tazkosti "kladne ako aj zaporne representacie" ako napr v tvojom prvom prispevku.
Tie mocniny nas zaujimaju lebo chces vysetrovat rovnice ako
$x^2 \equiv n \mod 65$ . A tak je zaujimave vediet ako su mozne obrazy pre funkciu
$x\to x^2$ modulo 65. Lebo je jasne ze len pre n ktore su v obraze moze mat rovnica typu $x^2 \equiv n \mod 65$ aspon jedno riesenie.

vanok · 04. 08. 2015 17:38 — Editoval vanok (04. 08. 2015 19:29)

Ilustraciu $x^2+1 \equiv (x+8)(x-8) \equiv (x-18)(x+18) \mod 65$ dostanes vdaka tabulke co som ti navrhol urobit.Jeden z riadkov z nej je $(-8)^2=8^2=64=-1\mod 65$ a iny $(-18)^2=...$ ( je to uzitocna etapa na hladanie rieseni a tiez ked je uz cela urobena umozni ti to bez omylu dat odpoved na danu otazku cvicenia) potom identita $a^2-b^2=...$ mod 65 pochopitelne plati....
No ale tu nas zaujimaju vysledky modulo 65, tak to nemozes pouzit v opacnom smere, cize povedat co plati mod 65, plati aj v prirodzenych ciskach.( priklad, mod 65 mas $8^2=-1$ ale to pochopitelne neplati pre celé cisla... To je jedna z pricin, preco sa taketo teorie neucia na SS)

Chcel by som vidiet ze vdaka tabulke si schopny napisat dobry dokaz ... Tak ho nam tu podrobne napis.( vediet pisat zrozumitelne riesenie je nevyhnutne, ak chces napredovat)
Tato technika riesenia je "vysetrenie vsetkych moznych pripadov ( alternativ)".
Aky je zdroj tvojho cvicenia?
Nemozem ti tu navrhovat ine riesenia, ben toho aby som vedel co si uz nastudoval a pochopil.
Take zakladne citanie mas napr tu
http://mathafou.free.fr/themes_en/kcongr.html

vytautas

↑ vanok:

ak som to správne pochopil, tak $x^2+1 \equiv (x+8)(x-8) \mod 65$
pretože platí $a \equiv b \mod m \Rightarrow a \equiv m-b \mod m$ a $(x+8)(x-8)=x^2-64$
čo sa dá zapísať ako $x^2+1 \equiv 0 \mod m$ alebo $x^2 \equiv -1 \mod m$

hmm, čo sa týka dôkazu, nejaký náčrt

keďže pracujeme mod 65, tak stačí uvažovať čísla (-32,-31 ,, 0 ,, 31 ,32) pretože každé iné číslo je kongruentné s nejakým číslom z tejto množiny.
po vypísaní tabuľký všetkých druhých mocnín čísel z množiny je vidieť, že každý zvyšok sa objavuje vždy aj s jeho opačným číslom .
čiže rovnica $x^2 \equiv n \mod 65 \Rightarrow x^2 \equiv (-n) \mod 65$
ako urobiť korektný dôkaz mi nenapadá.

zdroj: Birkhoff,Saunders Prehľad modernej algebry
pred touto kapitolou sú komutatívne okruhy, obory integrity, euklidov algoritmus, základná veta aritmetiky, dobré usporiadanie.
toto by som mal ako tak zvládať.

ďakujem za ochotu

odkaz prezriem, vyzerá byť dosť užitočný, no chýbajú mi dôkazy tvrdení.

vanok · 04. 08. 2015 21:47 — Editoval vanok (04. 08. 2015 21:54)

To na zaciatku si priliz komplikujes.
Staci povedat
Vseobecne pre kazde celé cislo plati $(x+8)(x-8)=x^2-64$
Toto sa pise modulo 65
$x^2+1 \equiv (x+8)(x-8) \mod 65$ .kOniec dokazu.
Poznamka
Toto ( tvoj druhy riadok) $a \equiv b \mod m \Rightarrow a \equiv m-b \mod m$ nema zmysel.

Tvoj riadok 3, to je len ukazka ze $x^2 \equiv -1 \mod m$
da $x^2+1 \equiv 0 \mod m$ .... A vtedy nas moze napadnut ta faktorizacia.

Tvoj nacrt dokazu je celkom dobry. ( napisat tu celu tabulku by to este viac objasnilo)
To si chcel napisat
$(\exists x,x^2 \equiv n \mod 65) \iff (\exists x, x^2 \equiv (-n) \mod 65)$
Takyto dokaz sa casto pouziva (povie sa tiez ze je konstruktivny).
Ked hovoris o mnozine, tak pis $\{-32,-31,...,-1,0, 1,...,31,32 \}$ . To tvoje znacenie z (...) znamena postupnost alebo aj 65-ticu.
Bolo by dobre (a elegantne) napisat aky je skutocne obraz $x\to x^2$ I ked sa da vycitat z tes tabulky. A povedat, ze ze len pre prvky obrazu rovnica $x^2 \equiv n \mod 65$ moze mat riesenie.
Na koniec citanie co som ti postal vyssie dava klucove myslienky dokazov. A riesenie cvicenia mozu ti velmi posluzit. Tiez tam poklikaj aj na ine temy...
Kniha co citas, je vyborna.

vytautas · 04. 08. 2015 22:12

↑ vanok:

tabuľka:

Autor skryl část textu. Zobrazit/skrýt!

"Bolo by dobre (a elegantne) napisat aky je skutocne obraz $x\to x^2$ I ked sa da vycitat z tes tabulky. A povedat, ze ze len pre prvky obrazu rovnica $x^2 \equiv n \mod 65$ moze mat riesenie."

nechápem presne túto vetu. v akom zmysle "aký" má byť obraz ?
myslí sa tým injekcia/surjekcia/bijekcia ?
ďakujem .

vanok · 04. 08. 2015 22:56

Obraz je vytvoreny vsetkymi prvkamy co su na pravo rovnosti. Napr tam nie je 3.
Tak $x^2 \equiv3 \mod 65$ nema ziadne riesenie.

Obraz $x\to x^2$ mod 65 je $\{0,\pm 1,\pm 4,...\pm 30 \}$

To uz lahucko doplnis z tej tabulky.

vytautas

↑ vanok:

jasné, teraz už chápem. Je tam nejaká zákonitosť, prečo práve niektoré čísla sú a niektoré nie sú závislá od modula ?

obraz je $\{0, \pm 1, \pm 4, \pm 9, \pm 10, \pm 14, \pm 16, \pm 25, \pm 26 ,\pm 29, \pm 30 \}$

vanok · 04. 08. 2015 23:17

↑ vytautas:,
Pochopitelne, tu pracujes modulo 65=5x13.
Keby sa pracovalo z nejakym prvocislom, situacia by bola v nieco mais jednoduchsia ...
Ale take prehlbenia si nechaj na druhe citanie tvojej knihy.
Tu je dolezite pochopit ako sa pracuje v okruhoch a potom v telesach.
Napreduj v tvojom citani a skus takto ako v tomto cviceni analyzovat situacie.
Dobre pokracovanie.

Brano · 05. 08. 2015 20:54

no ked uz si odpozoroval nejake zakonitosti, tak aby si urobil nejaky elegantny dokaz tak by si mohol postupovat takto:(vsetko bude mod 65)

predpokladas, ze $x^2=n$ ma riesenie a hladas riesenie rovnice $y^2=-n$ . dokazes napisat taku funkciu (presny predpis) $y=f(x)$ ktora bude splnat $f(x)^2=-x^2$ ?

hint: najpv by som skusal linearne fcie :) a odpoved uz mas v predchadzajucich prispevkoch.

vanok · 06. 08. 2015 01:15

Ahoj ↑ Brano:,
To myslis o vyuzitie $x^2 \equiv -1 \mod 65$ jedneho z rieseni ktore som popisal tu ↑ vanok: ?
Pochopitelne je to mozna cesta, i ked neviem ci to treba povazovat za "elegantny dokaz", ja by som len povedal iny dokaz.

Brano · 06. 08. 2015 11:31

↑ vanok:
elegentny v zmysle, ze sa da zapisat do jedneho riadku, nie ze by mal nejaku hlboku myslienku.

vanok · 06. 08. 2015 13:12 — Editoval vanok (06. 08. 2015 18:43)

↑ Brano:,
To je pravda, a iste si poznamenal, prave preto som napisal vyssie riesenia $x^2 \equiv -1 \mod 65$ . No vsak myslenie pomocou " morfismov" nie je asi uplne prirodzene, i ked by som ho cakal od vysokoskolaka po studiu prveho rocniku VS. No vsak tu kolega zatial precital len zaciatok peknej Birkhoff-vej knihy. Iste po jej precitani a vyrieseni cviceni bude pouzivat co najucinejsie metody riesenia.
Akoze kolega nereagoval pridavam jednu variantu toho kratkeho dokazu, ktory si moze pozriet pre kontrolu.

Autor skryl část textu. Zobrazit/skrýt!