Anki Deck Changes

Note 1: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: D]]~[I)jx9

modified

Before

Front

What is the lower limit for sorting algorithms?

Back

What is the lower limit for sorting algorithms?

\(\Omega(n \log n)\) cannot be improve upon.

After

Front

What is the lower limit for sorting algorithms?

Back

What is the lower limit for sorting algorithms?

\(\Omega(n \log n)\) cannot be improved upon.

Field-by-field Comparison

Field	Before	After
Back	\(\Omega(n \log n)\) cannot be improve upon.	\(\Omega(n \log n)\) cannot be improved upon.

Tags: ETH::1._Semester::A&D::04._Sorting_Algorithms::5._Lower_Bound_for_Sorting

Note 2: ETH::A&D

Deck: ETH::A&D
Note Type: Horvath Classic
GUID: c?99yQ/?;v

modified

Before

Front

How do we create a maxHeap?

Back

How do we create a maxHeap?

Insert the node \(v\) at the next free space in the tree, i.e. first to the left, then right (to conserve the tree structure).

Then we restore the heap condition by reverse-“versickern” the element until it’s restored.

You swap it with it’s parent nodes until the condition is restored.

After

Front

How do we create a maxHeap?

Back

How do we create a maxHeap?

Insert the node \(v\) at the next free space in the tree, i.e. first to the left, then right (to conserve the tree structure).

Then we restore the heap condition by reverse-“versickern” the element until it’s restored.

Swap it with it’s parent nodes until the condition is restored.

Field-by-field Comparison

Field	Before	After
Back	<div>Insert the node \(v\) at the next free space in the tree, i.e. first to the left, then right (to conserve the tree structure).</div><div><br></div> <div>Then we restore the heap condition by reverse-“<b>versickern</b>” the element until it’s restored.</div><div>~~You s~~wap it with it’s parent nodes until the condition is restored.</div>	<div>Insert the node \(v\) at the next free space in the tree, i.e. first to the left, then right (to conserve the tree structure).</div><div><br></div> <div>Then we restore the heap condition by reverse-“<b>versickern</b>” the element until it’s restored.</div><div><br></div><div>Swap it with it’s parent nodes until the condition is restored.</div>

Tags: ETH::1._Semester::A&D::04._Sorting_Algorithms::7._Heapsort

Note 3: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: BMW]cGxx90

modified

Before

Front

Give the formal definition of a greatest common divisor \(d\) of integers \(a\) and \(b\) (not both 0).

Back

Give the formal definition of a greatest common divisor \(d\) of integers \(a\) and \(b\) (not both 0).

After

Front

Give the formal definition of a greatest common divisor \(d\) of integers \(a\) and \(b\) (not both 0).

Back

Give the formal definition of a greatest common divisor \(d\) of integers \(a\) and \(b\) (not both 0).

\[d \mid a \land d \mid b \land \forall c \ ((c \mid a \land c \mid b) \rightarrow c \mid d)\] \(d\) divides both \(a\) and \(b\), AND every common divisor of \(a\) and \(b\) divides \(d\).

Field-by-field Comparison

Field	Before	After
Back	\[d \| a \land d \| b \land \forall c \ ((c \| a \land c \| b) \rightarrow c \| d)\] \(d\) divides both \(a\) and \(b\), AND every common divisor of \(a\) and \(b\) divides \(d\).	\[d \mid a \land d \mid b \land \forall c \ ((c \mid a \land c \mid b) \rightarrow c \mid d)\] \(d\) divides both \(a\) and \(b\), AND every common divisor of \(a\) and \(b\) divides \(d\).

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors

Note 4: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: JwxvW*##[%

modified

Before

Front

Give the formal definition of "\(a\) divides \(b\)" (denoted \(a | b\)).

Back

Give the formal definition of "\(a\) divides \(b\)" (denoted \(a | b\)).

\[a | b \overset{\text{def}}{\Longleftrightarrow} \exists c \in \mathbb{Z} \ b = ac\] \(a\) is a divisor of \(b\), \(b\) is a multiple of \(a\), and \(c\) is the quotient.

