Table of Contents

1 Abstract Algebra Topic Summary

Abstract Algebra TB: An Introduction to abstract algebra_ by Nicodemi, Sutherland and Towsley

Author: Ryan G; 17805315

Alternative/Accessible Textbooks:

2 1) Induction and Divisibility

Week 1 Material, Due Thur. 7 March TB: [1.1], [1.2], [2.1], [2.2]

2.1 Numbers and Sets

This is mostly reproduced in the Topic 1 section on Sets in the Analysis Notes

2.1.1 Set Orders

The Natural Numbers have an intuitive order:

\(0<1<2<3<4 \dots\)

As to the Real Numbers:

\( -99 < -1 < 0 < e < \pi < e^{4\pi} < \frac{999}{2} \)

However, the Field of Complex Numbers has no intuitive order because the numbers do not exist on a line but on a plane.

On a line mathematical operations can be seen as a symmetrical transformation of that line, but on a plane order becomes somewhat arbitrary. *3Blue1Brown has a great video on this.

2.1.2 Mathematical Induction

Refer to these notes in Analysis, they overlap entirely.

2.2 Arithmetic and Divisibility

Whats important here, is the division Algorithm, which states:

If an integer is divided by some \(b \in \mathbb{N}\) , there will always be some remainder \(r \enspace : \enspace 0

This is a pretty straightforward proposition, but it underlies all later proofs of abstract algebra.

2.2.1 Properties of the Integers

Investigating the properties of number sets will be important later for considering the algebraic structure of sets, but for now, consider the 6 properties of the integers:

  1. Associative under addition and multiplication
    1. \(\forall (a,b,c \in \mathbb{Z}), a + (b+c) = (a+b) + c\)
    2. \(\forall (a,b,c \in \mathbb{Z}), a \cdot (b\cdot c) = (a\cdot b) + c\)
  2. Commutative under multiplication and addition
    1. \(\forall (a,b \in \mathbb{Z}), a + b = b + a\)
    2. \(\forall (a,b \in \mathbb{Z}), a \cdot b = b \cdot a\)
  3. There always exists a unique additive Identity, \(0\)
    1. \(\forall x \in \mathbb{z}, !\exists 0 : 0+x=x\)
  4. There always exists a unique multiplicative identity, \(1\)
    1. \(\forall x \in \mathbb{z}, !\exists 1 : 1\cdot x=x\)
  5. Every integer has an additive inverse\
    1. \(\forall x \in \mathbb{Z}, \exists (-x) : x + (-x) = 0\)
  6. Addition and multiplication satisfy the distributive law
    1. \(\forall (x,y,z \in \mathbb{Z}), (x\cdot y) + (x\cdot z)\)

2.2.2 Divisibility Definition

Let \(a\) and \(b\) be integers with \(b \neq 0\):

\[(a,b) \in \mathbb{Z} : b \neq 0\]

it is said that \(b\) divides \(a\) (written \(b|a\)), if there is some integer \(q\) such that \(\enspace a = b\cdot q\):

\[b|a \iff \exists q \in \mathbb{Z} : a = b\cdot q\]

This is the same as saying:

  • \(a\) is divisible by \(b\)
  • \(a\) is a multiple of \(b\)

2.2.3 Divisibility Properties

  1. \(a|b \enspace \wedge \enspace b|c \implies a|c\)
  2. \(a|b \enspace \wedge \enspace a|c \implies a|(mb + nc)\)

####

  1. Proof

    Observe that:
    \(a|b \implies b = k\cdot a, \enspace \exists t \in \mathbb{Z} \quad \text{and} \quad b|c \implies c = s \cdot b, \enspace \exists s \in \mathbb{z}\)

2.2.4 Division Algorithm

The definition of the algorithm:

Let \(a\) and \(b\) bey any integers with \(b >0\).

There are unique integers \(q\) and \(r\) such that \(a = qb +r\), where \(0 \leq r

\[!\exists (q,r \in \mathbb{Z}, \enspace q \neq r) : (a = qb +r) \wedge (0 \leq r < b)\]

2.3 Greatest Common Divisors and Euclids Algorithm

2.3.1 Definition of the GCD

Suppose \(a\) and \(b\) are nonzero integers, the greatest common divisor of \(a\) and \(b\) is the largest integer that divides both of them and is denoted:

\(gcd(a,b)\)

Observe some properties of the gcd

  1. \(\gcd(0,0)\) is undefined because it would be
  2. \(\gcd(a,0) = a\) ; because any number divides and the largest number that divides is itself
    1. unless \(a=0\) in which case it would be like (1) above.
  3. \(\gcd(b, qb) = b\) ; because the \(b\) divides both terms and is the largest possible divisor of\(b\)

2.3.2 Theorem 1

The \(\gcd(a,b)\) is the smallest positive integer that can be expressed in the form:

\[ma + nb : (m,n \in \mathbb{Z})\]

  1. Corollary

    Observe further, that for \(x \in \mathbb{Z}\) , thwse two statements are wholly equivalent:

    1. \(x = ma+nb\)
    2. $gcd(a,b)x

    i.e. \(x = ma + nb \iff \gcd(a,b) | x\)

2.3.3 Relatively Prime

  1. Definition

    Suppose \(a\) and \(b\) are non-zero integers, they are relatively prime (i.e. coprime) if \(\gcd(a,b)=1\)

  2. Proposition; Relatively Prime by GCD

    Suppose \(a\) and \(b\) are non-zero integers, and let \(\gcd(a,b) =d\)

    Then \(\frac{a}{d}\) and \(\frac{b}{d}\) are relatively prime.

2.3.4 Euclid's Lemma (P.18)

  1. Definition

    Suppose \(a, b, c\) are integers such that \(a\) and \(b\) are coprime.

    if \(b\cdot c\) is a multiple of \(a\),

    Then \(c\) must be a multiple of \(a\)

    (because \(p\) was prime)

2.3.5 Theorem; GCD becomes Remainder and Factor

Suppose \((a,b,q,r)\) are all integers, such tat:

\[a = qb +r\]

Then,

\[\gcd(a,b) =\gcd(b,r)\]

2.3.6 Euclid's Algorithm (i.e. Calculating GCD's)

Euclid's Algorithm allows for a method to find the Greatest Common Denominator:

For two positive natural numbers, \(a,b\) such that \(a>b\):

  1. write in the form of \(a=qb+r\), where \((q,r\in \mathbb{Z})\) with \(0
  2. If \(r=0\), then \(a=q\cdot b\) and hence \(\gcd(a,b) = \gcd(b,r)\)
  3. if \(r\neq\) 0, then \(\gcd(a,b) = \gcd(b,r)\)
    1. Now repeat from step 1

2.3.7 Lowest Common Multiples

For two integers \((a,b) \in \mathbb{Z}\), the Lowest Common Multiple, is the smallest integer that is a multiple of both \(a\) and \(b\)

The \(LCM\) is a number that is the smallest possible multiple of other numbers

  1. Finding the LCM

    In order to find the LCM use the formula:

    \[\text{lcm} (a,b) = \frac{a\cdot b}{\gcd(a,b)}\]

3 (2) Prime Numbers

3.1 Definitions

Prime and composite numbers are any numbers that satisfy the following conditions:

Prime Numbers Composite Numbers
   
2. p  
3. x p (x =1 x=p)  
2. c  

Observe that \(1\) is neither a prime nor a composite number, this is important for later

3.2 Infinite Primes

3.2.1 Summary

There are infinite prime numbers

3.2.2 Proof

Suppose;

\[S = \{p_1, p_2, p_3, \dots p_n\}\]

is the set of the first \(n\) prime numbers,

let:

\[q = (p_1 \cdot p_2 \cdot p_3 \cdot \dots p_n)\]

Observe that \(q\) would not be a multiple of any value \(p \in S\)

Although this does not mean \(q\) is necessarily prime (primes can be much more difficult to generate), \(q\) is possible a composite of primes not in \(S\), but regardless, \(q\) is not divisible by any \(p \in S\)

Thus \(S\) cannot contain all prime values.

Observe likewise, no set \(S\) could be constructed such that it contained all the primes

or atleast no finite set \(S\)

\(\therefore\) , the set of all Prime numbers must not be finite (i.e. there are infinite primes).

3.3 Primes of Multiples

If a prime number divides a composite, it must divide one of
the factors of that composite number

3.3.1 Summary

\(p\) is a prime number if and only if:

\[\forall (a,b \in \mathbb{z}), \enspace p|a\cdot b \implies p|a \enspace \vee \enspace p|b\]

3.3.2 Proof

Suppose \(p\) is a prime number:

\[\enspace p | (a \cdot b)\]

Either \(p\) divides \(a\) or it does not:

\(p\mid a\) \(p\nmid a\)
\(p\mid a\) , thus<br />$p\mid ab \implies p a ∨ p b \quad \blacksquare$ \(p \nmid a\), thus:<br /><br />\(gcd(a,p) = 1\) <br /><br /> because $p ab$ and \(\gcd(a,p) = 1\)<br /><br />Then by Euclid's Lemma:<br />$p b$<br /><br />thus, <br />$p ab \implies p a ∨ p b \quad \blacksquare$

Thus:

\[p|ab \implies p|a \vee p|b\]

3.4 Prime Factors

3.4.1 Summary

Suppose \(p\) is prime and \(p\) divides some number \(a_1 \cdot a_2 \cdot a_3 \dots a_n\)

Then \(p\) divides \(a_k \enspace : \enspace 1 \leq k \leq n\)

Moreover, if \(a_k\) is prime, then \(p=a_k\)

3.5 The Fundamental Theorem of Arithmetic

3.5.1 Summary

For any integer \(n\):

  1. \(\enspace n = p^{k_1}_1\cdot p^{k_2}_2 \cdot p^{k_3}_3 \dots p^{k_m}_m\)
  2. The above factorisation of \(n\) is unique to the value of \(n\)

This proof is provided on p. 28 of the TB.

3.5.2 Corollary, Rational Numbers

Every rational number can be expressed in a lowes form of relatively prime integers.

  1. Summary

    Every rational number can be expressed uniquely as some fraction of integers:

    \[\forall r \in \mathbb{Q}, \enspace !\exists m,n \in \mathbb{Z} : r = \frac{m}{n}\]

    1. \(\sqrt{2}\) is not rational

      A rational number can be expressed as a ratio, \(\sqrt{2}\) cannot be, the proof is in the Analysis Textbookat [2.1.4].

3.6 Theorems of Euler and Fermat (ch. [1.7])

3.6.1 Euler-Phi Function

The Euler-Phi Function counts the number of integers relatively prime to \(n\) that are less than \(n\),

  1. Definition

    for \(n \geq 1\);

    \(\phi(n)\) is the number of positive integers less than or equal to \(n\) that are relatively prime to \(n\)

    e.g. \(2, 3, 7\) are relatively prime to \(10\), thus \(\phi(10) = 3\)

3.6.2 Powers of Euler-Phi Function

  1. Summary

    if \(p\) is prime and \(i \geq 1\),

    \[\begin{aligned} \phi(p^i) &= p^i - p^{i-1} \\ &=p^i(1-frac{1}{p})\end{aligned}\]

  2. Proof

    All the numbers between \(1\) and \(p-1\) are relatively prime to p, thus \(\phi(p)=p-1\).

    All integers less than \(p^i\) (for \(i\geq 1\)) are relatively prime to \(p^i\) except for multiples of \(p\).
    i.e. all values less than \(p^i\) are relatively prime except for \(1p,2p,3p \dots p^(i-1) p\).

    So there are exactly \(p^{i-1}\) multiples of \(p\) that are multiples and hence not relatively prime.

    Thus there is a total of \(p^i-p^{i-1}\) numbers between \(1\) and \(p^i\) that are relatively prime to \(p^i\).

3.6.3 Euler-Phi Function is Multiplicative

  1. Summary

    For positive relatively prime integers \(m\) and \(n\):

    \[\gcd(m, n) = 1 \implies \phi(m \cdot n) = \phi(m) \cdot \phi(n)\]

  2. Proof

    Refer to p. 44 of the TB.

  3. Corollary

    for primes \(p, e \in \mathbb{N}\),

    Given some \(n\) value:

    \[n = p^{e_1}_1 \times p^{e_2}_2 \times p^{e_3}_3 \times p^{e_r}_r\]

    Then the Euler Phi function is:

    \[\phi(n) = p^{e_1-1}_1 \cdot (p_1-1) \times p^{e_2-1}_2 \cdot (p_2-1) \times p^{e_3-1}_3 \cdot (p_3-1) \dots p^{e_r-1}_r \cdot (p_r-1)\]

    Further it follows:

    \[\phi(n) = n \times \frac{p_1 -1}{p_1} \times \frac{p_2 -1}{p_2} \times \frac{p_3 -1}{p_3} \times \frac{p_r -1}{p_r}\]

    I've merely interchanged \(\cdot\) and \(\times\) here
    for want of illustration, there is no significant
    meaning right here whatsoever (where as maybe
    later down \(\cdot\) may refer to more abstract
    ideas of multiplication but it's pretty lose as it stands)

3.6.4 Eulers Theorem

  1. Summary

    For relatively prime integers \(a\) and \(m \geq 1\):

    \[m | (a^{\phi(m)} - 1)\]

  2. Proof

    The proof is on page 45 of the TB.

  3. Fermats Little Theorem

    The special case of Euler's Theorem, men \(m\) is prime, in known as Fermat's Little Theorem.

    1. Summary

      For some prime \(p\) and integer \(a\):

      \[p \mid (a^p -a)\]

    2. Proof

      It must be such that \(p\) divides \(a\) or \(p\) does not divide \(a\) , hence:

      \(p \mid a\) \(p \nmid a\)
      if \(p \mid a\) <br />\(\implies p \mid a^n, \enspace \exists n \in \mathbb{N}\)<br /> \(\implies p \mid a^{p-1}\) <br /> \(\implies p \mid (a^p -a)\) if \(p\nmid a\)<br ><br />Then \(p\) and \(a\) are relatively prime, thus, /Eulers Theorem applies;<br ><br />By /Euler's Theorem:<br />$p (aφ(p)-1)$<br />\(\implies p \mid (a^{(p^1-p^0)}-1)\)<br />\(\implies p \mid (a^{(p-1)}-1)\)<br />\(\implies p \mid (a \cdot (a^{(p-1)}-1))\)<br />\(\implies p \mid (a^p-a)\)

      Thus for a prime \(p\) and integer \(a\):

      \[p \mid (a^p - a)\]

4 (3) Relations and Congruence

4.1 The Ring [2.4]

The ring \(\mathbb{Z}_m\) is the set of all congruence classes less than \(m\) such that:

\[\mathbb{Z}_m = \{ [0]_m, [1]_m, [2]_m, [3]_m, \dots [m-1]_m\}, \enspace \forall m \in \mathbb{Z}^+\]

4.1.1 Example

We could list all the congruence classes of \(\mathbb{Z}_5\):

\[\mathbb{Z}_5 = \{[0]_5, [1]_5, [2]_5, [3]_5, [4]_5\}\]

Where:

  • \([0]_5 = \{\dots -5, 0, 5, 10, 15 \dots \}\)
  • \([1]_5 = \{\dots -4, 1, 6, 11, 16 \dots \}\)
  • \([2]_5 = \{ \dots -3, 2, 7, 12, 17, \dots \}\)
  • \([3]_5 = \{ \dots -2, 3, 8, 13, 18 \dots \}\)
  • \([4]_5 = \{\dots -1, 4, 9, 14, 19 \dots \}\)

Hence \(\mathbb{Z}_5\) could be expressed equivalently as:

\[\mathbb{Z}_5 = \{[5]_5, [11]_5, [17]_5, [19]_5, [9]_5\}\]

4.1.2 Operations on Congruence Classes

The elements of \(\mathbb{Z}_5\) can be manipulated algebraically, they have an algebraic structure, observe the following operations \(\forall a,b,c \in \mathbb{Z}\).

  1. Addition

    Addition is commutative and associative:

    \[\begin{aligned} _m + [b]_m &= [a+b]_m \\ &= [b]_m + [a]_m\end{aligned}\]

  2. Multiplication

    Multiplication is commutative and associative

    \[\begin{aligned} _m \cdot [b]_m &= [a\cdot b]_m\\ &= [b]_m \cdot [a]_m\end{aligned}\]

  3. Linear Combination

    Addition and Multiplication can be combined:

    \[[a]_m \cdot \big( [b]_m + [c]_m \big) = [a]_m \cdot [b]_m + [a]_m \cdot [c]_m\]

5 (4) Rings

5.1 Linear Congruence Equations [2.1]

A linear congruence equation is of the form:

\[a\cdot x \equiv b \pmod{n}\]

where \(a,b \in \mathbb{z}\) and \(n \in \mathbb{Z}^+\) are fixed numbers and \(x \in \mathbb{Z}\) is a variable.

So an example could be:

\[3x \equiv 7 \pmod{8}\]

The solution to this equation is the set of all x values values for which the expression is true, i.e. the solution is the set \(X\) such that:

\[X = \{x: 3x \equiv 7 \pmod{8} \}\]

5.1.1 Coingruence Class

if some \(z \in \mathbb{Z}\) is a solution of a linear congruence equation, then all members of the congruence class \([z]_n\) are also solutions as well.

The complete set of solutions is the congruence class $[z]\frac{n}{d}.

5.1.2 Testing whether a solution exists

A linear congruence equation only has a solution, if and only if:

\[\gcd(a,n) \mid b\]

  1. Example
    • \(2x \equiv 1 \pmod{4}\) has no solution because \(\gcd(2,4) = 2 \nmid 1\)
    • \(2x \equiv 1 \pmod{3}\) has a solution because \(\gcd(2,3) = 1 \mid 1\)
    • \(ax \equiv b \pmod{p}\) has a solution only if \(\gcd(a,p) \mid b\)

5.1.3 Quick solution for multiples

if \(a \neq 0\) then,

\[ax \equiv ab \pmod{n} \iff x \equiv b \pmod{\small\frac{n}{\gcd(a,n)}}\]

  1. Example

    Solve,

    \[3x \equiv 3 \pmod{9}\]

    \(3 \neq 0\), thus:

    \[\begin{aligned} 3x \equiv 3 \times 1 \pmod{9} \iff x &\equiv 1 \pmod{ \small{\frac{9}{\gcd(3,9)}} }\\ \implies x &\equiv 1 \pmod{\small {\frac{9}{3}}}\\ \implies x & \equiv 1 \pmod{3}\end{aligned}\]

    Thus we know that the difference between \(x\) and \(1\) is always divisible by \(3\), so:

    \[x = \{1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, \dots\}\]

    So the solution is the congruence class:

    \[[1]_3 = \left \{ x : x = 1 + 3n, \enspace n \in \mathbb{Z} \right \}\]

5.1.4 General Method for Solving Linear Congruence Equations

Consider the equation \(ax \equiv b \pmod{n}\), where \(d = \gcd(a,n)\) and \(d \mid b\)

  • Is there a solution for \(x\)?
    • There is because \(\gcd(a,n) \mid b\)
  • A solution can thus be found using the Euclidean Algorithm
  • If \(x=z\) is a solution to the equation, then the complete set of solutions is \([z]_\frac{n}{d}\)
    • This is proven on p. 64 of the TB
    • Although all elements of \([Z]_n\) are solutions, the set may not contain all the solutions.
  1. Example 1 (Euclidean Algorithm)

    Give the complete set of solutions to \(34x \equiv 20 \pmod{60}\).

    First observe that \(\gcd(34, 60) = 2 | 20\), thus there is a solution for \(x\).

    If \(x\) is an integer solution, then:

    \[\begin{aligned} 60 \mid (34x-20) &\implies 60t = 34x-20 \enspace t \in \mathbb{Z} \\ &\implies 20 = 34x + 60t\end{aligned}\]

    The values of \(x\) and \(t\) can be solved via the *Euclidean Algorithm by using back substitution

    1. Euclidean Algorithm

      We are concerned with \(\gcd(34,60)\), because that's what our variables are multiplied by:

      \[\begin{aligned} {2} 60 = 1 \times 34 +26 &\implies 26 = 60-1 \times 34 \qquad &(1) \\ 34 = 1\times 26 + 8 &\implies 8 = 34-1\times 26 \qquad &(2) \\ 26 = 3 \times 8 + 2 & \implies 2 = 26 -3 \times 8 \qquad & (3) \\ \ \\ 8 = 4\times 2 + 0 &\implies \gcd(60, 34) = 2 &\end{aligned}\]

      Now recall that we are trying to find the values of \(x\) and \(t\):

      \[20 = 34x+60t\]

      We will solve for \(\gcd(34,60) = 2\) in terms of 34 and 60, because \(\gcd(34, 60) = 2 \mid 20\) we will be able to multiply by a factor of \(20 \mid 2\) afterwards and have all integer solutions.

      Backward Substitution

      State \((3)\)

      \[2 = 26-3\times 8\]

      Sub \((2)\)

      \[\begin{aligned} 2 &= 26 -3 \cdot (34-26) \\ &= 26 -3 \times 34 -3\times 26 \\ &= 4 \times 60 -7 \times 34\end{aligned}\]

      Sub \((1)\)

      \[\begin{aligned} 2 &= 4 \cdot (60-34)-3\times 34 \\ &= 4 \times 60 -4 \times 34 -3 \times 34 \\ &= 4 \times 60 - 7 \times 34\end{aligned}\]

      Multiply by \(\frac{20}{2}\)

      \[\begin{aligned} 20 &= 40 \times 60 - 70\times 34 \\ &= 34 \times (-70) + 60 \times 40\end{aligned}\]

      Solve for \(x\) and \(t\)

      Thus,

      \[\begin{aligned} {4} 20 &= 34 \cdot &x &+ 60 \cdot t& \\ 20 &= 34 \times &(-70) &+ 60 \times 40& \\ \ \\ &&&\implies x = -70\\ &&&\implies t = 40\end{aligned}\]

      Hence,

      \[34 \times (-70) \equiv 20 \pmod{60}\]

      And,

      \[\begin{aligned} x &= -70 \pmod{60} \\ &= 5\end{aligned}\]

    2. Conclusion

      Thus a soltuion is \(x = 5\),

      The set of all solutions is \([z]_{\frac{n}{d}}\) ,

      where:

      • \(n\) is the modulo
      • \(d = \gcd(a,n)\)
      • \(z\) is the solution to \(x\)

      Thus the solution set for \(x\) is the congruence class:

      \[[5]_{\frac{60}{2}} = [5]_{30} = \left \{ \dots -25, 5, 35, 65, 95 \dots \right \}\]

  2. Example 2 (Multiplicative Inverse)

    Solve \(17x \equiv 3 \pmod{29}\),

    In thgis case because \(\gcd(a,n) = 1\), we can solve this using a multiplicative inverse as an alternate method (p. 66 of TB).

    The multiplicative inverse cannot be solved for when \(\gcd(a,n) \neq 1\) (p. 66 of TB).

    What we are looking for, is a multiplicative inverse, we will call it \(v\), such that:

    \[17 \times v \equiv 1 \pmod{29} \\\]

    When we find \(v\), we expect that:

    \[x \equiv 3 \cdot 3v \pmod{29}\]

    Now, if:

    \[17\cdot v \equiv 1 \pmod{29}\]

    Then:

    \[\begin{aligned} 17\cdot v &= (1-29\cdot w) \enspace : \enspace w \in \mathbb{Z}\\ 1 &= 17\cdot v + 29w\end{aligned}\]

    1. Euclidean Algorithm

      Now use the Euclidean Algorithm on the numbers \(17\) and \(29\).

      We are concerned with \(\gcd(17,29)\), because that's what our variables are multiplied by:

      \[\begin{aligned} {2} 29 = 1 \times 17 + 12 &\implies 12 = 29-17 \qquad &(1) \\ 17 = 1\times 12 + 5 &\implies 5 = 17-12 \qquad &(2) \\ 12 = 1\times 5 + 2 &\implies 2 = 12-2\times 5 \qquad &(3) \\ 5 = 2 \times 2 + 1 & \implies 1 = 5 - 2 \times 2 \qquad & (4) \\ \ \\ 2 = 2\times 1 + 0 &\implies \gcd(29, 17) = 1 &\end{aligned}\]

      Backwards Substitution

      So our goal is to find \(v\), \(w\):

      \[17\cdot v + 29 \cdot w =1\]

      state \((4)\)

      \[1 = 5 -2\times2\]

      sub \((3)\)

      \[\begin{aligned} 1 &= 5 - 2 \times (12-2 \times 5) \\ &= 5 - 2 \times 12 + 4 \times 5 \\ &= 5 \times 5 - 2 \times 12\end{aligned}\]

      sub \((2)\)

      \[\begin{aligned} 1 &= 5 \times (17 - 12) - 2 \times 12 \\ &= 5 \times 17 - 7 \times 29 + 7 \times 17 \\ &= 12 \times 17 - 7 \times 29 \\\end{aligned}\]

      Sub \((1)\)

      \[\begin{aligned} 1 &= 5 \times 17 - 7 \times (29-17) \\ &= 5 \times 17 - 7 \times 29 + 7 \times 17 \\ &= 12 \times 17 - 7 \times 29\end{aligned}\]

      Solve for \(x\) and \(t\)

      Now;

      \[\begin{aligned} {4} 1 &= 17 \cdot &v &+ 29 \cdot w& \\ 1 &= 17 \times &12 &+ 29 \times (-7)& \\ \ \\ &&&\implies v = 12\\ &&&\implies w = 1\end{aligned}\]

      The original question is:

      \[\begin{aligned} 17x &\equiv 3 \pmod{29} \\ 17x \times 12 &\equiv 3 \times 12 \pmod{29} \\ (17\times 12) x &\equiv 12 \times 3 \pmod{29} \\ (1)x &\equiv 12 \times 3 \pmod{29} \\ x &\equiv 36 \pmod{29}\end{aligned}\]

      Thus \(x = 36\) is a solution, hence the residue is a solution:

      \[\begin{aligned} x &= 36 \pmod{29} \\ &= 7\end{aligned}\]

    2. Conclusion; Solve the set of solutions

      The complete set of solutions is the congruence class:

      \[[7]_{\frac{n}{d}}\]

      Where \(n\) is the modulo and \(d = \gcd(a, n)\):

      \[\begin{aligned} x = [7]_{\frac{n}{d}} = [7]_{\frac{n}{d}}=[7]_{29} &= \left \{ \dots, -22, 7, 36, 65 \dots \right \}\\ &= 7 + 29 \cdot q \enspace : \enspace q \in \mathbb{Z}\end{aligned}\]

5.2 Divisibility Tests [2.2]

This isn't a particularly important part of the topic, but a cool algebra trick.

It is possible to test for divisibility by 9 or 3 by summing the components, e.g.:

\[\begin{aligned} 9|832005 &\iff 9 \mid (8+3+2+0+0+5) \\ &\iff 9 \mid (18)\end{aligned}\]

This can be generalised into a theorem:

An integer \(x = x_nx_{n-1}x_{n-2} \dots x_2x_1x_0\) (in decimal notation, as in each \(x\) represents the a part of the unit value of the number ) is divisible by 9 if and only if \(( x_n + x_{n-1} + x_{n-2} + x_2 + x_1 +x_0)\) is divisible by 9

5.2.1 Proof

First observe that any integer can be expressed as a sum of its unit values (e.g. \(342 = 3 \times 100 + 4 \times 10 + 1 \times 2\)), hence:

\[\begin{aligned} x = (x_n \times 10^n) + (x_{n-1} \times 10^{n-1}) + (x_{n-2} \times 10^{n-2}) \dots (x_2 \times 10^2) + (x_1 \times 10) + x_0\end{aligned}\]

Now utilise the fact that \(10 \mod 9=1\) and that the $\mod \ $ operator distributes over addition:

\[\begin{aligned} {2} x &\equiv (x_n \times 1^n) + (x_{n-1} \times 1^{n-1}) + (x_{n-2} \times 1^{n-2}) \dots (x_2 \times 1^2) + (x_1 \times 1) + x_0 &\pmod{9}\\ &\equiv x_n + x_{n-1} + x_{n-2} + x_2 + x_1 +x_0 &\pmod{9}\end{aligned}\]

Now we know that \(9 \mid x \iff x \equiv 0 \pmod{9}\), thus

\[\begin{aligned} 9 \mid x &\iff (x_n + x_{n-1} + x_{n-2} + x_2 + x_1 +x_0) \pmod{9} \\ & \iff x_n + x_{n-1} + x_{n-2} + x_2 + x_1 +x_0\end{aligned}\]

  1. In Terms of 3

    Observe that $9= 3 × 3; hence the same rules apply for the value of 3, and a similar proof.

5.3 The Ring [2.4]

For \(n \in \mathbb{Z}\):

\[\mathbb{Z}_n := \left \{ [0]_n, [1]_n, [2]_n, \dots [n-1]_n \right \}\]

5.3.1 Example

\[\mathbb{Z}_4 =\left \{ [0]_4, [1]_4, [2]_4, [3]_4 \right \}\]

Recall that:

\[\begin{aligned} _4 &= \left \{ \dots, -4, 0, 4, 8, 12, 16, \dots \right \} \\ [1]_4 &= \left \{ \dots, -3, 1, 5, 9, 13 \dots \right \} \\ [2]_4 &= \left \{ \dots, -2, 2, 6, 10, 14 \dots \right \} \\ [3]_4 &= \left \{ \dots, -1, 7, 11, 15, 19 \dots \right \}\end{aligned}\]

Hence,

\[\begin{aligned} \mathbb{Z}_4 &= \left \{ [0]_4, [1]_4, [2]_4, [3]_4 \right \} \mathbb{Z}_4 &= \left \{ [8]_4, [9]_4, [10]_4, [7]_4 \right \}\end{aligned}\]

5.3.2 Algebra with Rings

In order to do algebra in \(\mathbb{Z}_m\) we need some means by which to manipulate the elements of \(\mathbb{Z}_m\).

Take \(a, b, c \in \mathbb{Z}\):

\[[a]_m, [b]_m, [c]_m \in \mathbb{Z}\]

  1. Addition

    We define:

    \[[a]_m + [b]_m := [a+b]_m\]

    Because:

    \[\begin{aligned} [a]_m = \left \{ x: \enspace x = a + qm, \enspace q \in \mathbb{Z} \right \} \\ [b]_m = \left \{ y: \enspace x = a + pm, \enspace p \in \mathbb{Z} \right \} \\\end{aligned}\]

    We choose to define:

    \[\begin{aligned} [a+b]_m = \left \{ x+y \right \} \\\end{aligned}\]

    Addition is commutative

5.4 Rings [2.5]

5.4.1 Definitions and Axioms

A ring is a set \(R\) that has two binary operations:

  • One that is associated with Addition
    • for which the following symbol is used \((+)\)
  • One that is associated with Multiplication \((*)\)
    • Occassionally \((\cdot)\) is used as well

** Binary Operations

:CUSTOMID: header-n711

Binary operations are basically an operation between two values, a formal definition of binary operations is:

A Binary Operation $$ on some set S is a function \(f_*\):

\[f_*\enspace : \enspace S\times S \rightarrow S \enspace : \enspace (a,b) \mapsto f_*(a,b)\]

And satisfies the axioms of a ring:

  1. Associativity of Addition

    a) \((\forall a, b, c \in R) (a+b) + c = a + (b+c)\)

  2. Commutativity of Addition

    a) \((\forall a, b \in R) \enspace a + b = b + a\)

  3. Additive Elements Exists

    a) \((\forall a, b \in R) \wedge (\exists0 \in R) \enspace a + 0 = 0 + a = 0\)

  4. Associativity of Addition

    a) \((\forall a, b, c \in R) (a+b) + c = a + (b+c)\)

  5. Commutativity of Addition

    a) \((\forall a, b \in R) \enspace a + b = b + a\)

  6. Additive Elements Exists

    a) \((\forall a, b \in R) \wedge (\exists0 \in R) \enspace a + 0 = 0 + a = 0\)

    ** Further Axioms

    :CUSTOMID: header-n737

    These further axioms provide different classes of following axioms are not necessarily exhibited by rings, but if they are the rings

    1. Commutativity of Multiplication*
      1. \((\forall a,b \in R) a \cdot b = b \cdot a\)
        1. A ring that satisfies this property is called a commutative Ring
    2. Existence of a Multiplicative identity Element (a ring with Unity)
      1. \((\exists1 \in R) (\forall a \in R) \enspace 1 \cdot a = a \cdot 1 = a\)
        1. A ring that satisfies this property is called a a ring with identity or equivalently a a ring with unity

    * Examples of Rings

    :CUSTOMID: header-n757

    • \(\mathbb{N}\) is not a ring, because there is no additive inverse
    • \(\mathbb{Z}, \mathbb{R}, \mathbb{Q}, \mathbb{C}\) are all commutative rings with identity/unity
    • The set of all even integers (\(2\mathbb{Z}\)) is a ring because
      • It is closed under addition and multiplicaiton
      • It satisfies all other axioms
      • It is a commutative ring
      • Because 1 is not even there is no multiplicative identity, hence it is NOT a ring with unity.
    • Square matrices are rings with unity/identity
      • They are not commutative because the order of multiplication is important.

    ** Properties of Rings

    :CUSTOMID: header-n780

    Proofs for these properties are provided in the textbook

    ** Unique Identitities

    :CUSTOMID: header-n782

    • The additive Identity of a ring is always unique
    • The additive inverse of a ring is always unique
    • The multiplicative identity of a ring is always unique
      • (i.e. If the ring has a multiplicative inverse)

    ** Algebraic Rules

    :CUSTOMID: header-n793

    The following rules hold for rings:

    Let \(a, b \in R\);

    1. \(0a = a0 =0\)
    2. \(a(-b)=-(ab)\)
    3. \(-(-a)=a\)
    4. \((-a)(-b) = ab\)
    5. \((-1)a=-a\)
      1. Assuming a multiplicative identity exists for the ring \(R\)

    * Zero Divisors

    :CUSTOMID: header-n811

    An element of some ring \(R\) is a zero divisor if:

    \[\begin{aligned} &a,b \in R: \\ \ \\ &(\forall a \in R : a \neq 0) (\exists b \in R : b \neq 0) : \\ \ \\ &\qquad \qquad \qquad ab = 0 \enspace \vee \enspace ba = 0 \end{aligned}\]

    ** Examples

    :CUSTOMID: header-n814

    \[2,3 \in \mathbb{Z}_6 : \\ \ \\ 2 * 3 = [6]_6 = [0]_6\]

