prev

next

of 23

Published on

20-Jan-2016View

45Download

0

Embed Size (px)

DESCRIPTION

Proof Must Have. Statement of what is to be proven. "Proof:" to indicate where the proof starts Clear indication of flow Clear indication of reason for each step Careful notation, completeness and order Clear indication of the conclusion I suggest pencil and good erasure when needed. - PowerPoint PPT Presentation

Transcript

Proof Must HaveStatement of what is to be proven."Proof:" to indicate where the proof startsClear indication of flowClear indication of reason for each stepCareful notation, completeness and orderClear indication of the conclusionI suggest pencil and good erasure when needed

Number Theory - Ch 3 DefinitionsZ --- integers Q - rational numbers (quotients of integers)rQ a,bZ, (r = a/b) ^ (b 0)Irrational = not rationalR --- real numberssuperscript of + --- positive portion onlysuperscript of - --- negative portion onlyother superscripts: Zeven, Zodd , Q>5

"closure" of these sets for an operationZ closed under what operations?

Integer Definitionseven integer n Zeven k Z, n = 2k odd integer n Zodd k Z, n = 2k+1 prime integer (Z>1) n Zprime r,sZ+, (n=r*s) (r=1)v(s=1)composite integer (Z>1) n Zcomposite r,sZ+, n=r*s ^(r1)^(s1)

Constructive Proof of ExistenceIf we want to prove:nZeven, p,q, r,sZprime n = p+q ^ n = r+s^pr^ ps^ qr^ qslet n=10 n Zeven by definition of even Let p = 5 and the q = 5p,q Zprime by definition of prime 10 = 5+5Let r = 3 and s = 7r,s Zprime by definition of prime 10 = 3+7and all of the inequalities hold

- Methods of Proving Universally Quantified StatementsMethod of Exhaustionprove for each and every member of the domainrZ+ where 23
Examples of Generalizing from the "Generic Particular"The product of any two odd integers is also odd.m,n Z, [(m Zodd n Zodd ) m*n Zodd ]

The product of any two rationals is also rational.m,nQ, m*n Q

Disproof by Counter Example rZ, r2Z+ rZ+Counter Example: r2= 9 ^ r = -3 r2Z+ since 9 Z+ so the antecedent is truebut rZ+ since -3Z+ so the consequent is falsethis means the implication is false for r = -3 so this is a valid counter exampleWhen a counter example is given you must always justify that it is a valid counter example by showing the algebra (or other interpretation needed) to support your claim

Division definitionsd | n kZ, n = d*kn is divisible by dn is a multiple of dd is a divisor of nd divides nstandard factored formn = p1e1 * p2e2 * p3e3 * * pkek

Proof using the ContrapositiveFor all positive integers, if n does not divide a number to which d is a factor, then n can not divide d.

Proof using the ContrapositiveFor all positive integers, if n does not divide a number to which d is a factor, then n can not divide d.

n,d,cZ+, ndc nd

Proof using the ContrapositiveFor all positive integers, if n does not divide a number to which d is a factor, then n can not divide d.

n,d,cZ+, ndc nd n,d,cZ+, n|d n|dcproof:

- more integer definitionsdiv and mod operatorsn div d --- integer quotient forn mod d --- integer remainder for(n div d = q) ^ (n mod d = r) n = d*q+r where n Z0, d Z+, r Z, q Z, 0 r
Quotient Remainder TheoremnZ dZ+ q,rZ (n=dq+r) ^ (0 r < d)Proving definition of equiv in a mod by using the quotient remainder theoremThis means prove that if [m d n], then [d|(n-m)]where m,nZ and dZ+

Proofs using this definitionmZ+ a,bZ a m b k Z a=b+km

mZ+ a,b,c,dZ a m b ^ c m d a+c m b+d

Proof by Division into CasesnZ 3n n2 3 1

Floor and Ceiling Definitionsn is the floor of x where xR ^ n Z x = n n x < n+1n is the ceiling of x where xR ^ n Z x = n n-1 < x n

Floor/Ceiling Proofsx,yR x+y = x + y

xR yZ x+y = x +y

Proof by Division into Cases (again)

The floor of (n/2) is eithera) n/2 when n is even or b) (n-1)/2 when n is odd

Prime Factored Formn = p1e1 * p2e2 * p3e3 * * pkek Unique Factorization Theorem (Theorem 3.3.3)given any integer n>1kZ, p1,p2,pkZprime, e1,e2,ekZ+, where the ps are distinct and any other expression of n is identical to this except maybe in the order of the factorsStandard Factored Formpi < pi+1mZ,8*7*6*5*4*3*2*m=17*16*15*14*13*12*11*10Does 17|m ??

Steps Toward Proving the Unique Factorization TheoremEvery integer greater than or equal to 2 has at least one prime that divides it

For all integers greater than 1, if a|b, then a (b+1)

There are an infinite number of primes

Using the Unique Prime Factorization TheoremProve that aZ+ 3 | a2 3 | aProve that the

Prove: aZ+qZprime q|a2 q |a

Summary of Proof MethodsConstructive Proof of Existence

Proof by ExhaustionProof by Generalizing from the Generic ParticularProof by ContrapositionProof by ContradictionProof by Division into Cases

Errors in ProofsArguing from example for universal proof.Misuse of VariablesJumping to the Conclusion (missing steps)Begging the QuestionUsing "if" about something that is known