Matematické Fórum

vytautas · 16. 08. 2015 12:48

zdravím

mám úlohu : "Ukážte, že prvok $c \in \mathbb{Z}_n$ , ktorý nie je deliteľom jednotky, je deliteľom nuly.

moje riešenie.
ak je prvok deliteľom jednotky v $\mathbb{Z}_n$ tak existuje riešenie rovnice $ax \equiv 1 \mod n$ , čiže $|gcd(a,n)|=1$
keď prvok nie je deliteľom jednotky, tak $|gcd(a,n)| > 2$ a to znamená, že je deliteľom nuly v $\mathbb{Z}_n$ .

je to správne ?

ďakujem .

vytautas · 16. 08. 2015 22:10

v podstate by úloha mala byť ekvivalentná s tvrdením

ak $\not \exists x ; ax \equiv 1 \mod n \Rightarrow \exists y; ay \equiv 0 \mod n$

ako v prvom príspevku, x neexistuje práve vtedy, keď $gcd(a,n) \nmid 1$ a tak musí byť $gcd(a,n) > 1$ (ak beriem, že gcd je len kladné)

keď tak teraz rozmýšľam, ako presnejšie dokázať, že ak $gcd(a,n)=d$ a $d\not =1$ tak potom je $a$ deliteľom nuly, že existuje $y$ také,čiže $ay \equiv 0 \mod n$

ďakujem .

vanok · 17. 08. 2015 14:05 — Editoval vanok (18. 08. 2015 09:11)

[img][/img]Ahoj ↑ vytautas:,
Ide o pekne cvicenie, vlasnost ktoru pripomina, je zial akokeby zabudnuta vela studentamy.
Vidim ze si sa snazil preformulovat tvoje cvicenie. Mas tam au dobre myslienky....

Ukazem ti, trochu viac ako to co je formulovane v tvojom cviceni.

$\mathbb{Z}_n$ je disjonktna unia mnoziny jeho delitelov jednotky a mnoziny jeho delitelov nuly.
Naviac
$\bar{x} \in \mathbb{Z}_n$ je delitelom jednotky v $\mathbb{Z}_n$ len a len ak $(x,n)=1$
$\bar{x} \in \mathbb{Z}_n$ je delitel nuly v $\mathbb{Z}_n$ len a len ak $(x,n)>1$

Nech $d=(x,n)$ .
Ak $\bar{x}$ je delitelom jednotky a $\bar{y}=(\bar{x})^{-1}$ , tak mame $xy=1 \mod n$ , a preto existuje $k \in \mathbb{Z}$ take, ze $xy-1=kn$ . Co da $d|xy-kn=1$ a preto $d=1$ .
Reciprocne, nech d=1. Bachet-ova veta nam zarucuje, ze existuje $u,v \in \mathbb{Z}$ take, ze $xu+vn=1$ . To nam da $xu=1 \mod n$ a preto $\bar{x}$ je delitelom jednotky v $\mathbb{Z}_n$ .
Edit. Oprava podla beznej pouzivanej sk terminologie

Porozmyslaj o tejto casti dokazu, kde som vyuzil uzitocnu Bachet-ovu vetu.
Zvysok to bude pokracovanie. ( ale nic ti nebrani trochu o tom porozmyslat)

Brano · 17. 08. 2015 21:17 — Editoval Brano (17. 08. 2015 21:30)

↑ vytautas:

tu mas v podstate "chybu" v dokaze (chybu v zmysle, ze ti tam chyba argumentacia)
totizto vyzera to, ze tvrdis : "a je delitel jednotky" implikuje "(a,n)=1" a teda "a nie je delitel jednotky" implikuje "(a,n)>2" ale takto implikacia nefunguje - v prvom tvrdeni by si potreboval presne opacnu implikaciu
(ktora v skutocnosti plati - pozri Bezoutovu identitu)

Alternativny dokaz:
Nech $a\in Z_n$ uvazujme vsetky $a\cdot k$ pre $k=1,2,...,n-1$ - tento sucin ale moze nadobudat iba hodnoty $0,1,2,...,n-1$ - lebo sme v $Z_n$ . Ak je medzi nimi $1$ tak je $a$ delitelom jednotky; ak nie je, tak bud je medzi nimi nula a sme hotovi, alebo sa tam jedna z moznych hodnot nachadza (aspon) dva krat a teda existuju take $k,l$ , $k>l$ , ze plati $a\cdot k=a\cdot l$ avsak potom $a\cdot(k-l)=0$ cize $a$ je delitelom nuly.

vytautas · 17. 08. 2015 22:05

↑ vanok:

ďakujem za nápad a riešenie. lenže ako na druhú časť ? podobný postup nebude fungovať resp. neviem ho použiť.

↑ Brano:

chápem to a ďakujem za riešenie .

vanok · 17. 08. 2015 23:30 — Editoval vanok (18. 08. 2015 09:13)

Tak ta posledna cast dokazu.
Ak d>1, mame $x=dx';n=dn'$ . Potom $n'x=n'dx'=dn'x'=nx'=0 \mod n$ , co znamena, ze $\bar{x}$ je delitel nuly v $\mathbb{Z}_n$ .
Reciprocne delitel nuly nemoze byt delitelom jednotky a tak $d>1$ .

Poznamka. Delitel jednotky, je vlastne inverzibiliny ( regularny) prvok (ktore generuju grupu inverzibilnych prvkov, o ktorej sa da dokazat, ze ma $\varphi (n)$ prvkov, $\varphi$ je Euler-ova funkcia).
Poznamenajme este, ze pojem unité = "jednotka" sa pouziva vo fr., en. namiesto pojmu delitel jednotky.

vytautas · 18. 08. 2015 00:17

↑ vanok:

otázka, prečo práve $n'x$ ? či len preto, že si môžem zvoliť čísla $n'$ a $x$ a vedie to k riešeniu ?

$x=dx';n=dn'$ toto mi napadlo, len som nevedel, čo s tým ďalej .

ďakujem .

vanok · 18. 08. 2015 01:33

↑ vytautas:,
Vies ze $d>1$
A chces ukazat, ze $\bar{x}$ je delitelom nuly.
$n'x$ je dobry kandidat na dokaz prave preto ze $x=dx';n=dn'$ ...
Dobre pokracovanie.

vytautas · 18. 08. 2015 11:02

↑ vanok:

jasné, chápem, ďakujem.

vanok · 18. 08. 2015 22:58 — Editoval vanok (19. 08. 2015 14:47)

↑ vytautas:
Doplnok.
Upresnim este co som napisal tu ↑ vanok: v poznamke.
Iste si teraz schopny dokazat toto
Nech $n \in \mathbb{N}^*, n \ge2$ , $s \in \mathbb{Z}$ , nasledujuce vlasnosti su ekvivalentne
1) $(s,n)=1$
2) $\bar{s}$ je generator grupy $(\mathbb{Z}_n,+)$
3) $\bar{s}\in (\mathbb{Z}_n)^*$ co je grupa intervertibilnych prvkov okruhu $\mathbb{Z}_n$

Tento vysledok je dolezity co sa tyka studia automorfizmov groupy $\mathbb{Z}_n$ co umozni napr. vysetrenie urcitych semi-direktnych sucinov grup.

No vsak to iste prehlbis neskor, ak budes pokracovat vo studiu algebry.