Hence, 2 and 3 are both Zero Divisors

5.4.2 Units

An element \(a \in R\) of some ring \(R\) is a unit if:

The element always has a multiplicative inverse, i.e.

\[a \text{ is a unit} \iff \exists b \in R : ab = ba =1\]

  • 1 is a unit of all rings
  • Any ring with unity/identity is such that -1 is a unit
    • Because (-1) × (-1) = 1
  1. Application

    If \(a \in \mathbb{Z}_n\) is a unit, then the equation:

    \[x \equiv b \pmod{n}\]

    Can be solved by multiplying both sides by \(a^{-1}\)

    1. Example

      \[3x \equiv 5 \pmod{7}\]

      For \(3\in \mathbb{Z}_7\) there exists an inverse:

      \[3 \times 5 = 1 \implies 3^{-1} = 5\]

      3 is a unit because there exists 5 such that:

      \[3 \times 5 = 5\times 3 = 1 \in \mathbb{Z}_7\]

      Hence,

      \[\begin{aligned} {2} 3x &\equiv 5 &\pmod{7} \\ 5 \times 3x &\equiv 5 \times 5 &\pmod{7} \\ 15x &\equiv 25 &\pmod{7} \\ (1x) &\equiv 25 &\pmod{7} \\ x &\equiv 25 &\pmod{7} \\ &\equiv 3 &\pmod{7} \\ &= [3]_7 &\pmod{7} \\\end{aligned}\]