After

Front

Give the formal definition of "\(a\) divides \(b\)" (denoted \(a \mid b\)).

Back

Give the formal definition of "\(a\) divides \(b\)" (denoted \(a \mid b\)).

\[a \mid b \overset{\text{def}}{\Longleftrightarrow} \exists c \in \mathbb{Z} \ b = ac\] \(a\) is a divisor of \(b\), \(b\) is a multiple of \(a\), and \(c\) is the quotient.

Field-by-field Comparison

Field	Before	After
Front	Give the formal definition of "\(a\) divides \(b\)" (denoted \(a \| b\)).	Give the formal definition of "\(a\) divides \(b\)" (denoted \(a \mid b\)).
Back	\[a \| b \overset{\text{def}}{\Longleftrightarrow} \exists c \in \mathbb{Z} \ b = ac\] \(a\) is a divisor of \(b\), \(b\) is a multiple of \(a\), and \(c\) is the quotient.	\[a \mid b \overset{\text{def}}{\Longleftrightarrow} \exists c \in \mathbb{Z} \ b = ac\] \(a\) is a divisor of \(b\), \(b\) is a multiple of \(a\), and \(c\) is the quotient.

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::1._Divisors

Note 5: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: Kz0bW-z|V:

modified

Before

Front

What are the trivial divisors that apply to all integers?

Back

What are the trivial divisors that apply to all integers?

Every non-zero integer is a divisor of \(0\)
\(1\) and \(-1\) are divisors of every integer

After

Front

What are the trivial divisors that apply to all integers?

Back

What are the trivial divisors that apply to all integers?

1 and \(-1\) are divisors of every integer.

Note also that every non-zero integer is a divisor of \(0\).

Field-by-field Comparison

Field	Before	After
Back	~~<ul> <li>Every non-zero integer is a divisor of \(0\)</li> <li>\(1\) and \(-1\) are divisors of every integer</li> </ul>~~	1 and \(-1\) are divisors of every integer.<br><br>Note also that every non-zero integer is a divisor of \(0\).

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::1._Divisors

Note 6: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID: dJ#.`ol9+u

modified

Before

Front

What is the ideal \((a, b)\) generated by integers \(a\) and \(b\) and just \(a\)?

Back

What is the ideal \((a, b)\) generated by integers \(a\) and \(b\) and just \(a\)?

\[(a, b) \overset{\text{def}}{=} \{ ua + vb \ | \ u, v \in \mathbb{Z}\}\] and \[(a) \overset{\text{def}}{=} \{ ua \ | \ u \in \mathbb{Z}\}\] The set of all integer linear combinations of \(a\) and \(b\).

After

Front

How are the ideals \((a, b)\) and \((a)\) defined?

Back

How are the ideals \((a, b)\) and \((a)\) defined?

Field-by-field Comparison

Field	Before	After
Front	~~What is~~ the ideal \((a, b)\) ~~generated by integers \(a\) and \(b\) and just \(a\)~~?	How are the ideals \((a, b)\) and \((a)\) defined?

Tags: ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors

Note 7: ETH::DiskMat

Deck: ETH::DiskMat
Note Type: Horvath Classic
GUID:

