**Note:** This guide is offered without warranty.

The second exam will cover the following topics.

Chapter 3 omitting 3.6 and 3.7 but including:

- Section 3.1 Congruence
- Section 3.3 Equivalence Relations
- Section 3.4 Modular Arithmetic, in particular Fermat’s Little Theorem (3.42)
Section 3.5 Congruence Equations, in particular The Linear Congruence Theorem (3.54)

Chapter 4, all topics.

Sequences and Series

- Definitions of convergence of a sequence to a limit
- Proofs of convergence and divergence in particular cases
- Sums of convergent sequences converge; constant multiples of convergent sequences converge
- Geometric Series (finite and infinite): definition, proof of convergence

Decimal Expansions of Rational Numbers (Section 4 of Chapter 5)

- Relationship between repeating expansions and geometric series
- Convergence of eventually repeating decimal expansions to rational numbers
- Proof that rational numbers have eventually repeating decimal expansions

- Definition of congruence and ways in which it acts like equality (Prop 3.11, 3.12). Example: Prove that if \(a\equiv a'\pmod{m}\) and \(b\equiv b'\pmod{m}\) then \(ab\equiv a'b'\pmod{m}\).
- Division of congruences (When you can cancel x from both sides in a congruence \(ax\equiv bx\pmod{m}\) and proof of why or why not) (Proposition 3.13)
- Calculation modulo \(m\) (see for Example 3.15). Examples: Prove that no perfect square is of the form \(3n+2\) for some \(n\); find the ones digit of \(3^{2019}\).
- Equivalence relations: Definition of an equivalence relation (reflexivity, symmetry, transitivity); proof that congruence is an equivalence relation – for example, prove that if \(a\equiv b\pmod{m}\) and \(b\equiv c\pmod{m}\) then \(a\equiv c\pmod{m}\). Definition of an
*equivalence class.***Example:**Suppose the relation on people is “currently live in the same town”; explain that this is an equivalence relation; what are the equivalence classes?**Example:**Say \(x\sim y\) if \(x^2=y^2\); is this an equivalence relation? What are the equivalence classes? - Modular Arithmetic.
**Example:**Solve the congruence \(13x=53\pmod{11}\).**Example:**Prove that if \(\mathrm{gcd}(a,m)=1\) then \(ax\equiv b\pmod{m}\) has a solutions.**Example:**Prove that if \(ax\equiv b\pmod{m}\) has a solution \(x\) then \(\mathrm{gcd}(a,m)\) divides \(d\).**Example:**Explain the relationship between the theorem on solving congruences (3.54) and the Theorem from chapter 2 on Linear Diophantine Equations.**Example:**Suppose \(p\) is a prime, and \(a\) is an integer not divisible by \(p\). Prove that if \(ai\equiv aj\pmod{p}\) then \(i\equiv j\pmod{p}\). Use this to prove that the set of congruence classes \(\{[a],[2a],[3a],\ldots,[(p-1)a]\}\) modulo \(p\) is the same as the set \(\{[1],[2],\ldots,[p-1]\}\). (this is a key step in the proof of Fermat’s little theorem).**Example:**Prove Fermat’s little theorem. - Congruence Equations. See problems 32-41 on page 83 of Gilbert and Vanstone. Also look at problems 98-104.

Sample problems on induction from Gilbert and Vanstone – see for example: 11-18, 29, 31, 33, 37, 43, 45, 47, 53, 56, 65-67, 74, 76.

Prove that the binomial coefficient \(\binom{n}{r}\) counts the number of \(r\) element subsets of an \(n\) element set.

Prove that the sum of a finite geometric series \(a+ar+ar^2+\cdots+ar^{n}\) is \(a\frac{r^{n+1}-1}{r-1}\).

(Optional) Define a function recursively by setting \(f(0)=0\), \(f(1)=1\), and \(f(n)=af(n-1)+bf(n-2)\) for constants \(a\) and \(b\). Let \[ u(x)=\sum \frac{f(n)}{n!}x^{n}. \]

Prove that \(u(x)\) is a solution to the linear second order differential equation \[ \frac{d^2u}{dx^2}-a\frac{du}{dx}-bu. \]

Let \(t^2-at-b=0\) be the characteristic polynomial of this differential equation and let \(r_0\) and \(r_1\) be its roots. Assume for simplicity that these roots are distinct (so that \(a^2-4b\not=0\).) By expressing \(u(x)\) as a linear combination of \(\exp(r_0x)\) and \(\exp(r_1x)\), derive a formula for \(f(n)\) involving \(r_0\) and \(r_1\).

See the problems in Hammack in the section on sequences, esp. Problems 1-6, 8, 9, 10, 13. In particular You should be able to state

**verbatim**the definition of convergence of a sequence and prove directly that simple sequences converge to stated limits.**Example:**Prove that \(n/(3n+2)\) converges to \(1/3\) without using any tricks from Calculus.See the problems in Hammack in the section on series, esp. problem 1.

Prove that an eventually repeating decimal expansion (or base r expansion) converges to a rational number. Prove that a rational number has an eventually repeating decimal (or base r) expansion.

See: Gilbert and Vanstone, Chapter 5, Problems 23-32, 37, 41, 42, 44,