Proofread abstrakt algebra

Mange finner bevis vanskelig. Her er rom for spørsmål vedrørende bevis, og for å dele dine bevis med andre. Vi tenker først og fremst videregående nivå, men det er ingen begrensninger her.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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$
DennisChristensen
Grothendieck
Grothendieck
Innlegg: 826
Registrert: 09/02-2015 23:28
Sted: Oslo

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.
Markus
Fermat
Fermat
Innlegg: 767
Registrert: 20/09-2016 13:48
Sted: NTNU

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$?
DennisChristensen
Grothendieck
Grothendieck
Innlegg: 826
Registrert: 09/02-2015 23:28
Sted: Oslo

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.
Svar