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

412 views24 pages
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
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 24 pages and 3 million more documents.

Already have an account? Log in
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.
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 24 pages and 3 million more documents.

Already have an account? Log in
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.
Unlock document

This preview shows pages 1-3 of the document.
Unlock all 24 pages and 3 million more documents.

Already have an account? Log in

Get access

Grade+
$10 USD/m
Billed $120 USD annually
Homework Help
Class Notes
Textbook Notes
40 Verified Answers
Study Guides
1 Booster Class