  # Basic Number Theory

 Definitions • Even and Odd numbers A number n from Z is called even iff . A number n from Z is called odd iff . • Prime and Composite numbers A number n from Z is called prime iff  A number n from Z is called composite iff Definitions • A real number r is called rational if , such that r = p / q. Is 0.121212… a rational number? Every rational number can be written as a repeating or terminating decimal . Every integer is a rational number. • All real numbers which are not rational are called irrational. • If n and d are both integers, then n is divisible by d iff . Notation: d | n  Synonymous statements: n is a multiple of d d is a factor of n d is a divisor of n d divides n Theorem: Transitivity of Divisibility • For all integers a, b and c, if a divides b and b divides c, then a divides c. Unique Factorization Theorem for Integers • Given any integer n>1, there exist a positive integer k, distinct prime numbers , and positive integers such that n can be uniquely represented in the standard factored form: . (Proof in Section 10.4.) Quotient and Remainder Theory • Given any integer n and positive integer d, there exist unique integers q and r, such that n = dq + r and 0 ≤ r < d. (Proof in Sec 4.4.) Definitions Given a nonnegative integer n and a positive integer d, • n div d: the integer quotient when n is divided by d. • n mod d: the integer remainder when n is divided by d. Symbolically, (n div d=q and n mod d =r) ↔ n=dq+r. Definition • The parity of an integer refers to the property of an integer to be even or odd. Definitions (Floor and Ceiling) • For any real number x, the floor of x, written , is the unique integer n such that n ≤ x < n + 1. It is the max of all ints ≤ x. (Symbolically, ) • For any real number x, the ceiling of x, written , is the unique integer n such that n – 1 < x ≤ n. (Symbolically, .) Examples: • If k is an integer, what are and ? • Is the statement true? Methods of Proof Strategies Direct Proof Method of Exhaustion Generalizing from the Generic particular Indirect Proof Proof by Contradiction Proof by Contraposition Cases Proving an existential statement Constructive vs non-constructive proofs of existence Disproving an existential statement (strategies above) Proving a universal statement (strategies above) Disproving a universal statement Counterexample Examples• Show that there is a prime number that can be written as the sum of two perfect squares. • Disprove the following statement: has no non-trivial whole number solutions . (See a counterexample on P.139.) • Prove or Disprove the following statements: For any integers a, b, c: (a | b) → (a | bc). For any integers a, b, c: . Methods of Proof Direct Proof: Express the statement in the form:  Take a particular but arbitrarily chosen x from D so that P(x) is true. Show that the conclusion Q(x) is true based on definitions, previous results , theorems and the rules for logical inference. ExamplesProve the following: • The sum of any two rational numbers is rational. • For all integers a, b and c, if a divides b and b divides c, then a divides c. • Any integer n>1 is divisible by a prime number. ExamplesProve the following: (proof by cases) • Any two consecutive integers have opposite parity. • The square of any odd integer has the form 8m+1 for some integer m. ExamplesProve the following: • For all real numbers x and all integers m,  • For any integer is n/2 for even n and (n– 1)/2 for odd n. • For any nonnegative integer n and any positive integer d, if and , then n = d*q + r and 0 ≤ r < d. Methods of Proof Proof by Contraposition: Express the statement in the form:  Rewrite the statement in the contrapositive form:  Prove the contrapositive by a direct proof: Take a particular but arbitrarily chosen x from D so that Q(x) is false. Show that the conclusion P(x) is false. ExamplesProve the following: • , n is even ↔ n2 is even. Methods of Proof Proof by Contradiction: Suppose that the negation of the statement is true. Show that this supposition leads logically to a contradiction . Conclude that the statement to be proved is true. Examples Prove the following:• is irrational. • There is no integer that is both even and odd. • The sum of any rational number and any irrational number is irrational. • For any integer a and any prime number p, if p | a, then p does not divide (a + 1). • The set of prime numbers is infinite. Common Mistakes Common mistakes in a proof • Arguing from example • Using the same symbol for different variables • Jumping to a conclusion • Begging the question • Misuse of the word if
 Prev Next

Start solving your Algebra Problems in next 5 minutes!      2Checkout.com is an authorized reseller
of goods provided by Sofmath

Attention: We are currently running a special promotional offer for Algebra-Answer.com visitors -- if you order Algebra Helper by midnight of September 17th you will pay only \$39.99 instead of our regular price of \$74.99 -- this is \$35 in savings ! In order to take advantage of this offer, you need to order by clicking on one of the buttons on the left, not through our regular order page.

If you order now you will also receive 30 minute live session from tutor.com for a 1\$!

You Will Learn Algebra Better - Guaranteed!

Just take a look how incredibly simple Algebra Helper is:

Step 1 : Enter your homework problem in an easy WYSIWYG (What you see is what you get) algebra editor: Step 2 : Let Algebra Helper solve it: Step 3 : Ask for an explanation for the steps you don't understand: Algebra Helper can solve problems in all the following areas:

• simplification of algebraic expressions (operations with polynomials (simplifying, degree, synthetic division...), exponential expressions, fractions and roots (radicals), absolute values)
• factoring and expanding expressions
• finding LCM and GCF
• (simplifying, rationalizing complex denominators...)
• solving linear, quadratic and many other equations and inequalities (including basic logarithmic and exponential equations)
• solving a system of two and three linear equations (including Cramer's rule)
• graphing curves (lines, parabolas, hyperbolas, circles, ellipses, equation and inequality solutions)
• graphing general functions
• operations with functions (composition, inverse, range, domain...)
• simplifying logarithms
• basic geometry and trigonometry (similarity, calculating trig functions, right triangle...)
• arithmetic and other pre-algebra topics (ratios, proportions, measurements...)

ORDER NOW!         