Anki Deck Changes

Note 1: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: G3,dI)){d{

modified

Before

Front

Which elements generate \(\mathbb{Z}_n\)? How can this be proven?

Back

Which elements generate \(\mathbb{Z}_n\)? How can this be proven?

\(\mathbb{Z}_n\) is generated by all \(a \in \mathbb{Z}_n\) for which \(\gcd(a, n) = 1\) (all elements coprime to \(n\)).

Proof:

\(a\) generator \(\implies\)\(\gcd(a, n) = 1\)
\(\mathbb{Z}_n = \langle a \rangle\)
\(\implies\)\(1 \in \langle a \rangle\)
\(\implies\)\(a^u = ua \equiv_n 1\) for some \(u\)
\(\implies\)\(\gcd(a, n) = 1\) (\(\gcd\) must divide both \(au-qn\) and 1).

\(\gcd(a, n) = 1 \implies\)\(a\) generator
\(\gcd(a, n) = 1\)
\(\implies\)\(ua + un = 1\) for some \(u, n\) (Bézout)
\(\implies\)\(ua = a^u \equiv_n 1\)
\(\implies\)for every element \(b\), \(\exists c\) s.t. \(b = c \cdot u \cdot a = (a^u)^c = a^{u \cdot c}\)

After

Front

Which elements generate \(\mathbb{Z}_n\)? How can this be proven?

Back

Which elements generate \(\mathbb{Z}_n\)? How can this be proven?

\(\mathbb{Z}_n\) is generated by all \(a \in \mathbb{Z}_n\) for which \(\gcd(a, n) = 1\) (all elements coprime to \(n\)).

Proof:

\(a\) generator \(\implies\)\(\gcd(a, n) = 1\)
\(\mathbb{Z}_n = \langle a \rangle\)
\(\implies\)\(1 \in \langle a \rangle\)
\(\implies\)\(a^u = au \equiv_n 1\) for some \(u\)
\(\implies\)\(\gcd(a, n) = 1\) (\(\gcd\) must divide both \(au-qn\) and 1).

\(\gcd(a, n) = 1 \implies\)\(a\) generator
\(\gcd(a, n) = 1\)
\(\implies\)\(ua + un = 1\) for some \(u, n\) (Bézout)
\(\implies\)\(ua = a^u \equiv_n 1\)
\(\implies\)for every element \(b\), \(\exists c\) s.t. \(b = c \cdot u \cdot a = (a^u)^c = a^{u \cdot c}\)

Field-by-field Comparison

Field	Before	After
Back	<p>\(\mathbb{Z}_n\) is generated by <strong>all \(a \in \mathbb{Z}_n\) for which \(\gcd(a, n) = 1\)</strong> (all elements coprime to \(n\)).</p> <p><strong>Proof:</strong></p><p>\(a\) generator \(\implies\)\(\gcd(a, n) = 1\)<br>\(\mathbb{Z}_n = \langle a \rangle\)<br>\(\implies\)\(1 \in \langle a \rangle\)<br>\(\implies\)\(a^u = ua \equiv_n 1\) for some \(u\)<br>\(\implies\)\(\gcd(a, n) = 1\) (\(\gcd\) must divide both \(au-qn\) and 1).</p>\(\gcd(a, n) = 1 \implies\)\(a\) generator<br>\(\gcd(a, n) = 1\)<br>\(\implies\)\(ua + un = 1\) for some \(u, n\) (Bézout)<br>\(\implies\)\(ua = a^u \equiv_n 1\)<br>\(\implies\)for every element \(b\), \(\exists c\) s.t. \(b = c \cdot u \cdot a = (a^u)^c = a^{u \cdot c}\)	<p>\(\mathbb{Z}_n\) is generated by <strong>all \(a \in \mathbb{Z}_n\) for which \(\gcd(a, n) = 1\)</strong> (all elements coprime to \(n\)).</p> <p><strong>Proof:</strong></p><p>\(a\) generator \(\implies\)\(\gcd(a, n) = 1\)<br>\(\mathbb{Z}_n = \langle a \rangle\)<br>\(\implies\)\(1 \in \langle a \rangle\)<br>\(\implies\)\(a^u = au \equiv_n 1\) for some \(u\)<br>\(\implies\)\(\gcd(a, n) = 1\) (\(\gcd\) must divide both \(au-qn\) and 1).</p>\(\gcd(a, n) = 1 \implies\)\(a\) generator<br>\(\gcd(a, n) = 1\)<br>\(\implies\)\(ua + un = 1\) for some \(u, n\) (Bézout)<br>\(\implies\)\(ua = a^u \equiv_n 1\)<br>\(\implies\)for every element \(b\), \(\exists c\) s.t. \(b = c \cdot u \cdot a = (a^u)^c = a^{u \cdot c}\)

Tags: ETH::1._Semester::DiskMat::5._Algebra::3._The_Structure_of_Groups::5._Cyclic_Groups

Note 2: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: LFnfauD_]7

modified

Before

Front

A group \(G = \langle g \rangle\) generated by an element \(g \in G\) is called cyclic, and \(g\) is called a generator of \(G\).

Back

A group \(G = \langle g \rangle\) generated by an element \(g \in G\) is called cyclic, and \(g\) is called a generator of \(G\).

Examples:
\(\langle \mathbb{Z}_n;\oplus\rangle\) (cyclic for every \(n\), 1 is a generator)
\(\langle\mathbb{Z}_n; +,-,0\rangle\)(infinite cyclic group with generators 1 and -1)

After

Front

A group \(G = \langle g \rangle\) generated by an element \(g \in G\) is called cyclic, and \(g\) is called a generator of \(G\).

Back

A group \(G = \langle g \rangle\) generated by an element \(g \in G\) is called cyclic, and \(g\) is called a generator of \(G\).

Examples:
\(\langle \mathbb{Z}_n;\oplus\rangle\) (cyclic for every \(n\), 1 is a generator)
\(\langle\mathbb{Z}_n; +,-,0\rangle\) (infinite cyclic group with generators 1 and -1)

Field-by-field Comparison

Field	Before	After
Extra	Examples:<br>\(\langle \mathbb{Z}_n;\oplus\rangle\) (cyclic for every \(n\), 1 is a generator)<br>\(\langle\mathbb{Z}_n; +,-,0\rangle\)(infinite cyclic group with generators 1 and -1)	Examples:<br>\(\langle \mathbb{Z}_n;\oplus\rangle\) (cyclic for every \(n\), 1 is a generator)<br>\(\langle\mathbb{Z}_n; +,-,0\rangle\) (infinite cyclic group with generators 1 and -1)

Tags: ETH::1._Semester::DiskMat::5._Algebra::3._The_Structure_of_Groups::5._Cyclic_Groups

Note 3: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: Wr5Xy7Rn3U

modified

Before

Front

\(F\) of the form \(\forall x G\) or \(\exists x G\) semantics:

\(\mathcal{A}(\forall x G) = 1\) if {{c1::\(\mathcal{A}_{[x \rightarrow u]}(G) = 1\) for all \(u\) in \(U\)}}
\(\mathcal{A}(\exists x G) = 1\) if {{c2::\(\mathcal{A}_{[x \rightarrow u]}(G) = 1\) for some \(u\) in \(U\)}}

Back

\(F\) of the form \(\forall x G\) or \(\exists x G\) semantics:

\(\mathcal{A}(\forall x G) = 1\) if {{c1::\(\mathcal{A}_{[x \rightarrow u]}(G) = 1\) for all \(u\) in \(U\)}}
\(\mathcal{A}(\exists x G) = 1\) if {{c2::\(\mathcal{A}_{[x \rightarrow u]}(G) = 1\) for some \(u\) in \(U\)}}

\(\mathcal{A}_{[x \rightarrow u]}\)}} for \(u\) in \(U\) is the same structure as \(\mathcal{A}\), except that \(\xi(x)\) is overwritten by \(u\): \(\xi(x) = u\).

