Proofs And Theory Flashcards
√2
√2 is irrational
√2 is irrational (Proof)
This is a proof by contradiction. Suppose the statement is false — that is, suppose √2 is rational.
This means that there are integers m,n such that
√2 = m/n.
Take m/n to be in lowest terms (recall that this means that m,n have no common factors greater than 1).
Squaring the above equation gives 2 = m^2/n^2, hence m^2 = 2n^2.
If m was odd, then m^2 would be odd but m^2 = 2n^2 is clearly even, so this cannot be the case.
Therefore, m is even. Hence, we can write m = 2k, where k is an integer.
Then m^2 = 4k^2 = 2n^2.
Consequently n^2 = 2k^2. So n^2 is even and, again this means n is also even.
We have now shown that both m and n are even. However, this means that the fraction m/n is not in lowest terms. This is a contradiction.
Therefore, 2 is not rational.
De Moivre’s Theorem (statement)
Let z1,z2 be complex numbers with polar forms
z1 = r1 (cosθ1 +isinθ1), z2 = r2 (cosθ2 +isinθ2).
Then the product is
z1z2 = r1r2 (cos(θ1 +θ2)+isin(θ1 +θ2)).
In other words, z1z2 has modulus r1r2 and argument θ1 + θ2.
De Moivre’s Theorem (proof)
Maybe check
We have
z1z2 = r1r2 (cosθ1 +isinθ1)(cosθ2 +isinθ2)
z1z2 = r1r2 (cosθ1 cosθ2 −sinθ1 sinθ2 +i(cosθ1 sinθ2 +sinθ1 cosθ2))
z1z2 = r1r2 (cos(θ1 +θ2)+isin(θ1 +θ2)).
The Fundamental Theorem of Algebra
Every polynomial equation of degree at least 1 has a root in C.
Euler’s Formula
For a convex polyhedron with V vertices, E edges and F faces, we have
V − E + F = 2
The Fundamental Theorem of Arithmetic
Let n be an integer with n≥2.
(I) Then n is equal to a product of prime numbers: we have:
n = p1 . . . pk
where p1,…, pk are primes and p1 ≤ p2 ≤ … ≤ pk.
(II) This prime factorization of n is unique: in other words, if n= p1…pk =q1…ql
where the pis and qis are all prime, p1 ≤ p2 ≤…≤ pk and q1 ≤q2 ≤ …≤ql,
then
k=l and pi =qi for all i=1,…,k.
The Fundamental Theorem of Arithmetic (existence proof)
Every positive integer greater than 1 is equal to a product of prime numbers.
Use Strong induction.
For n ≥ 2, let P(n) be the statement that n is equal to a product of prime numbers.
Clearly P(2) is true, as 2 = 2 is a prime factorization of 2.
Suppose that P(2),…,P(n) are all true. This means that every integer between 2 and n has a prime factorization.
Now consider n+1. If n+1 is prime, then it certainly has a prime factorization
(as a product of 1 prime).
If n+1 is not prime, then by the definition of a prime number, there is an integer a dividing n+1 such that a≠1 or n+1.
Writing b = (n+1)/a, we then have n+1=ab and a,b∈{2,3,…,n}.
By assumption, P(a) and P(b) are both true, i.e., a and b have prime factorizations. Say
a= p1…pk, b=q1…ql, where all the pi and qi are prime numbers.
Then
n+1=ab= p1…pkq1…ql.
This is an expression for n + 1 as a product of prime numbers.
We have now shown that P(2), . . . , P(n)⇒P(n+1).
Therefore, P(n) is true for all n ≥ 2, by Strong Induction.
The Fundamental Theorem of Arithmetic (uniqueness proof)
We prove this by contradiction.
Suppose there is some integer n which has two different prime factorizations, say
n= p1…pk =q1…ql
where p1 ≤p2 ≤…≤pk, q1 ≤q2 ≤…≤ql,
and the list of primes p1,…,pk is not the same list as q1,…,ql.
Now in the equation p1 … pk = q1 …ql, cancel any primes that are common to both sides. Since we are assuming the two factorizations are different, not all the primes cancel, and we end up with an equation
r1 …ra = s1 …sb,
where each ri ∈ {p1,…, pk}, each si ∈ {q1,…,ql}, and none of the ri’s is equal to any of the si’s (i.e., ri ≠ sj for all i, j).
Now we obtain a contradiction. Certainly r1 divides r1 …ra, hence r1 divides s1 …sb.
By Proposition 10.6, this implies that r1|sj for some j.
However, sj is prime, so its only divisors are 1 and sj, and hence r1 = sj. But we know that none of the ri’s is equal to any of the si’s, so this is a contradiction.
This completes the proof of (II).
Number of primes
there are infinitely many prime numbers
there are infinitely many prime numbers (proof)
This is a proof by contradiction.
Assume that there are only finitely many primes.
This means that we can make a finite list
p1,p2,p3,…,pn
of all the prime numbers.
Now define a positive integer
N=p1p2p3…pn +1.
By Proposition 8.1, N is equal to a product of primes, say N = q1 . . . qr with all qi prime.
As q1 is prime, it belongs to the above list of all primes, so q1 = pi for some i.
Now q1 divides N, and hence pi divides N.
Also pi divides p1p2…pn, which is equal to N−1.
Thus, pi divides both N and N−1.
But this implies that pi divides the difference between these numbers, namely 1. This is a contradiction
Fermat’s Little Theorem
Let p be a prime number, and let a be an integer that is not divisible by p.
Then:
a^(p−1) ≡ 1 mod p.
