Side 1 av 1

Proofread abstrakt algebra

Lagt inn: 21/01-2019 21:34
av Markus
Skulle gjerne hatt en proofread av det følgende, da jeg gjorde det annerledes enn LF og er en smule usikker.
Vis at et element $m \in \mathbb{Z}_n$ er en generator hvis og bare hvis $\gcd(m, n) = 1$.
Bevis:
$(\Longrightarrow)$ Hvis $m$ er et genererende element for gruppa så er vi gitt at $\{km \pmod{n}: k\in \mathbb{Z} \} = \mathbb{Z}_n$. Dvs. at for konstanter $k_i \in \mathbb{Z}$, må vi ha at $$\begin{alignat*}{2}
k_0m &\equiv 0 \pmod{n} \\
k_1m &\equiv 1 \pmod{n} \\
&\vdots \\
k_{n-1}m &\equiv n-1 \pmod{n}
\end{alignat*}$$ Alle disse er på formen $k_im \equiv i \pmod{n}$ som er ekvivalent med $k_im - yn = i$, som er løsbar hvis og bare hvis $\gcd(m,n) \mid i$. Siden $i=0,1,2,\dots,n-1$, må vi ha $\gcd(m,n)=1$ siden $1$ er det eneste tallet som deler alle disse $i$.

$(\Longleftarrow)$ Av Bézouts lemma $\gcd(m,n)=1 \implies \exists x,y \in \mathbb{Z}: mx+ny = 1 \Longleftrightarrow mx \equiv 1 \pmod{n}$ Gang den siste kongruensen med $k$ for $k=0,1,\dots,n-1$ og da fås at $m(xk) \equiv k \pmod{n}$ og $xk \in \mathbb{Z}$ så $m$ genererer $\mathbb{Z}_n$. $ \blacksquare$

Re: Proofread abstrakt algebra

Lagt inn: 22/01-2019 09:18
av DennisChristensen
Markus skrev:Skulle gjerne hatt en proofread av det følgende, da jeg gjorde det annerledes enn LF og er en smule usikker.
Vis at et element $m \in \mathbb{Z}_n$ er en generator hvis og bare hvis $\gcd(m, n) = 1$.
Bevis:
$(\Longrightarrow)$ Hvis $m$ er et genererende element for gruppa så er vi gitt at $\{km \pmod{n}: k\in \mathbb{Z} \} = \mathbb{Z}_n$. Dvs. at for konstanter $k_i \in \mathbb{Z}$, må vi ha at $$\begin{alignat*}{2}
k_0m &\equiv 0 \pmod{n} \\
k_1m &\equiv 1 \pmod{n} \\
&\vdots \\
k_{n-1}m &\equiv n-1 \pmod{n}
\end{alignat*}$$ Alle disse er på formen $k_im \equiv i \pmod{n}$ som er ekvivalent med $k_im - yn = i$, som er løsbar hvis og bare hvis $\gcd(m,n) \mid i$. Siden $i=0,1,2,\dots,n-1$, må vi ha $\gcd(m,n)=1$ siden $1$ er det eneste tallet som deler alle disse $i$.

$(\Longleftarrow)$ Av Bézouts lemma $\gcd(m,n)=1 \implies \exists x,y \in \mathbb{Z}: mx+ny = 1 \Longleftrightarrow mx \equiv 1 \pmod{n}$ Gang den siste kongruensen med $k$ for $k=0,1,\dots,n-1$ og da fås at $m(xk) \equiv k \pmod{n}$ og $xk \in \mathbb{Z}$ så $m$ genererer $\mathbb{Z}_n$. $ \blacksquare$
Ser riktig ut. Du kan riktignok forenkle $(\implies)$ via reductio ad absurdum: Anta at $\mathbb{Z}_n = \langle m\rangle$ men at $\gcd(m,n)\neq 1$. Ettersom $m$ genererer $\mathbb{Z}_n$ vet vi at det finnes $x, y\in\mathbb{Z}$ slik at $mx + ny = 1$. Om vi reduserer denne likningen mod $\gcd(m,n)$ får vi en selvmotsigelse.

Re: Proofread abstrakt algebra

Lagt inn: 22/01-2019 18:18
av Markus
Takker Dennis! Bare slik at jeg har forstått rett så blir selvmotsigelsen at $1 \equiv 0\pmod{\gcd(m,n)} \implies \gcd(m,n)=1$?

Re: Proofread abstrakt algebra

Lagt inn: 23/01-2019 08:18
av DennisChristensen
Markus skrev:Takker Dennis! Bare slik at jeg har forstått rett så blir selvmotsigelsen at $1 \equiv 0\pmod{\gcd(m,n)} \implies \gcd(m,n)=1$?
Vi kan tenke på selvmotsigelsen på to forskjellige måter:
(1) Vi har antatt at $\gcd(m,n) = g > 1$, men kongruensen vi ender opp med sier at $1\equiv 0 \mod g$, hvilket ikke går an.
(2) Likningen $mx + ny = 1$ må også holde som kongruens når vi reduserer mod $g = \gcd(m,n)$. Dette tvinger $\gcd(m,n) = 1$. en selvmotsigelse.