Next:
Introduction
Up:
Applied Abstract Algebra
Previous:
Contents
Contents
Index
Some elementary number theory
Subsections
Introduction
Divisibility
Division algorithm
The greatest common divisor and least common multiple
Linear diophantine equations
Binary and
-ary notation
Application: Divisibility criteria
Application: Winning the game of Nim
The Euclidean algorithm
Ideals
The Euclidean algorithm
The extended Euclidean algorithm
Euler's phi function
Primes
Pascal's triangle revisited
The Fundamental Theorem of Arithmetic
Perfect numbers and Mersenne primes
Primality testing
Sieve of Eratosthenes
Multiplicative Functions
Congruences
Application: Divisibility criteria revisited
Aside on equivalence relations
Properties of
Repeated squaring algorithm
Fermat's little theorem
Linear recurrence equations
Application: Two ciphers
Caesar's cipher
A stream cipher: linear feedback shift registers
Feedback with carry shift register ciphers
Application: calendar calculations
First method
Second method (due to Conway)
The Chinese remainder theorem
General Chinese remainder theorem
An application to Euler's
-function
Integral powers mod
Fermat's Little Theorem, revisited
Euler's theorem
Application: Decimal expansions of rational numbers
Application: RSA encryption
Small exponent attack on RSA
Application: The discrete log problem
Application: Diffie-Hellman key exchange
Application: ElGamal encryption
Arithmetic properties of
: a summary
Special project: continued fractions (optional)
Number theory exercises using GAP
Number theory exercises using MAGMA
David Joyner 2002-08-23
-ary notation
-function
: a summary