5.4.3 Unit or Zero Divisor but not both

an element \(a \in R\) cannot be both a zero divisor and a unit

Because the prior multiplies to give zero and the latter multiplies to give 1.

6 (5) Fields and Complex Numbers

TB: [2.5], [2.6] *

6.1 Rings [2.5]

6.1.1 Integral Domain

An integral domain is a ring that is:

  1. Is commutative
  2. Is with unity/identity
  3. Has no Zero Divisors
  1. Properties of Integral Domains

    In an integral domain we can cancel, i.e.:

    \[(c \neq 0) \enspace \wedge \enspace (ac = bc) \implies a = b\]

    1. Proof

      \[\begin{aligned} ac &= bc \\ ac - bc = 0 \\ c\cdot (a-b) = 0 \\ \ \\ \text{But} \\ c\neq 0 \\ \implies a - b = 0 \\ a=b\end{aligned}\]

  2. Example

    So for example \(\mathbb{Z}_5\) is an integral domain because:

    1. The elements of \(\mathbb{Z}_5\) are commutative
    2. \(1 \in \mathbb{Z}_5\), hence it is with unity
    3. There are no non-zero values in \(\mathbb{Z}_5\) that multiply to give 0

    Further,

    Take \(\mathbb{Z}_p : p = \left \{ 2,3, 5, 7, 11, 13, 17, \dots \right \}\)

    All \(\mathbb{Z}_p\) are integral Domains

