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	Real numbers. Rational and irrational numbers.	Divisibility of integers. Unique factorization and the Fundamental Theorem of Arithmetic. 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. Recognize that the universal existence of roots ⁿ√x and fractional powers xm/n of real numbers x>0 cannot be proved by algebraic methods alone.