fIw1$@c


            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::3._Factorization_into_Primes::1._Primes_and_the_Fundamental_Theorem_of_Arithmetic
  
  
    Give the formal definition of a prime number \(p\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::3._Factorization_into_Primes::1._Primes_and_the_Fundamental_Theorem_of_Arithmetic
  
  
    Give the formal definition of a prime number \(p\).
    
    \[p \ \text{prime} \overset{\text{def}}{\Longleftrightarrow} p > 1 \land \forall d \ ((d > 1) \land (d | p) \rightarrow d = p)\]
A prime is greater than 1 and its only positive divisors are 1 and itself.
  






                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::3._Factorization_into_Primes::1._Primes_and_the_Fundamental_Theorem_of_Arithmetic
  
  
    Give the formal definition of a prime number \(p\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::3._Factorization_into_Primes::1._Primes_and_the_Fundamental_Theorem_of_Arithmetic
  
  
    Give the formal definition of a prime number \(p\).
    
    \[p \ \text{prime} \overset{\text{def}}{\Longleftrightarrow} p > 1 \land \forall d \ ((d > 1) \land (d \mid p) \rightarrow d = p)\]
A prime is greater than 1 and its only positive divisors are 1 and itself.
  






                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Back
                            \[p \ \text{prime} \overset{\text{def}}{\Longleftrightarrow} p &gt; 1 \land \forall d \ ((d &gt; 1) \land (d | p) \rightarrow d = p)\]
A prime is greater than 1 and its only positive divisors are 1 and itself.
                            \[p \ \text{prime} \overset{\text{def}}{\Longleftrightarrow} p &gt; 1 \land \forall d \ ((d &gt; 1) \land (d \mid p) \rightarrow d = p)\]
A prime is greater than 1 and its only positive divisors are 1 and itself.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::1._Semester::DiskMat::4._Number_Theory::3._Factorization_into_Primes::1._Primes_and_the_Fundamental_Theorem_of_Arithmetic

Field	Before	After
Back	\[p \ \text{prime} \overset{\text{def}}{\Longleftrightarrow} p > 1 \land \forall d \ ((d > 1) \land (d \| p) \rightarrow d = p)\] A prime is greater than 1 and its only positive divisors are 1 and itself.	\[p \ \text{prime} \overset{\text{def}}{\Longleftrightarrow} p > 1 \land \forall d \ ((d > 1) \land (d \mid p) \rightarrow d = p)\] A prime is greater than 1 and its only positive divisors are 1 and itself.


        
        
            Note 8: ETH::DiskMat
            
                Deck: ETH::DiskMat

                Note Type: Horvath Classic

                GUID: juXB+9W`+)
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    Does \( p | a \land q | a \land \gcd(p, q) = 1 \implies pq | a \) hold?
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    Does \( p | a \land q | a \land \gcd(p, q) = 1 \implies pq | a \) hold?
    
    Yes, but this has to be reproven before using.

The proof technique is important. Replacing a neutral element by something it's equal is often a smart move.


Proof: This is an important result for the exam:

\[p \mid a \land q \mid a \land \gcd(p, q) = 1 \implies pq \mid a\]

Which is the same as saying \(\exists k \in \mathbb{Z}\) such that \(a = pq \cdot k\).




Since \(p \mid a\) and \(q \mid a\), we have:
\[\exists k, k' \in \mathbb{Z} \text{ such that } a = pk \land a = qk'\]

Since \(\gcd(p, q) = 1\), by Bézout's identity:
\[\exists u, v \in \mathbb{Z} \text{ such that } 1 = pu + qv\]

Now we can write:
\[\begin{align}
a &= 1 \cdot a \\
&= a \cdot (pu + qv) \\
&= pua + qva \\
&= pu \cdot qk' + qv \cdot pk \\
&= pq(uk' + vk')
\end{align}\]

Thus \(pq \mid a\). \(\square\)
  






                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    Does \( p \mid a \land q \mid a \land \gcd(p, q) = 1 \implies pq \mid a \) hold?
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    Does \( p \mid a \land q \mid a \land \gcd(p, q) = 1 \implies pq \mid a \) hold?
    
    Yes, but this has to be reproven before using.

The proof technique is important. Replacing a neutral element by something it's equal to often is a smart move.



Proof: This is an important result for the exam:

\[p \mid a \land q \mid a \land \gcd(p, q) = 1 \implies pq \mid a\]

Which is the same as saying \(\exists k \in \mathbb{Z}\) such that \(a = pq \cdot k\).




Since \(p \mid a\) and \(q \mid a\), we have:
\[\exists k, k' \in \mathbb{Z} \text{ such that } a = pk \land a = qk'\]

Since \(\gcd(p, q) = 1\), by Bézout's identity:
\[\exists u, v \in \mathbb{Z} \text{ such that } 1 = pu + qv\]

Now we can write:
\[\begin{align}
a &= 1 \cdot a \\
&= a \cdot (pu + qv) \\
&= pua + qva \\
&= pu \cdot qk' + qv \cdot pk \\
&= pq(uk' + vk')
\end{align}\]

Thus \(pq \mid a\). \(\square\)
  






                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Front
                            Does&nbsp;\( p | a \land q | a \land \gcd(p, q) = 1 \implies pq | a \)&nbsp;hold?
                            Does&nbsp;\( p \mid a \land q \mid a \land \gcd(p, q) = 1 \implies pq \mid a \)&nbsp;hold?
                        
                        
                        
                            Back
                            Yes, but this has to be reproven before using.<br><br>The proof technique is important. Replacing a neutral element by something it's equal is often a smart move.<br>

<b>Proof:</b> This is an important result for the exam:

<div>\[p \mid a \land q \mid a \land \gcd(p, q) = 1 \implies pq \mid a\]</div>

Which is the same as saying \(\exists k \in \mathbb{Z}\) such that \(a = pq \cdot k\).

<br>

Since \(p \mid a\) and \(q \mid a\), we have:
<div>\[\exists k, k' \in \mathbb{Z} \text{ such that } a = pk \land a = qk'\]</div>

Since \(\gcd(p, q) = 1\), by Bézout's identity:
<div>\[\exists u, v \in \mathbb{Z} \text{ such that } 1 = pu + qv\]</div>

Now we can write:
<div>\[\begin{align}
a &amp;= 1 \cdot a \\
&amp;= a \cdot (pu + qv) \\
&amp;= pua + qva \\
&amp;= pu \cdot qk' + qv \cdot pk \\
&amp;= pq(uk' + vk')
\end{align}\]</div>

Thus \(pq \mid a\). \(\square\)
                            Yes, but this has to be reproven before using.<br><br>The proof technique is important. Replacing a neutral element by something it's equal to often is a smart move.<br><br>

<b>Proof:</b> This is an important result for the exam:

<div>\[p \mid a \land q \mid a \land \gcd(p, q) = 1 \implies pq \mid a\]</div>

Which is the same as saying \(\exists k \in \mathbb{Z}\) such that \(a = pq \cdot k\).

<br>

Since \(p \mid a\) and \(q \mid a\), we have:
<div>\[\exists k, k' \in \mathbb{Z} \text{ such that } a = pk \land a = qk'\]</div>

Since \(\gcd(p, q) = 1\), by Bézout's identity:
<div>\[\exists u, v \in \mathbb{Z} \text{ such that } 1 = pu + qv\]</div>

Now we can write:
<div>\[\begin{align}
a &amp;= 1 \cdot a \\
&amp;= a \cdot (pu + qv) \\
&amp;= pua + qva \\
&amp;= pu \cdot qk' + qv \cdot pk \\
&amp;= pq(uk' + vk')
\end{align}\]</div>

Thus \(pq \mid a\). \(\square\)
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
                    
                    
                    
                
            
            
        
        
        
            Note 9: ETH::DiskMat
            
                Deck: ETH::DiskMat

                Note Type: Horvath Cloze

                GUID: kC`G6X,/]b
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    \(\gcd(a, 0) = \) \(|a|\)
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    \(\gcd(a, 0) = \) \(|a|\)
    
    
    
    This is why \(0\) not in \(Z_m^* \) and \(F[x]^*_{m(x)}\)
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    \(\gcd(a, 0) = \) \(|a|\)
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    \(\gcd(a, 0) = \) \(|a|\)
    
    
    
    This is why \(0\) isn't in \(Z_m^* \) and \(F[x]^*_{m(x)}\).
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Extra
                            This is why&nbsp;\(0\)&nbsp;not in&nbsp;\(Z_m^* \)&nbsp;and&nbsp;\(F[x]^*_{m(x)}\)
                            This is why&nbsp;\(0\)&nbsp;isn't in&nbsp;\(Z_m^* \)&nbsp;and&nbsp;\(F[x]^*_{m(x)}\).
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
                    
                    
                    
                
            
            
        
        
        
            Note 10: ETH::DiskMat
            
                Deck: ETH::DiskMat

                Note Type: Horvath Cloze

                GUID: q%i_)pDyvo
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::7._Countable_and_Uncountable_Sets::5._Existence_of_Uncomputable_Functions
  
  
    A prominent example for an uncomputable function is the Halting problem.
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::7._Countable_and_Uncountable_Sets::5._Existence_of_Uncomputable_Functions
  
  
    A prominent example for an uncomputable function is the Halting problem.
    
    
  



                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::7._Countable_and_Uncountable_Sets::5._Existence_of_Uncomputable_Functions
  
  
    A prominent example for an uncomputable function is the Halting problem.
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::7._Countable_and_Uncountable_Sets::5._Existence_of_Uncomputable_Functions
  
  
    A prominent example for an uncomputable function is the Halting problem.
    
    
    
    Given as input a program (encoded as a bit-string or natural number) together with an input (to the program), determine whether the program will eventually stop (function value 1) or loop forever (function value 0) on that input. 