6.1.2 Fields

A field is:

  1. An integral Domain
  2. In which every non-zero element is a unit.

So for clarity a field is a set \(F\) that is:

  1. A Ring
  2. A commutative Ring
  3. A Ring with unity/identity
  4. All elements are units
    1. This necessitates that no elements can be zero-divisors because they are mutually exclusive
  1. Examples

    \(\mathbb{N}\) is not a Ring because it does not contain an additive identify \(0\)

    \(\mathbb{Z}\) is an integral domain because it is commutative, with unity and has no non-zero value that multiply to give 0;

    It is NOT a field because not all values have an inverse (e.g. \(3^{-1} = \frac{1}{3} \notin \mathbb{Z}\))

    \(\mathbb{Q}\), \(\mathbb{R}\), \(\mathbb{C}\) are all fields because every element has a multiplicative identity and are hence units.

6.2 The Field of Complex Numbers

The field of complex numbers is:

\[\mathbb{C} = \left \{ a + b i : a, b \in \mathbb{R} \right \}\]

Addition is defined by:

\[(a+bi) + (c+di) = (a+c) + (b+d)i\]

Multiplication is defined by:

\[(a+bi)\cdot (c + di) = (ac-bd) + (ad+bc)i\]

More over we represent the real and imaginary parts of a complex number thusly:

