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.

Proofread abstrakt algebra

Innlegg Markus » 21/01-2019 21:34

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$
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Proofread abstrakt algebra

Innlegg DennisChristensen » 22/01-2019 09:18

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.
DennisChristensen offline
Fermat
Fermat
Innlegg: 770
Registrert: 09/02-2015 23:28
Bosted: Oslo

Re: Proofread abstrakt algebra

Innlegg Markus » 22/01-2019 18:18

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$?
Markus offline
Fermat
Fermat
Innlegg: 760
Registrert: 20/09-2016 12:48
Bosted: NTNU

Re: Proofread abstrakt algebra

Innlegg DennisChristensen » 23/01-2019 08:18

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.
DennisChristensen offline
Fermat
Fermat
Innlegg: 770
Registrert: 09/02-2015 23:28
Bosted: Oslo

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 2 gjester