# MAT1313

## Course Catalog

MAT 1313. Algebra and Number Systems. (3-0) 3 Credit Hours.

Corequisite: MAT1214. Basic logic and proofs. Properties of integer numbers, mathematical induction, the fundamental theorem of arithmetic, the infinitude of primes, modular arithmetic, rational and irrational numbers, complex numbers, functions, polynomials, and the binomial theorem. Generally offered: Fall, Spring. Course Fees: LRS1 \$45; STSI \$21.

## Topics List

Week # Sections Topics Prerequisite Skills Student Learning Outcomes
1

1.1 & 1.2

Propositional Logic

• Recognize propositional formulas built from atoms using connectives.
• Correctly interpret propositional formulas using truth tables.

2

1.3 & 1.4

• Tautologies and Deductions.
• Quantifiers.
• Propositional Logic.
• Establish whether a propositional formula is a tautology.
• State De Morgan's Laws of logic.
• Recognize conditional tautologies as laws of deduction.
• Express conditionals in disjunctive form.
• Express the negation of a conditional in conjunctive form.
• Identify the direct and contrapositive forms of a conditional.
• Recognize the non-equivalence of a conditional and its converse.
• Recognize a biconditional as the conjunction of a conditional and its converse.
• Identify the domain of interpretation of a quantified statement.
• Correctly interpret quantified statements.
• Correctly negate quantified statements.

3

1.5 & 1.6

• Sets.
• Set Operations.
• Introduction to proofs of universal statements in set theory
• Disproving universal statements via counterexamples.
• Tautologies and Deductions.
• Quantifiers.
• Recognize and interpret set equality and set inclusion.
• Recognize set operations and state their formal definitions.
• Recognize formal proofs as processes of logical deduction of conclusions from assumptions.
• Prove basic universal statements pertaining to set inclusion and set operations.
• Correctly identify false universal statements in set theory and disprove them with appropriate counterexamples.
• Correctly use propositional and quantified tautologies as deductive laws.

4

2.1

• Divisibility of integers.
• The Division Algorithm.
• Proofs and Counterexamples.
• Propositional Logic.
• Quantifiers.
• Recognize the notion of integer divisibility via its formal definition, examples and counterexamples.
• Correctly state and apply the Division Algorithm of integers.
• Prove basic facts pertaining to divisibility and the division algorithm.

5

2.2 & 2.3

• Greatest Common Divisor.
• Bèzout's Identity: GCD(a,b) = au + bv for some u,v∊ℤ.
• Coprime integers.
• The Extended Euclidean Algorithm.
• Divisibility of integers.
• The Division Algorithm.
• Compute the GCD of two integers using the Euclidean algorithm.
• Express the GCD of two integers as a linear combination thereof using the extended Euclidean algorithm.

6

2.5

• Primes.
• Euclid's proof of the infinitude of primes by contradiction.
• Euclid's Lemma: for p prime, p|ab implies p∣a or p∣b.
• Unique factorization and the Fundamental Theorem of Arithmetic.
• Divisibility of integers.
• The Extended Euclidean Algorithm.
• Greatest Common Divisor.
• Coprime integers.
• Define prime numbers and state their basic properties.
• Prove the infinitude of primes.
• Prove Euclid's Lemma using Bèzout's identity.
• Prove uniqueness of prime factorization using Euclid's Lemma.
• Characterize divisibility and GCD of integers in terms of their prime factorizations.

7

3.1–3.3

• Arithmetic congruences and basic modular arithmetic.
• Tests of divisibility.
• Divisibility of integers.
• The Division Algorithm.
• Use arithmetic congruences to interpret the remainder of integer division.
• Use congruences to compute remainders of divisions where the quotient is large or irrelevant.
• Prove basic divisibility criteria by 2, 3, 5, 9 and 11 for number in base 10, using modular arithmetic.

8

3.4