\[z = a + bi \\ \implies \text{Re}(z) = a \enspace ; \enspace \text{Im}(z) =b\]

6.2.1 The set of Complex Numbers is a Field

Remember that a field is:

  1. A Ring
  2. A Commutative Ring
  3. A Ring with Identity
  4. All elements are units
    1. This necessitates that no elements can be zero-divisors, for they are mutually exclusive.

In this case the complex numbers:

  1. Are indeed a ring
  2. Complex Numbers are commutative
  3. There existws a multiplicative Identity (\(z = 1 + 0i\))
  4. Every element has an inverse
    1. \(z \times \frac{1}{z} = 1\)

6.2.2 Polar Notation   diagram

A complex Number can be represented on the complex Plane:

1551604985277.png

And any complex number can be represented also in polar notation:

\[\begin{aligned} z &= a +bi = r \cdot \text{cis}(\theta) \\\end{aligned}\]

Where:

\(r = \sqrt{a^2 +b^2} \\ \theta = \text{Atan}(\frac{b}{a})\)

And the combination is equivalent because:

\[\begin{aligned} \text{cis}(\theta) & = \cos(\theta) + i \cdot \sin(\theta) \\ &= \cos{\theta} + i\cdot \sin{\left ( \text{Asin}\left( \frac{b}{a} \right ) \right )} \\ &=a + bi\end{aligned}\]