This function is uncomputable. 

This is usually stated as: The Halting problem is undecidable.
  



                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Extra
                            
                            Given as input a program (encoded as a bit-string or natural number) together with an input (to the program), determine whether the program will eventually stop (function value 1) or loop forever (function value 0) on that input. <br><br>This function is uncomputable. <br><br>This is usually stated as: The Halting problem is undecidable.
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::1._Semester::DiskMat::3._Sets,_Relations,_and_Functions::7._Countable_and_Uncountable_Sets::5._Existence_of_Uncomputable_Functions
                    
                    
                    
                
            
            
        
        
        
            Note 11: ETH::DiskMat
            
                Deck: ETH::DiskMat

                Note Type: Horvath Classic

                GUID: r.P@LlU$vR
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::4._Least_Common_Multiples
  
  
    Give the formal definition of the least common multiple \(\text{lcm}(a, b)\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::4._Least_Common_Multiples
  
  
    Give the formal definition of the least common multiple \(\text{lcm}(a, b)\).
    
    \[a | l \land b | l \land \forall m \ ((a | m \land b | m) \rightarrow l | m)\]
\(l\) is a common multiple of \(a\) and \(b\) which divides every common multiple of \(a\) and \(b\).
  






                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::4._Least_Common_Multiples
  
  
    Give the formal definition of the least common multiple \(\text{lcm}(a, b)\).
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::4._Least_Common_Multiples
  
  
    Give the formal definition of the least common multiple \(\text{lcm}(a, b)\).
    
    \[a \mid l \land b \mid l \land \forall m \ ((a \mid m \land b \mid m) \rightarrow l \mid m)\]
\(l\) is a common multiple of \(a\) and \(b\) which divides every common multiple of \(a\) and \(b\).
  






                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Back
                            \[a | l \land b | l \land \forall m \ ((a | m \land b | m) \rightarrow l | m)\]
\(l\) is a common multiple of \(a\) and \(b\) which divides every common multiple of \(a\) and \(b\).
                            \[a \mid l \land b \mid l \land \forall m \ ((a \mid m \land b \mid m) \rightarrow l \mid m)\]
\(l\) is a common multiple of \(a\) and \(b\) which divides every common multiple of \(a\) and \(b\).
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::4._Least_Common_Multiples
                    
                    
                    
                
            
            
        
        
        
            Note 12: ETH::DiskMat
            
                Deck: ETH::DiskMat

                Note Type: Horvath Classic

                GUID: x-z%Jc>A>g
            
            modified
            

            
            
            
                
                    Before
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    How does the GCD change when we subtract a multiple? (Lemma 4.2)
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    How does the GCD change when we subtract a multiple? (Lemma 4.2)
    
    For any integers \(m, n\) and \(q\):
\[\text{gcd}(m, n - qm) = \text{gcd}(m, n)\]
This is the key property for Euclid's algorithm:
\[\text{gcd}(m, R_m(n)) = \text{gcd}(m, n)\]
  






                        
                    
                    
                
                
                    After
                    
                    
                        Front
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    How does the GCD change when we subtract a multiple? (Lemma 4.2)
  



                        
                    
                    
                        Back
                        
                            
  ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors
  
  
    How does the GCD change when we subtract a multiple? (Lemma 4.2)
    
    Not at all.

For any integers \(m, n\) and \(q\):
\[\text{gcd}(m, n - qm) = \text{gcd}(m, n)\]
This is the key property for Euclid's algorithm:
\[\text{gcd}(m, R_m(n)) = \text{gcd}(m, n)\]
  






                        
                    
                    
                
            
            

            
            
            
                Field-by-field Comparison
                
                    
                        
                            Field
                            Before
                            After
                        
                    
                    
                        
                        
                            Back
                            For any integers \(m, n\) and \(q\):
\[\text{gcd}(m, n - qm) = \text{gcd}(m, n)\]
This is the key property for Euclid's algorithm:
\[\text{gcd}(m, R_m(n)) = \text{gcd}(m, n)\]
                            Not at all.<br><br>For any integers \(m, n\) and \(q\):
\[\text{gcd}(m, n - qm) = \text{gcd}(m, n)\]
This is the key property for Euclid's algorithm:
\[\text{gcd}(m, R_m(n)) = \text{gcd}(m, n)\]
                        
                        
                    
                
            
            

            
            
            
                Tags:
                
                    
                    
                    
                    
                    ETH::1._Semester::DiskMat::4._Number_Theory::2._Divisors_and_Division::3._Greatest_Common_Divisors

Field	Before	After
Front	Does \( p \| a \land q \| a \land \gcd(p, q) = 1 \implies pq \| a \) hold?	Does \( p \mid a \land q \mid a \land \gcd(p, q) = 1 \implies pq \mid a \) hold?
Back	Yes, but this has to be reproven before using.<br><br>The proof technique is important. Replacing a neutral element by something it's equal is often a smart move.<br> <b>Proof:</b> This is an important result for the exam: <div>\[p \mid a \land q \mid a \land \gcd(p, q) = 1 \implies pq \mid a\]</div> Which is the same as saying \(\exists k \in \mathbb{Z}\) such that \(a = pq \cdot k\). <br> Since \(p \mid a\) and \(q \mid a\), we have: <div>\[\exists k, k' \in \mathbb{Z} \text{ such that } a = pk \land a = qk'\]</div> Since \(\gcd(p, q) = 1\), by Bézout's identity: <div>\[\exists u, v \in \mathbb{Z} \text{ such that } 1 = pu + qv\]</div> Now we can write: <div>\[\begin{align} a &= 1 \cdot a \\ &= a \cdot (pu + qv) \\ &= pua + qva \\ &= pu \cdot qk' + qv \cdot pk \\ &= pq(uk' + vk') \end{align}\]</div> Thus \(pq \mid a\). \(\square\)	Yes, but this has to be reproven before using.<br><br>The proof technique is important. Replacing a neutral element by something it's equal to often is a smart move.<br><br> <b>Proof:</b> This is an important result for the exam: <div>\[p \mid a \land q \mid a \land \gcd(p, q) = 1 \implies pq \mid a\]</div> Which is the same as saying \(\exists k \in \mathbb{Z}\) such that \(a = pq \cdot k\). <br> Since \(p \mid a\) and \(q \mid a\), we have: <div>\[\exists k, k' \in \mathbb{Z} \text{ such that } a = pk \land a = qk'\]</div> Since \(\gcd(p, q) = 1\), by Bézout's identity: <div>\[\exists u, v \in \mathbb{Z} \text{ such that } 1 = pu + qv\]</div> Now we can write: <div>\[\begin{align} a &= 1 \cdot a \\ &= a \cdot (pu + qv) \\ &= pua + qva \\ &= pu \cdot qk' + qv \cdot pk \\ &= pq(uk' + vk') \end{align}\]</div> Thus \(pq \mid a\). \(\square\)