Prove that the square root of 2 is irrational

Prove that the square root of 2 is irrational.

We will use the well ordering principle for this proof and try to reach a contradiction.

Let A be a set in the natural numbers so that there exists b and a in the natural numbers so that sqrt(2)=(a)/(b)

thus 2 =(a^2)/(b^2)

and (a^2)= 2(b^2)

From the formula above we see that a must be an even number because it is equal to 2(b^2). If we substitute 2k for a to represent this we get:

(2k^2) = 2 (b^2)

(b^2) = 4(k^2) / 2 = 2(k^2)

so
b = 2k

And so b also must be even, however if both a and b are smallest elements in the set A, then one must be even and one must be odd so we have a contradiction and the square root of 2 cannot be expressed as the ratio of two numbers, thus it is irrational.

Prove for natural numbers a and b, the greatest common divisor of a and b may be written as a linear combination of a and b.

Prove for natural numbers a and b, the greatest common divisor of a and b may be written as a linear combination of a and b. Or if d is the greatest common divisor of a and b GCD(a,b) there exist integers x and y such that

ax+ by = d

Let C be a set defined by z where z=ax+by for some integers x and y, and z is greater than 0. C is in the natural numbers and has a smallest element. m such that m=ax(0)+by(0). No we see that m < = a and m < = b because a(1) + b(0) and a(0) + b(1) are also in C. We will show that m=d. Since d divides a and d divides b, d divides ax(0) + by(0). Thus d divides m. Therefore d < = m.

Now the proof by contradiction...
suppose m does not divide a. Then by the division algorithm we proved yesterday there exist natural numbers q and r such that a=mq+r, where 0 < style="color: rgb(204, 0, 0);">m= ax(0) + by(0)
mq = aqx(0) + bqy(0)
a -r =aqx(0) + bqy(0)
r = a - aqx(0) - bqy(0)
r = a(1-qx(0) + b(-qy(0))

So r is a linear combination of a and b, so r is in our first set C. But r < style="color: rgb(204, 153, 51);">m < = d and as we proved earlier d <= m so d = m , so d (the GCD) can be written as a linear combination of a and b.

Prove every natural number n > 1 has a prime factor

Prove every natural number n > 1 has a prime factor.

Prime numbers are numbers which have no divisors other than 1 (i.e. 1,3,5,7,11...)
Composite numbers have more than one divisor (i.e. 4,6,8,9...)

If n is prime (has no divisor other than 1), then n is a prime factor of n. If n is composite then n has divisors other than 1 and n. We will make p a number that is the smallest divisor of n (other than 1), and show that p is prime.

To do this we will use a proof by contradiction, so start by assuming the opposite. Assume p is composite and not prime, then p must also have a divisor d, where 1 < d < p. So now d divides p, and p divides n, but then d < p which contradicts the definition of p being the smallest divisor. Thus p must be prime if it is the smallest divisor, and so every natural number has a prime factor.

Prove if ab is odd, then both a and b are odd. (Contradiction)

Assume a and b are positive integers, prove if a*b is odd then a and b are odd.

Proof by contradiction: where we want to prove Q => P we take ~P=> Q Λ ~ Q which is a contradiction, so therefore we conclude P.

This is a proof by contradiction which means that we have to assume the opposite consequent, which is the say that a and b are not both odd. So either a is even or b is even.

If a is even, then a=2k for some integer k, and b*2k will always be even.

If b is even, then b=2m for some integer m, and a*2m will always be even.

So either case leads to a contradiction that a*b is odd, and therefore if a*b is odd, then both a and b are odd.