# MA121 Study Guide - Final Guide: Good Luck!!, Set Notation, Integer Factorization

412 views24 pages

28 Feb 2018

School

Department

Course

Professor

For unlimited access to Study Guides, a Grade+ subscription is required.

Wilfrid Laurier University

MA 121

Introduction to Mathematical Proofs

Fall 2017

Final Exam

Prof: Robert John Rundle

Exam Guide

Table of Contents:

Prime Number Proofs & Least Common Multiple

Congruent Relations

Linear Congruences and Congruence Classes

Introduction to Diophantine Equations

Complex Numbers

Polar Form

Complex Exponentials and Roots of Complex Numbers

Prime Number Proofs & Least Common Multiple

We will see two different (yet similar) proofs that there are infinitely many prime numbers. One

proof would be sufficient, however, seeing something proved 2 different ways can be helpful as it

demonstrates that there are more than one way to make a mathematical argument.

Theorem: There exists a prime greater than n for all positive integers n. (it could also say there are

infinitely many primes)

Proof: Given any value n we construct a larger value that is either prime or has a prime factor

greater than n.

Consider y = n! and x = n! + 1.

Let p be a prime divisor of x, such that p ≤ n. This implies that p is also a divisor of y, because n! is a

product of natural numbers from 1 to n. So we have p/y and p/x, as well as p/(x+y) and p/(x-y).

But x-y = 1 and the only other divisor of 1 is -1 or 1, both of which are not prime. So there are no

prime divisors of x less than n. And since every integer is either prime or a product of primes, we

either have that x > n is prime, or there exists a prime p where p > n in the prime factorization of x.

Theorem: There is no largest prime.

Proof: Proof by contradiction.

Suppose there is a largest prime. So we can write down all of the infinitely many primes as: {p1, p2,

…. pΩ} such that pΩ is the largest.

Now let n = p1 x p2 x … pΩ . Observe that n must be larger than pΩ. Therefore n is composite and is a

product of primes. Let pk denote a prime factor of n. Thus we have pk/n. And since pk∈{p1, p2, …. pΩ},

we also have pk/(n-1). We know that pk/n and pk/(n-1) implies that pk/n-(n-1) or pk/1.

But no positive integer divides 1 but 1, and 1 is not prime so pk/1 is impossible. and raises a

mathematical contradiction. This implies that our assumption that pk is the largest prime is false, and

so we conclude that there is no largest prime.

Least Common Multiple (LCM)

Abbreviations:

*LCM: Least Common Multiple

*GCD: greatest common divisor

Given 2 non-zero integers a and b we can have many values that are positive common multiples of

a and b. By the well ordering principle we know that amongst all of those multiples there is one

that’s the smallest, and this is known as the least common multiple of a and b. We define a

function lcm(a,b) that returns this value.

Example: Suppose a = 12 and b = 24, so we have lcm(a,b) = 24. In general if a/b then lcm(a,b) = |b|.

At this point it is worth mentioning that if a/b then gcd(a,b) = |a|, and that lcm(a,b) x gcd(a,b) =

|ab|.

Example: Suppose a = 13, b = 24 we have lcm(a,b) = (13)(24). In general if a and b are relatively

prime, that is, if gcd(a,b) = 1 then lcm(a,b) = |ab|. So when gcd(a,b) = 1, we can observe that

lcm(a,b) × gcd(a,b) = |ab|.

Let a = 250 and b = 575. We can construct a prime factorization of a and b.

Prime factorization:

250 = 2(53)

575 = 23(52)

We can inspect the prime factorization of a and b for their greatest common divisor (52, or 25).

We can also inspect them for their least common multiple:

250 x 575 = 2(53) x (52)(23) = 52 x (2)(53)(23)

And since gcd(a,b) = 52 we can conclude that lcm(a,b) = (2)(53)(23). So in this case we also have

gcd(a,b) x lcm(a,b) = |ab|.

Let p1, p2, pk denote all prime factors of both a and b ordered from smallest to largest. In our

example the list of prime factors would be 2,5,23.