Transcript 01-NumberTheoryslides

Number Theory
Number Theory: A reflection of the
basic mathematical endeavor.
Exploration Of Patterns: Number theory
abounds with patterns and requires little
background to understand questions.
• Inductive Reasoning: Patterns are
discovered and generalized.
• Deductive Reasoning: Patterns are
formalized and verified with proof.
Pythagoras of Samos
Born: about 569 BC in Samos,
Ionia
Died: about 475 BC
Pythagorean Society
• 4000 years ago: Traders, calender makers
and surveyors used large natural
numbers.
• 500 B.C: Pythagorean school considered
the natural numbers to be the key to
understanding the universe.
-Basis of philosophy and religion
-Imparted to them humanistic and
mystic properties.
• Natural numbers were their friends,
associates, tools and enemies.
• Applied adjectives associated with people
such as friendly, perfect, natural, rational.
• Disintegration of school almost occurred
when they discovered that not all physical
quantities were expressible as ratios of
natural numbers.
• Discovery of 2 as irrational number
1
2
1
Perfect Numbers
• A natural number is perfect if it is the sum
of its divisors.
• Ancient Greeks knew 4 perfect numbers
and endowed them with mystic properties.
• 6=3+2+1
• Greek numerology considered 6 the most
beautiful of all numbers, representing
marriage, health and beauty – since it was
the sum of its own parts.
• 6 represented the goddess of love Venus
for it is the product of 2, which represents
female, and 3, which represents male.
• God created the world in 6 days.
• 28 = 14 + 7 + 4 + 2 + 1
• Cycle of moon is 28 days.
• Show that 496 and 8128 are the next two
perfect numbers.
Perfect Number Characteristics
•
•
•
•
Are there infinitely many perfect numbers?
Is every perfect number even?
Do all perfect numbers end in 6 or 8?
Is there a formula for generating perfect
numbers?
Are there infinitely many perfect numbers?
• Not Known – unsolved problem
• Only 24 known perfect numbers.
• Cataldi (1603 ) - 5th through 7th
33, 550, 336
8, 589, 869, 056
137, 438, 691, 328
• Euler (1772) – 8th perfect number
2, 305, 483, 008, 139, 952, 128
Do all perfect even numbers end in 6 or 8?
• Not known if any odd perfect numbers
exist.
• Proven all perfect number that are even do
end in 6 or 8.
Perfect Number Form
• An even perfect number must have the
form 2p-1(2p-1) where 2p – 1 is prime.
• Mersenne Primes – primes of form 2p - 1.
Perfect Numbers related to
Mersenne Primes
•
•
•
•
•
•
•
•
•
6 = 2(22 – 1)
28 = 22(23-1)
496 = 24(25-1)
8128= 26(27-1)
212(213-1)
216(217-1)
218(219-1)
230(231-1)
Largest Know Perfect Number is 219936(219937-1)
Leopold Kronecker
Born: 7 Dec 1823 in Liegnitz,
Prussia (now Legnica, Poland)
Died: 29 Dec 1891 in Berlin,
Germany
Leopold Kronecker(1823-1891)
• God made the integers, all the rest is the
work of man.
• All results of the profoundest mathematical
investigation must ultimately be expressed
in the simple form of properties of integers.
Johann Carl Friedrich
Gauss
Born: 30 April 1777 in
Brunswick, Duchy of Brunswick
(now Germany)
Died: 23 Feb 1855 in Göttingen,
Hanover (now Germany)
Karl Friedrich Gauss(1777-1855)
• Mathematics is the queen of sciences and
number theory is the queen of
mathematics.
Leonhard Euler
Born: 15 April 1707 in Basel,
Switzerland
Died: 18 Sept 1783 in St
Petersburg, Russia
Leonard Euler (1707-1783)
• There are even many properties of the
numbers with which we are well
acquainted, but which we are not yet able
to prove – only observations have led us
to their knowledge.
Famous Number Theory
Conjectures
• Goldbach’s Conjecture: Every even
number greater than 4 can be expressed
as the sum of two odd primes.
• Twin Prime Conjectures: There is an
infinite number of pairs of primes whose
difference is two.
Goldbach’s Conjecture
• Examine the first several cases
– Easy to understand question
– Difficult to prove
•
•
•
•
•
6=3+3
8=3+5
10 = 3 + 7
12 =5 + 7
Try some larger even numbers
Pierre de Fermat
Born: 17 Aug 1601 in
Beaumont-de- Lomagne, France
Died: 12 Jan 1665 in Castres,
France
Fermat’s Last Theorem
There are no non-zero whole numbers a, b,
c where a n + b n = c n for n a whole
number greater than 2.
• Extension of Pythagorean Theorem
a2+b2 =c2
• Pythagorean triples (3,4,5), (5,12,13)
• Try letting n = 3 and finding cases that
work. Use the TI-73 to explore.
Divides
• If a, b  Z with a  0, then a divides b if
there exists a c  Z such that a  c = b.
• Notation: a | b a divides b
b is a multiple of a
a is a divisor of b
a | b a does not divide b
Properties Of Divides
•
•
•
•
•
•
•
a  0 then a | 0 and a | a.
1 | b for all b  Z.
If a | b then a | b·c for all c  Z.
Transitivity: a | b and b | c implies a | c.
a | b and a | c implies a | (bx+cy), x,y  Z.
a | b and b  0 implies |a| |b|.
a | b and b | a implies a =b
Proof of Divide Property
• a | b and a | c implies a | (bx+cy), x,y  Z
• Proof:
Divisibility Rules for 2, 5, and10
• Rule for 2: If n is even, then 2 | n
• Rule for 5: If n has a ones digit of 0 or
5, then 5 | n.
• Rule for 10: If n has a ones digit of 0, then
10 | n.
Proof of Divisibility by 5
• Proof: Let n be an integer ending in 0 or 5.
Write n out in expanded notation and
verify that 5 divides n.
Divisibility Rules For 3, 6 and 9
• Rule for 3: If 3 divides the sum of the digits
of n, then 3 | n.
• Rule for 6: If 2 | n and 3 | n, then 6 | n.
• Rule for 9: If 9 divides the sum of the digits
of n, then 9 | n.
Exploration of Divisibility by 3
• 3 | (2+1+ 6) so 3 | 216.
• Expand 216 = 2100 + 110 + 6.
• Convert to terms divisible by 3.
Proof of Divisibility by 3
• Proof: Show for 3 digit number, then
expand to higher cases
Principle Of Mathematical Induction
Let S(n) be a statement involving the
integers n. Suppose for some fixed integer
no two properties hold:
• Basis Step: S(no) is true;
• Induction Step: If S(k) is true for k  Z
where k no ,then S(k+1) is true.
• THEN S(n) is true for all nZ , n  n0
Mistaken Induction?
• Prove: an = 1 for any n  Z+ {0},
a  Real, a  0.
Proof: Basis Step: a o = 1 so true for n = 0
Induction Step: Suppose for some integer k
that a k = 1 then
ak+1 = a k a k / ak-1 = (1  1)/1 = 1
By induction an = 1.
• What is the error in this argument?
Math Induction Proof
Divisibility by 3
• Proof: Let n be any integer such that the
sum of its digits is divisible by 3.
Exploration
• Use the rule for divisibility by 3 to prove
the rules for 6 and 9.
Divisibility Rules for 4, 8 and 12
• Rule for 4: If 4 divides the last 2 digits of n,
then 4 | n.
• Rule for 8: If 8 divides the last 3 digits of n,
then 8 | n.
• Rule for 12: If 3 | n and 4 | n, then 12 | n.
Exploration
• Parallel the argument for divisibility by 3 to
prove divisibility by 4.
• Divisibility by 8 and 12 follow from the
divisibility by 4.
Divisibility Rules for 7,11 and 13
• Rule for 7: If 7 divides the alternating
sum/difference of 3 successive digits then
7 | n.
• Rule for 11: If 11 divides the alternating
sum/difference of 3 successive digits then
11 | n.
• If 13 divides the alternating sum/difference
of 3 successive digits, then 13 | n.
Example
• Does 7 divide 515, 592?
• 592 – 515 = 77
Since 7 | 77, then 7 | 515,592
• Try 1,516,592
Proof of Divisibility by 7
• Proof: Argue for 6 digit number and use
Math Induction to verify generalization
Prime Numbers
• Prime Number: If p is an integer, p > 1,
and p has only 2 positive integer divisors,
then p is called a prime number.
• Composite Number: If p > 1 and p is not
prime, then p is called a composite
number.
Fundamental Theorem Of
Arithmetic
• Every integer n  2 is either prime or can
be factored into a product of primes.
• Prove requires a stronger form of
Mathematical Induction
Strong Principle Of Mathematical
Induction
• Let S(n) be a statement involving the
integer n. Suppose for some fixed integer
n0.
• Basis Step: S(n0) is true
• Induction Step: If S(n0), S(n0+1)…S(k) are
true for k  Z , k  n0 then S(k+1) is true.
• THEN S(n) is true for all integers n  n0
Proof of FTA
• Proof: Use Strong Math Induction
Sieve of Eratosthenes
• Finds primes up to n from knowledge of
primes up to n
• Easy to implement in a graphical form
Thank You !!