Matematické Fórum

Saturday · 10. 10. 2009 12:24

Ukažte, že v $\mathbb{Z}_n$ jsou prvky a, b asociované <=> NSD(a, n) = NSD(b, n)

Prvky a, b jsou asociované pokud platí $a | b$ a zároveň $b | a$ ("a | b" značí "a dělí b").

Neporadil by mi s tím někdo?

EDIT: Moje úvaha ohledně implikace "=>":

Pokud bych byl v $\mathbb{Z}$ , pak by platilo toto:

Máme NSD(a, n), protoze a|b => NSD(a, n) = SD(b, n) SD značí nějakého společného dělitele
protoze b|a => NSD(b, n) = SD(a, n)

Z toho dal: SD(a, n) <= NSD(a, n) <= SD(b, n) <= NSD(b, n) <= SD(a, n) => NSD(a, n) = NSD(b, n)

xxsawer · 12. 10. 2009 02:26

Myslim, ze tohle je uplne jasny, jestli to teda dobre chapu...

Co totiz znamena ze a|b (a deli b)?
To znamena, ze b je delitelny a nebo taky, ze b mod a = 0
Obracene b|a znamena, ze a je delitelny b nebo taky, ze a mod b = 0
Kdy jsou tyhle dve podminky splneny? No preci jenom kdyz a = b tim padem je jasny, ze ty dva prvky maji stejnyho NSD coz sou vlastne ty samotny prvky...
Jestli ti jde o ten vyraz NSD(a, n) = NSD(b, n) tak to je pak taky jasny...Kdyz a = b tak maji stejny rozklad na prvocisla a tim padem maji stejnyho NSD s jakymkoli jinym cislem...

Kondr · 12. 10. 2009 08:30

↑ xxsawer:To bohužel není dobže, protože se pohybujeme v $\mathbb{Z}_n$ . Třeba v $\mathbb{Z}_{12}$ platí 5*5=1 a 5*1=5, proto 5|1 a 1|5. Na druhou stranu 2 nedělí 5.

Kondr · 13. 10. 2009 23:42

↑ Saturday:To NSD se musí brát v $\mathbb{Z}$ , jinak by nebylo jednoznačné. A pokud a|b v $\mathbb{Z}_n$ , pak v $\mathbb{Z}$ $ka+ln=b$ , takže opravdu NSD(a,n)=SD(b,n), tvůj důkaz je dobře.

Druhá strana: NSD(a,n)=NSD(b,n)=d, n=de, a=df, b=dg. Nechť G je inverze g (mod e), z nesoudělnosti g a e takové G existuje. Pak
gG=te+1
$b(fG)=dfgG=dfet+df=dn+df\equiv a\pmod{n}$ , takže $b|a$ , symetricky dokážeme $a|b$ .

Saturday · 18. 10. 2009 11:51

Díky moc!

EDIT:

Jeste zkusim rozpitvat tu mou implikaci, jestli jsem to dobre pochopil:

NSD tedy počítám v $\mathbb{Z}$ , pro c = NSD(a, n) mi tedy platí: $c|a \equiv p \cdot c = a$ , $c|n \equiv q \cdot c = n$ .

$a|b \text{ v } \mathbb{Z}_n \equiv k \cdot a + l \cdot n = b \text{ v } \mathbb{Z}$

Abych ověřil, že c = SD(b, n), tak stačí ověřit, že platí c|b a c|n (toto už mám).

$c|b \equiv r\cdot c = b = k \cdot a + l \cdot n$ a za r můžu dosadit: k.p + l.q a rovnost platí => c|b.

Je to dobře?

Matematické Fórum

#1 10. 10. 2009 12:24

Algebra - NSD

#2 12. 10. 2009 02:26

Re: Algebra - NSD

#3 12. 10. 2009 08:30

Re: Algebra - NSD

#4 13. 10. 2009 23:42

Re: Algebra - NSD

#5 18. 10. 2009 11:51

Re: Algebra - NSD

Zápatí