• Modular rings ℤₙ.
• Modular fields ℤₚ.
• Fermat's Little Theorem.
• Primes.
• Arithmetic congruences and basic modular arithmetic.
• Recognize the modular rings ℤₙ as number systems.
• Evaluate sums, differences, negations and products in ℤₙ.
• Identify invertible and non-invertible elements of ℤₙ.
• Find the inverse (when defined) of a given element of ℤₙ.
• Prove that the modular ring ℤₚ is a field if and only if p is prime.
• Correctly state Fermat's Little Theorem, both as a theorem in modular arithmetic modulo a prime p, and as a theorem for the finite field ℤₚ.
• Apply Fermat's Little Theorem to solve arithmetic problems.

9

4.1

• Mathematical Induction.
• Inductive proofs.
• Basic proofs.
• Tautologies and Deductions.
• Quantifiers.
• Divisibility of integers.
• State the Principle of Mathematical Induction (PMI).
• Prove elementary algebraic and arithmetic statements by induction.
• Prove elementary algebraic and arithmetic statements by strong induction.

10

4.2 & 4.3

• Recursion.
• The Binomial Theorem (Binomial Expansion Formula).
• Mathematical Induction.
• Inductive proofs.
• Factorials.
• Recognize recursive definitions of sequences and sets.
• Prove elementary properties of recursively defined sets and sequences (Fibonacci and geometric sequences).
• Recursively construct successive rows of Pascal's triangle.
• Identify the entries in Pascal's Triangle as Binomial Coefficients.
• State and apply the Binomial Expansion Formula.
• Compute individual binomial coefficients using the quotient-of-falling powers formula (n𝑪k) = n(n−1)…(n−k+1)/k!

11

5.1 & 5.2

• The rational number system 𝐐.
• The real number system 𝐑.
• Fractional powers and roots of real numbers.
• Rational and irrational numbers. Existence of irrationals.
• Divisibility of integers.
• Unique factorization and the Fundamental Theorem of Arithmetic.
• Decimals and decimal expansions.
• Roots and fractional powers of real numbers.
• Identify the set 𝐐 of rational numbers as a number system (a field).
• Identify the set 𝐑 of real numbers as a number system (a field extending 𝐐).
• Prove the irrationality of √2 and, more generally, of √p for p prime.
• Prove that fractional powers xm/n of real x>0 are well defined and unique.
• Informally interpret the convergence of decimal expansions as the completeness of 𝐑.
• Informally recognize that the universal existence of roots ⁿ√x and fractional powers xm/n of real numbers x>0 relies on the completeness of 𝐑.

12

8.1–8.4

• Introduction to complex numbers and their operations.
• The complex number system 𝐂.
• The complex plane.
• The real number system 𝐑.
• Fractional powers and roots of real numbers.
• Represent complex numbers algebraically in Cartesian form.
• Represent complex numbers geometrically as points on a plane.
• Carry out arithmetic operations with complex numbers.
• Interpret the geometric meaning of addition, subtraction and complex conjugation.
• Identify the set 𝐂 of complex numbers as a field extending the real number system 𝐑.

13

8.5–8.7

• Polar form of complex numbers.
• Geometric meaning of complex multiplication and division.
• Powers and roots of complex numbers. De Moivre’s Theorem.
• The complex number system 𝐂.
• The complex plane.
• Roots and fractional powers of real numbers.
• Represent complex numbers in polar form.
• Algebraically relate the Cartesian and polar forms of a complex number.
• Use the identities cis(𝜃+ɸ) = cis𝜃∙cisɸ and (cis𝜃)n = cis(n𝜃) (De Moivre's formula) for the complex trigonometric function cis𝜃 = cos𝜃 + i∙sin𝜃 to evaluate products and powers both algebraically and geometrically.
• Evaluate all n-th roots of a given complex number both in trigonometric and (when possible) in algebraic closed form, and represent them geometrically.

14

8.8–9.2

• Roots and factors of polynomials. The Remainder Theorem.
• Real and complex roots.
• The Fundamental Theorem of Algebra.
• The complex number system 𝐂.
• Powers and roots of complex numbers. De Moivre’s Theorem.
• Polynomials: arithmetic operations, long division, and factorizations.
• State and prove the Remainder Theorem.
• Identify roots with linear factors of a polynomial.
• Factor given simple polynomials into irreducible factors over ℚ, ℝ and ℂ.
• State the Fundamental Theorem of Algebra.
• Use the Fundamental Theorem of Algebra to prove that irreducible real polynomials are linear or quadratic.