Abstract Algebra

Instructor: Dr. Gabriel Sosa Castillo
Date: From 2025-08-28 to 2025-12-19

Foundational Principles of Proof

The Principle of Mathematical Induction

If is a sentence dependent on and:

1. is true for some natural number .
2. being true implies is also true.

Then is true for all natural numbers .

Tip: When proving by induction:

1. Start with a number of base cases (usually one or two).
2. State the induction hypothesis: "Assume is true for some ".
3. Inductive step: Prove the implication for .

The Principle of Strong Mathematical Induction

If is a sentence dependent on and:

1. are true for some and some .
2. being true for all where implies is true.

Then is true for all .

Example

Let and for . Prove that for all .

Proof

1. Base Cases: We check and since the recurrence relation depends on the two preceding terms.

   • For : and . The formula holds.
   • For : and . The formula holds.

2. Inductive Hypothesis: Assume that for some , the formula is true for all integers with .

3. Inductive Step: We want to prove the formula for .

   This is the required formula for .

By the principle of strong induction, the formula holds for all .

Induction vs. Strong Induction

The main difference between mathematical induction (weak induction) and strong mathematical induction lies in the inductive hypothesis.

• In weak induction, the inductive step assumes the statement is true for a single integer and proves .
• In strong induction, the inductive step assumes the statement is true for all integers from the base case up to and proves .

The Well-Ordering Principle

If is a non-empty subset of , then has a least element. That is, there exists an element such that for all .

Proof by Contradiction

Assume for contradiction that there is a non-empty subset with no minimum element. Let . We will prove by strong induction that .

1. Base Case ( ): If , it would be the minimum element of . This contradicts our assumption. Therefore, , which means .

2. Inductive Hypothesis: Assume that for some , all integers such that are in .

3. Inductive Step: We want to show that . From the hypothesis, are not in . If were in , it would be the smallest element of . But has no minimum, so . Thus, .

By the principle of strong induction, . This implies is empty, contradicting our initial assumption that is non-empty. Thus, the well-ordering principle holds.

Proving Equality

Here are common strategies for proving equality in different mathematical contexts:

Core Concepts in Number Theory

Theorem 1: The Division Algorithm

Given natural numbers and with , there exist unique natural numbers (quotient) and (remainder) such that and .

Proof of Theorem 1 (Existence by Induction)

Let be a fixed natural number. We prove by induction on that the statement : "there exist such that and " is true for all .

1. Base Cases:

   • If , then . Here , and .
   • If :
     • If : . ( )
     • If : . ( )

2. Inductive Hypothesis: Assume is true for some . So, with and .

3. Inductive Step: Consider .

   • Case 1: . Then . Let and . Then .
   • Case 2: . Let and . Then .

This completes the inductive step.

Proof of Uniqueness

Assume and where and . Without loss of generality, assume . Then . Since is a multiple of and is strictly less than , it must be . So, . This implies . Since , we must have .

Greatest Common Divisor (GCD)

Given two integers and , not both zero, their greatest common divisor, denoted or , is a positive integer satisfying:

1. divides both and (i.e., and ).
2. If any integer divides both and , then must also divide .

Theorem 2: Characterization of the GCD (Bezout's Identity)

Let be integers, not both zero. The is the smallest positive integer that can be expressed as a linear combination of and . Note: are integers, not just natural numbers!

Proof of Theorem 2

Proof to be added.

Prime and Coprime Numbers

• Prime: A natural number is prime if its only positive divisors are 1 and .
• Coprime: Two integers and are coprime (or relatively prime) if .

Corollary 3: Characterization of Coprime Numbers

Integers and are coprime if and only if there exist integers and such that .

Proof of Corollary 3

Proof to be added (from Sep 5 notes).

Lemma 4: Euclid's Lemma

Let and be a prime number. If , then or .

Proof of Lemma 4

Proof to be added (from Sep 8 notes).

Theorem 5: Infinitude of Primes

There are infinitely many prime numbers.

Theorem 6: The Fundamental Theorem of Arithmetic (Unique Factorization)

Every integer can be represented as a product of prime numbers. This representation is unique, apart from the order of the factors.

More formally, for any integer , there exist unique primes and unique positive integers such that:

Introduction to Algebraic Structures

Basic Properties of Binary Operations

Let be a binary operation on a set .

• Commutative Property: for all .
• Associative Property: for all .

Identity and Inverse Elements

• Identity Element: An element is an identity element if for all . The identity element must be unique for the entire set.

  • Right Identity: An element is a right identity if for all .
  • Pitfalls: 0 is not an identity for subtraction because . 1 is a right identity for exponentiation ( ) but not a left identity ( ).

• Inverse Element: If has an identity element , an element is the inverse of if .

  • Right Inverse: is a right inverse of if .

Groups

A group is a set combined with a binary operation that satisfies four axioms:

1. Closure: For all , the result is also in .
2. Associativity: For all , .
3. Identity Element: There exists an element such that for every , .
4. Inverse Element: For each , there exists an element (denoted ) such that .

If a group also satisfies the commutative property, it is called an Abelian Group.

Examples:

• Abelian Groups: , , ,
• Non-Abelian Groups: (invertible 2x2 matrices with matrix multiplication), Bijections on a set with function composition .
• Not Groups:
  • lacks inverses.
  • lacks inverses for singular matrices.

Other Groups