Math 2710 Second Exam Study Guide

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

Key topics from Chapter Three

• 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.

Key Topics from Chapter 4

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\).

Sequences and series

• 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.

Decimal expansions

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,