After

Front

\(F\) of the form \(\forall x G\) or \(\exists x G\) semantics:

\(\mathcal{A}(\forall x G) = 1\) if {{c1::\(\mathcal{A}_{[x \rightarrow u]}(G) = 1\) for all \(u\) in \(U\)}}
\(\mathcal{A}(\exists x G) = 1\) if {{c2::\(\mathcal{A}_{[x \rightarrow u]}(G) = 1\) for some \(u\) in \(U\)}}

Back

\(F\) of the form \(\forall x G\) or \(\exists x G\) semantics:

\(\mathcal{A}(\forall x G) = 1\) if {{c1::\(\mathcal{A}_{[x \rightarrow u]}(G) = 1\) for all \(u\) in \(U\)}}
\(\mathcal{A}(\exists x G) = 1\) if {{c2::\(\mathcal{A}_{[x \rightarrow u]}(G) = 1\) for some \(u\) in \(U\)}}

\(\mathcal{A}_{[x \rightarrow u]}\) for \(u\) in \(U\) is the same structure as \(\mathcal{A}\), except that \(\xi(x)\) is overwritten by \(u\): \(\xi(x) = u\).

Field-by-field Comparison

Field	Before	After
Extra	<div>\(\mathcal{A}_{[x \rightarrow u]}\)}} for \(u\) in \(U\) is the same structure as \(\mathcal{A}\), except that \(\xi(x)\) is overwritten by \(u\): \(\xi(x) = u\).</div>	<div>\(\mathcal{A}_{[x \rightarrow u]}\) for \(u\) in \(U\) is the same structure as \(\mathcal{A}\), except that \(\xi(x)\) is overwritten by \(u\): \(\xi(x) = u\).</div>

