Introduction
1
Introduction to Proofs and Mathematical Logic
1.1
Introduction
1.2
Statements, predicates and connectives
1.3
Logical equivalence
1.4
Implications
1.5
Proofs
1.5.1
Direct Proof
1.5.2
Equality
1.5.3
Proof by cases
1.5.4
Proof by contrapositive
1.5.5
Proof by contradiction
1.6
Sets and Quantifiers
1.6.1
Sets
1.6.2
Quantifiers
1.6.3
Implicit quantifiers
2
The Integers
2.1
Axioms
2.2
Decimal Expansions
2.3
Order properties of
\(\mathbb Z\)
2.4
Proof by Induction
2.5
The Remainder Theorem
2.6
More Decimal Expansions
3
Divisibility and Euclid’s Algorithm
3.1
Divisors
3.2
The Euclidean Algorithm
3.3
Bezout’s Identity
3.4
Coprime Integers
3.5
Linear Diophantine Equations
4
Prime Numbers
5
Congruences
5.1
Congruences
5.2
Congruence Classes
5.3
Modular Arithmetic
5.4
Linear congruences
5.5
Simultaneous linear congruences
6
Congruences with a prime modulus
6.1
Lagrange’s Theorem
6.2
Fermat’s Little Theorem
6.3
Square roots mod
\(p\)
and mod
\(pq\)
7
Euler’s Function
7.1
Euler’s Theorem
7.2
Euler’s Product Formula
8
Applications to cryptography
8.1
Ciphers using modular exponentiation
8.2
Digital Signatures
9
More cryptography
9.1
Deciphering the Vigenère cipher
9.2
Index of Coincidence
9.3
Chi-squared test
9.4
Frequency Analysis
9.5
Cracking Keyword Substitution Cipher
10
Appendix A - Well ordering principle
11
Appendix B - Peano’s Axioms
11.1
The Axioms
11.2
Arithmetic
11.3
Models for
\(\mathbb N\)
11.4
Von Neumann’s model for
\(\mathbb N\)
11.5
Extending
\(\mathbb N\)
to
\(\mathbb Z\)
11.6
Extending
\(\mathbb Z\)
to
\(\mathbb Q\)
.
11.7
Extending the rationals to the reals
12
Appendix C - Infinite Cardinals
13
Appendix D - Euclidean Algorithm
14
Appendix E - Linear congruence
15
Appendix F - Simultaneous Linear congruences
16
Appendix G - Frequency calculator
17
Appendix H - Vigenère Cipher Calculator
18
Appendix I - Substitution Cipher Calculator
Content Index
References
MATH1001 Introduction to Number Theory
Chapter 3
Divisibility and Euclid’s Algorithm