The Central Idea
Algebra does not depend on ordinary real-number arithmetic alone.
We can change the underlying set and redefine the operations while still preserving meaningful algebraic structure.
Two important examples are:
- modular arithmetic, where numbers are grouped by remainders;
- Boolean algebra, where values such as \(0\) and \(1\) are combined by logical operations.
These systems are finite, highly structured, and fundamental in number theory, abstract algebra, logic, and computing.
What Is Modular Arithmetic?
Modular arithmetic studies integers according to their remainders after division by a fixed positive integer called the modulus.
For modulus \(n\), we write
\[ a\equiv b\pmod n \]when \(a\) and \(b\) differ by a multiple of \(n\).
Equivalently,
\[ \boxed{ a\equiv b\pmod n \Longleftrightarrow n\mid(a-b) }. \]Example: Congruence Modulo 5
Consider
\[ 17 \]and
\[ 2. \]Their difference is
\[ 17-2=15. \]Since
\[ 5\mid15, \]we have
\[ \boxed{17\equiv2\pmod5}. \]Congruence Classes
Modulo \(n\), every integer belongs to one of \(n\) congruence classes.
A standard set of representatives is
\[ \boxed{ \mathbb{Z}_n=\{0,1,2,\ldots,n-1\} }. \]Each integer is identified with the representative having the same remainder modulo \(n\).
Example: Classes Modulo 4
Modulo \(4\), every integer is congruent to exactly one of
\[ 0,\qquad1,\qquad2,\qquad3. \]For example,
\[ 14\equiv2\pmod4, \]because
\[ 14=4(3)+2. \]Clock Arithmetic
A clock provides an intuitive model of modular arithmetic.
On a \(12\)-hour clock,
\[ 10+5=15 \]corresponds to
\[ 15\equiv3\pmod{12}. \]So five hours after \(10\) o'clock is \(3\) o'clock.
The arithmetic wraps around after reaching the modulus.
Addition Modulo \(n\)
To add modulo \(n\):
- add normally;
- reduce the result to its remainder modulo \(n\).
For example,
\[ 4+6=10. \]Modulo \(7\),
\[ 10\equiv3\pmod7. \]Therefore,
\[ \boxed{4+6\equiv3\pmod7}. \]Multiplication Modulo \(n\)
Multiplication works similarly.
For example,
\[ 5\cdot4=20. \]Modulo \(6\),
\[ 20\equiv2\pmod6. \]Therefore,
\[ \boxed{5\cdot4\equiv2\pmod6}. \]Congruence Respects Addition
If
\[ a\equiv b\pmod n \]and
\[ c\equiv d\pmod n, \]then
\[ \boxed{ a+c\equiv b+d\pmod n }. \]This makes addition well defined on congruence classes.
Congruence Respects Multiplication
Under the same assumptions,
\[ a\equiv b\pmod n \]and
\[ c\equiv d\pmod n \]imply
\[ \boxed{ ac\equiv bd\pmod n }. \]Therefore multiplication is also well defined on modular classes.
Modular Addition Forms a Group
Under addition modulo \(n\),
\[ (\mathbb{Z}_n,+) \]is an abelian group.
The additive identity is
\[ 0. \]Every element has an additive inverse modulo \(n\).
For example, modulo \(7\),
\[ 3+4\equiv0\pmod7. \]Thus \(4\) is the additive inverse of \(3\) modulo \(7\).
Additive Inverse Modulo \(n\)
The additive inverse of \(a\) modulo \(n\) is any representative \(b\) satisfying
\[ a+b\equiv0\pmod n. \]A convenient choice is
\[ \boxed{n-a} \]when
\[ 0Multiplicative Inverses Modulo \(n\)
A multiplicative inverse of \(a\) modulo \(n\) is an element \(b\) satisfying
\[ \boxed{ab\equiv1\pmod n}. \]Unlike additive inverses, multiplicative inverses do not always exist.
When Does a Modular Inverse Exist?
An integer \(a\) has a multiplicative inverse modulo \(n\) exactly when
\[ \boxed{\gcd(a,n)=1}. \]Such elements are called units modulo \(n\).
Example: Inverse Modulo 7
Since
\[ \gcd(3,7)=1, \]the element \(3\) has a multiplicative inverse modulo \(7\).
Indeed,
\[ 3\cdot5=15\equiv1\pmod7. \]Therefore,
\[ \boxed{3^{-1}\equiv5\pmod7}. \]Example: No Inverse Modulo 8
Consider \(2\) modulo \(8\).
Since
\[ \gcd(2,8)=2\ne1, \]\(2\) has no multiplicative inverse modulo \(8\).
No product
\[ 2b \]is congruent to \(1\) modulo \(8\).
Prime Moduli
If \(p\) is prime, then every nonzero element of
\[ \mathbb{Z}_p \]is relatively prime to \(p\).
Therefore every nonzero element has a multiplicative inverse.
Thus
\[ \boxed{\mathbb{Z}_p\text{ is a field}}. \]Composite Moduli
If \(n\) is composite, then
\[ \mathbb{Z}_n \]contains zero divisors.
For example, modulo \(8\),
\[ 2\cdot4=8\equiv0\pmod8. \]Since neither factor is zero modulo \(8\), both are zero divisors.
Therefore \(\mathbb{Z}_8\) is not a field.
Solving a Modular Linear Equation
Consider
\[ 3x\equiv5\pmod7. \]Since the inverse of \(3\) modulo \(7\) is \(5\), multiply both sides by \(5\):
\[ 5(3x)\equiv5(5)\pmod7. \]Then
\[ x\equiv25\equiv4\pmod7. \]Therefore,
\[ \boxed{x\equiv4\pmod7}. \]Cancellation in Modular Arithmetic
Cancellation must be handled carefully.
From
\[ ac\equiv bc\pmod n, \]we cannot always conclude
\[ a\equiv b\pmod n. \]Cancellation is valid when \(c\) is invertible modulo \(n\).
Example: Cancellation Failure
Modulo \(6\),
\[ 2\cdot1\equiv2\pmod6 \]and
\[ 2\cdot4\equiv8\equiv2\pmod6. \]Thus
\[ 2\cdot1\equiv2\cdot4\pmod6, \]but
\[ 1\not\equiv4\pmod6. \]The factor \(2\) cannot be cancelled because it is not invertible modulo \(6\).
Modular Operation Tables
Because \(\mathbb{Z}_n\) is finite, modular arithmetic can be displayed in operation tables.
For addition modulo \(4\):
| \(+\) | \(0\) | \(1\) | \(2\) | \(3\) |
|---|---|---|---|---|
| \(0\) | \(0\) | \(1\) | \(2\) | \(3\) |
| \(1\) | \(1\) | \(2\) | \(3\) | \(0\) |
| \(2\) | \(2\) | \(3\) | \(0\) | \(1\) |
| \(3\) | \(3\) | \(0\) | \(1\) | \(2\) |
Applications of Modular Arithmetic
Modular arithmetic appears in many areas of mathematics and computing.
Applications include:
- clock and calendar calculations;
- divisibility tests;
- check digits and error detection;
- cryptography;
- computer arithmetic;
- hashing and cyclic data structures;
- number theory;
- finite fields and coding theory.
What Is Boolean Algebra?
Boolean algebra is an algebraic system built around two values, commonly written
\[ \boxed{\{0,1\}}. \]These may represent:
- false and true;
- off and on;
- no and yes;
- open and closed states;
- absence and presence.
Boolean operations are designed to model logical combination rather than ordinary arithmetic.
Three Fundamental Boolean Operations
The basic Boolean operations are:
- AND;
- OR;
- NOT.
Common symbolic forms include
\[ x\land y, \] \[ x\lor y, \]and
\[ \neg x. \]Boolean AND
The operation
\[ x\land y \]equals \(1\) only when both inputs are \(1\).
| \(x\) | \(y\) | \(x\land y\) |
|---|---|---|
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(0\) |
| \(1\) | \(0\) | \(0\) |
| \(1\) | \(1\) | \(1\) |
Boolean OR
The operation
\[ x\lor y \]equals \(1\) when at least one input is \(1\).
| \(x\) | \(y\) | \(x\lor y\) |
|---|---|---|
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(1\) |
Boolean NOT
The operation
\[ \neg x \]reverses the Boolean value:
\[ \boxed{\neg0=1} \]and
\[ \boxed{\neg1=0}. \]Boolean Algebra Is Not Ordinary Arithmetic
The symbols \(0\) and \(1\) may look familiar, but the operations are different.
In ordinary arithmetic,
\[ 1+1=2. \]In Boolean OR,
\[ 1\lor1=1. \]Therefore Boolean algebra must be interpreted according to its own operations and laws.
Boolean Identities
For OR,
\[ \boxed{x\lor0=x}. \]Thus \(0\) is the identity for OR.
For AND,
\[ \boxed{x\land1=x}. \]Thus \(1\) is the identity for AND.
Boolean Absorbing Elements
Under OR,
\[ \boxed{x\lor1=1}. \]So \(1\) is absorbing for OR.
Under AND,
\[ \boxed{x\land0=0}. \]So \(0\) is absorbing for AND.
Idempotent Laws
Boolean operations satisfy
\[ \boxed{x\lor x=x} \]and
\[ \boxed{x\land x=x}. \]These are called idempotent laws.
Repeating the same Boolean input does not change the result.
Commutative Laws
Boolean OR and AND are commutative:
\[ \boxed{x\lor y=y\lor x} \]and
\[ \boxed{x\land y=y\land x}. \]Associative Laws
Boolean operations are also associative:
\[ \boxed{ (x\lor y)\lor z=x\lor(y\lor z) } \]and
\[ \boxed{ (x\land y)\land z=x\land(y\land z) }. \]Distributive Laws
AND distributes over OR:
\[ \boxed{ x\land(y\lor z) = (x\land y)\lor(x\land z) }. \]Boolean algebra also has the dual distributive law:
\[ \boxed{ x\lor(y\land z) = (x\lor y)\land(x\lor z) }. \]The second law has no direct analogue in ordinary arithmetic.
Complements
Every Boolean value has a complement.
The complement of \(x\) is
\[ \neg x. \]It satisfies
\[ \boxed{x\lor\neg x=1} \]and
\[ \boxed{x\land\neg x=0}. \]Double Negation
Applying Boolean complement twice returns the original value:
\[ \boxed{\neg(\neg x)=x}. \]Thus complement is self-inverse.
De Morgan's Laws
Two of the most important Boolean identities are
\[ \boxed{ \neg(x\land y) = \neg x\lor\neg y } \]and
\[ \boxed{ \neg(x\lor y) = \neg x\land\neg y }. \]Negating a combined statement switches AND and OR while negating each component.
Absorption Laws
Boolean algebra also satisfies
\[ \boxed{ x\lor(x\land y)=x } \]and
\[ \boxed{ x\land(x\lor y)=x }. \]These are called absorption laws.
The Principle of Duality
Many Boolean identities come in pairs.
If we interchange
\[ \lor \longleftrightarrow \land \]and simultaneously interchange
\[ 0 \longleftrightarrow 1, \]one valid Boolean identity often becomes another valid identity.
This symmetry is called the principle of duality.
Example of Duality
Begin with
\[ x\lor0=x. \]Swap OR with AND and \(0\) with \(1\):
\[ x\land1=x. \]The dual statement is also true.
Boolean Expressions
Boolean variables can be combined into expressions such as
\[ (x\land y)\lor\neg z. \]These expressions behave like algebraic formulas, but their values are determined by Boolean operations.
Evaluating a Boolean Expression
Suppose
\[ x=1,\qquad y=0,\qquad z=0. \]Evaluate
\[ (x\land y)\lor\neg z. \]First,
\[ x\land y = 1\land0 = 0. \]Also,
\[ \neg z = \neg0 = 1. \]Therefore,
\[ 0\lor1 = \boxed{1}. \]Truth Tables
A truth table lists the output of a Boolean expression for every possible assignment of its variables.
With two Boolean variables,
\[ x,\qquad y, \]there are
\[ 2^2=4 \]possible input combinations.
Truth Table for Exclusive OR
The exclusive OR operation, often written XOR, is true when exactly one input is true.
| \(x\) | \(y\) | XOR |
|---|---|---|
| \(0\) | \(0\) | \(0\) |
| \(0\) | \(1\) | \(1\) |
| \(1\) | \(0\) | \(1\) |
| \(1\) | \(1\) | \(0\) |
XOR behaves exactly like addition modulo \(2\).
Boolean Algebra and \(\mathbb{Z}_2\)
There is an important connection between Boolean operations and arithmetic modulo \(2\).
Addition modulo \(2\) has table
\[ 0+0=0,\qquad 0+1=1,\qquad 1+0=1,\qquad 1+1=0. \]This matches XOR.
Multiplication modulo \(2\) has table
\[ 0\cdot0=0,\qquad 0\cdot1=0,\qquad 1\cdot0=0,\qquad 1\cdot1=1. \]This matches Boolean AND.
Boolean OR Is Not Addition Modulo 2
Boolean OR differs from modular addition.
In Boolean OR,
\[ 1\lor1=1. \]But modulo \(2\),
\[ 1+1\equiv0\pmod2. \]Therefore OR and addition modulo \(2\) must not be confused.
Boolean Algebra of Sets
Boolean algebra also appears naturally in set theory.
On the power set
\[ \mathcal{P}(U), \]the operations correspond as follows:
| Boolean Operation | Set Operation |
|---|---|
| AND | Intersection \(\cap\) |
| OR | Union \(\cup\) |
| NOT | Complement |
| \(0\) | \(\varnothing\) |
| \(1\) | \(U\) |
De Morgan's Laws for Sets
Boolean De Morgan laws correspond directly to set identities:
\[ \boxed{ (A\cap B)^c = A^c\cup B^c } \]and
\[ \boxed{ (A\cup B)^c = A^c\cap B^c }. \]The same structural law appears in logic and set algebra.
Boolean Algebra and Logic
Boolean algebra provides an algebraic language for propositions.
We may interpret
\[ 1 \]as true and
\[ 0 \]as false.
Then
\[ \land \]corresponds to logical conjunction,
\[ \lor \]corresponds to logical disjunction, and
\[ \neg \]corresponds to negation.
Boolean Algebra and Digital Circuits
Boolean operations also model digital logic gates.
- AND corresponds to an AND gate.
- OR corresponds to an OR gate.
- NOT corresponds to an inverter.
- XOR corresponds to an exclusive-OR gate.
Complex digital circuits can be represented and simplified using Boolean expressions.
Simplifying Boolean Expressions
Boolean laws can simplify expressions much as algebraic identities simplify ordinary formulas.
Consider
\[ x\lor(x\land y). \]By the absorption law,
\[ \boxed{x\lor(x\land y)=x}. \]The entire expression reduces to a single variable.
Example: Simplification with Complements
Consider
\[ x\land(\neg x\lor y). \]Distribute:
\[ (x\land\neg x)\lor(x\land y). \]Since
\[ x\land\neg x=0, \]we get
\[ 0\lor(x\land y). \]Therefore,
\[ \boxed{ x\land(\neg x\lor y) = x\land y }. \]Boolean Algebra as an Algebraic Structure
A Boolean algebra is more than the two-element set
\[ \{0,1\}. \]More generally, it is a set equipped with two binary operations and a complement operation satisfying Boolean laws such as:
- commutativity;
- associativity;
- distributivity;
- identity laws;
- complement laws.
The power set of any set under union, intersection, and complement is a standard example.
Modular Arithmetic and Boolean Algebra Share a Theme
The two systems are different, but they illustrate the same central algebraic principle:
\[ \boxed{ \text{structure depends on the set and the operations} }. \]Ordinary arithmetic laws cannot simply be assumed.
Instead, we identify the operations, test their properties, and work according to the laws of the chosen structure.
Common Error: Treating Congruence as Equality
The statement
\[ 17\equiv2\pmod5 \]does not mean
\[ 17=2. \]It means their difference is divisible by \(5\).
Congruence is an equivalence relation, not ordinary numerical equality.
Common Error: Forgetting to Reduce Modulo \(n\)
If working in
\[ \mathbb{Z}_7, \]the result
\[ 5+6=11 \]should be reduced:
\[ 11\equiv4\pmod7. \]Therefore the modular result is
\[ \boxed{4}. \]Common Error: Cancelling a Noninvertible Factor
In modular arithmetic, cancellation is safe only when the cancelled factor has a multiplicative inverse modulo the modulus.
A common factor in the ordinary integer sense is not enough.
Common Error: Assuming Every Nonzero Residue Has an Inverse
This is true modulo a prime, but not modulo an arbitrary composite number.
In \(\mathbb{Z}_8\),
\[ 2 \]is nonzero but has no multiplicative inverse.
Common Error: Treating Boolean OR as Ordinary Addition
Boolean OR satisfies
\[ 1\lor1=1. \]Ordinary addition satisfies
\[ 1+1=2. \]Addition modulo \(2\) satisfies
\[ 1+1\equiv0\pmod2. \]These are three different operations.
Common Error: Confusing Boolean Complement with Additive Inverse
Boolean complement satisfies
\[ x\lor\neg x=1 \]and
\[ x\land\neg x=0. \]It is not the same concept as the additive inverse from a group.
The word “complement” reflects the laws of Boolean algebra.
A Reliable Modular-Arithmetic Procedure
- Identify the modulus \(n\).
- Perform the ordinary integer operation.
- Reduce the result modulo \(n\).
- For inverse questions, check \(\gcd(a,n)=1\).
- For equations, multiply by modular inverses only when they exist.
- Be cautious with cancellation when zero divisors are present.
- Use prime-modulus field structure when applicable.
A Reliable Boolean-Algebra Procedure
- Identify the Boolean variables and operations.
- Apply NOT before the binary operations it modifies.
- Use truth tables when direct verification is helpful.
- Use identity and absorbing laws to simplify.
- Use idempotent and absorption laws to remove redundancy.
- Use distributive laws to rearrange expressions.
- Use De Morgan's laws when negating AND or OR expressions.
- Check the final expression against a truth table when needed.
Example: Full Modular Workflow
Solve
\[ 5x\equiv3\pmod7. \]First find the inverse of \(5\) modulo \(7\).
Since
\[ 5\cdot3=15\equiv1\pmod7, \]the inverse is \(3\).
Multiply both sides by \(3\):
\[ 3(5x)\equiv3(3)\pmod7. \]Therefore,
\[ x\equiv9\equiv2\pmod7. \]Hence
\[ \boxed{x\equiv2\pmod7}. \]Example: Full Boolean Workflow
Simplify
\[ (x\lor y)\land(x\lor\neg y). \]Use the distributive identity
\[ (a\lor b)\land(a\lor c) = a\lor(b\land c). \]Then
\[ (x\lor y)\land(x\lor\neg y) = x\lor(y\land\neg y). \]Since
\[ y\land\neg y=0, \]we obtain
\[ x\lor0=x. \]Therefore,
\[ \boxed{ (x\lor y)\land(x\lor\neg y)=x }. \]Practice 1: Congruence
Determine whether
\[ 23\equiv5\pmod6. \]Practice 2: Modular Addition
Compute
\[ 8+9\pmod7. \]Practice 3: Modular Multiplication
Compute
\[ 6\cdot5\pmod8. \]Practice 4: Modular Inverse
Find the multiplicative inverse of \(4\) modulo \(7\).
Practice 5: No Modular Inverse
Does \(6\) have a multiplicative inverse modulo \(9\)? Explain.
Practice 6: Boolean AND and OR
Evaluate
\[ (1\land0)\lor1. \]Practice 7: Boolean Complement
Evaluate
\[ \neg(1\lor0). \]Practice 8: De Morgan's Law
Rewrite
\[ \neg(x\land y) \]using De Morgan's law.
Practice 9: Simplify
Simplify
\[ x\lor(x\land y). \]Practice 10: Identify the Error
A student says:
“Because \(1+1=2\), Boolean OR satisfies \(1\lor1=2\).”
Explain the error.
Practice Answers
Practice 1
Since
\[ 23-5=18 \]and
\[ 6\mid18, \]we have
\[ \boxed{23\equiv5\pmod6}. \]Practice 2
\[ 8+9=17. \]Modulo \(7\),
\[ 17\equiv3\pmod7. \]Therefore,
\[ \boxed{3}. \]Practice 3
\[ 6\cdot5=30. \]Modulo \(8\),
\[ 30\equiv6\pmod8. \]Therefore,
\[ \boxed{6}. \]Practice 4
We need \(b\) such that
\[ 4b\equiv1\pmod7. \]Since
\[ 4\cdot2=8\equiv1\pmod7, \]the inverse is
\[ \boxed{2}. \]Practice 5
No. Since
\[ \gcd(6,9)=3\ne1, \]\(6\) is not invertible modulo \(9\).
Practice 6
\[ 1\land0=0, \]so
\[ 0\lor1=\boxed{1}. \]Practice 7
\[ 1\lor0=1, \]so
\[ \neg1=\boxed{0}. \]Practice 8
By De Morgan's law,
\[ \boxed{ \neg(x\land y) = \neg x\lor\neg y }. \]Practice 9
By the absorption law,
\[ \boxed{x\lor(x\land y)=x}. \]Practice 10
Boolean OR is not ordinary addition.
Its definition gives
\[ \boxed{1\lor1=1}. \]The symbols \(0\) and \(1\) represent Boolean values under Boolean operations, not ordinary arithmetic quantities in this context.
What to Remember
Modular arithmetic identifies integers that differ by multiples of a modulus:
\[ \boxed{ a\equiv b\pmod n \Longleftrightarrow n\mid(a-b) }. \]Important modular facts include:
- \(\mathbb{Z}_n\) has \(n\) congruence classes;
- addition modulo \(n\) forms an abelian group;
- \(a\) has a multiplicative inverse modulo \(n\) exactly when \(\gcd(a,n)=1\);
- \(\mathbb{Z}_p\) is a field when \(p\) is prime;
- composite moduli produce zero divisors.
Boolean algebra uses values such as \(0\) and \(1\) with operations AND, OR, and NOT.
Its major laws include:
- identity and absorbing laws;
- commutative and associative laws;
- idempotent and absorption laws;
- distributive laws;
- complement laws;
- De Morgan's laws;
- duality.
Both systems reinforce the same structural lesson: algebraic behavior is determined by the underlying set together with its operations and laws.
Where We Go Next
Modular arithmetic and Boolean algebra show how finite algebraic systems can support rich internal structure. The next stage returns to objects that can be added and scaled, leading from abstract operations toward linear structure.
The next lesson, Scalars, Vectors, and Vector Spaces, introduces vectors as algebraic objects, scalars drawn from fields, and the axioms that organize vector addition and scalar multiplication.