Tags: ETH::1._Semester::DiskMat::6._Logic::6._Predicate_Logic_(First-order_Logic)::3._Semantics

Note 4: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Cloze
GUID: oKjV}w*z+.

modified

Before

Front

In a finite group the function \(x \rightarrow x^e\) is a bijection if \(e\) coprime to \(|G|\).

For \(x^e = y\), the inverse of \(y\) is the unique \(e\)th root \(x = y^d\).

Back

In a finite group the function \(x \rightarrow x^e\) is a bijection if \(e\) coprime to \(|G|\).

For \(x^e = y\), the inverse of \(y\) is the unique \(e\)th root \(x = y^d\).

After

Front

In a finite group the function \(x \rightarrow x^e\) is a bijection if \(e\) coprime to \(|G|\).

For \(x^e = y\), the inverse of \(y\) is {{c3:: the unique \(e\)-th root \(x = y^d\), with \(de \equiv_{|G|} 1\)}}.

Back

In a finite group the function \(x \rightarrow x^e\) is a bijection if \(e\) coprime to \(|G|\).

For \(x^e = y\), the inverse of \(y\) is {{c3:: the unique \(e\)-th root \(x = y^d\), with \(de \equiv_{|G|} 1\)}}.

Proof:

We have \(ed = k \cdot |G| + 1\) for some \(k\). Thus, for any \(x \in G\) we have\[(x^e)^d = x^{ed} = x^{k \cdot |G| + 1} = \underbrace{(x^{|G|})^k}_{=1} \cdot x = x\]which means that the function \(y \mapsto y^d\) is the inverse function of the function \(x \mapsto x^e\) (which is hence a bijection). The under-braced term is equal to 1 because the order of \(x\) must divide the order of \(G\) (Lagrange).

Field-by-field Comparison

Field	Before	After
Text	In a finite group the function \(x \rightarrow x^e\) is {{c1:: a bijection}} if {{c2::~~ ~~\(e\) coprime to \(\|G\|\)}}.<br><br>For \(x^e = y\), the inverse of \(y\) is {{c3:: the <b>unique</b> \(e\)th root \(x = y^d\)}}.	In a finite group the function \(x \rightarrow x^e\) is {{c1:: a bijection}} if {{c2::\(e\) coprime to \(\|G\|\)}}.<br><br>For \(x^e = y\), the inverse of \(y\) is {{c3:: the <b>unique</b> \(e\)-th root \(x = y^d\), with \(de \equiv_{\|G\|} 1\)}}.
Extra		<b>Proof:<br></b><div>We have \(ed = k \cdot \|G\| + 1\) for some \(k\). Thus, for any \(x \in G\) we have\[(x^e)^d = x^{ed} = x^{k \cdot \|G\| + 1} = \underbrace{(x^{\|G\|})^k}_{=1} \cdot x = x\]which means that the function \(y \mapsto y^d\) is the inverse function of the function \(x \mapsto x^e\) (which is hence a bijection). The under-braced term is equal to 1 because the order of \(x\) must divide the order of \(G\) (Lagrange).</div><div><br></div><br><div><br></div><br><div><br></div>

Tags: ETH::1._Semester::DiskMat::5._Algebra::4._Application:_RSA_Public-Key_Encryption::1._eth_Roots