Flowing from power series for exponential, cosine and sine functions we have also:

\[z = a + bi = r \text{cis}(\theta) = e^{i\theta}\]

6.2.3 Multiplying Complex Numbers

Polar notation makes it far easier to multiply complex numbers

Remember that multiplying a number on the complex plane is really a transformative process involving scaling and rotating the plane from the point 1 (the multiplicative identity) top the point of the multiplier.

Hence it stands to reason that the distance from the origin of the new point will be larger by a factor of the scaling and the rotation on the plane will simply be added.

For:

\[u = r\cdot \text{cis}(\theta) \enspace \text{and} \enspace v = s \cdot \text{cis}(\phi) \\ \ \\ u\cdot v = rs \cdot \text{cis}(\phi + \theta)\]

6.2.4 Power of Complex Numbers (De Moivre's Theorem)

If follows algebraically that raising complex numbers to the power of some \(n\):

\[\begin{aligned} z &= r \cdot \text{cis}(\theta) \\ &\implies z^n = r^n \cdot \text{cis}(n\cdot \theta) \enspace : \enspace n \in \mathbb{Z^*}\end{aligned}\]

Recall that \(\mathbb{Z^*}\) is the set of non-negative integers {0, 1, 2, 3, 4 …}.

#+BEGINQUOTE This is an important distinction from \(\mathbb{N}\) because although many texts provide \(0 \notin \mathbb{N}\) using the reasoning that the naturals are the various possible sums of 1, many authors provide \(0 \in \mathbb{N}\) where it is convenient, so try not to use \(\mathbb{N}\) because it can be ambiguous

#+ENDQUOTE

6.2.5 Roots of Complex Numbers

Multiple Complex Numbers, when raised to a power, may equal the same end result, hence solutions for \(z\) given \(z^n\) are:

\[z^{1/n} = r ^{1/n} \cdot \text{cis}\left( \frac{\theta + 2k\pi}{n} \right ), \quad \text{for} k = 1,2,3, \dots (n-1)\]

There are always \(n\) roots.

7 Endnotes

Notes on Polynomials and the Fundamental Theorem of Arithmetic are contained in the PDF file.

I don't have any notes whatsoever on anything thereafter.

8 collapsible markdown?

9 Notes on Markdown

  • Small MathBlocks on iPhone
    • If numbered equations are used, they will render extremely small on an iPhone, is the trade off worth it?
      • It's relatively easy to enable and disable numbered mathblocks in Typora on the fly through the preferences Ctrl + , on mac ⌘ + ,

Author: ryan

Created: 2019-11-10 Sun 19:42

Validate