Proof Techniques in Number Theory

 
1
 
Methods of Proof
Methods of Proof
 
Proof techniques in this handout
Direct proof
Division into cases
Proof by contradiction
 
In this handout, the proof techniques will be
used to prove properties in number theory.
 
2
 
Even and Odd Integers
Even and Odd Integers
 
Definition:
 An integer n
 
 
 is 
even
 iff
  
   
 an integer k 
such that
 n=2k
;
 
 
 is 
odd
 iff
  
   
 an integer k 
such that
 n=2k+1
.
 
Ex:
 If x and y are integers,
    
is                     even or odd?
 
3
 
Method of Direct Proof
Method of Direct Proof
 
To prove a statement: 
x
D if P(x) then Q(x).
 
Suppose
 x is a 
particular
 but 
arbitrarily
 
     
 
    chosen
 element of D
    
     
for which
 P(x) is true;
Show
 the conclusion Q(x) is true by using
   
    ♦ definitions;
   
    ♦ previously established results;
  
      
 
    ♦ rules of logical inference.
Method of Direct Proof (Ex.)
Method of Direct Proof (Ex.)
 
S
h
o
w
 
 
x
Z
 
 
i
f
 
 
x
 
i
s
 
o
d
d
    
  
then
 
3x+9 is even
.
Proof:
 Suppose x is an arbitrarily chosen odd integer.
  
  
Then
 x=2k+1 for some integer k.  
(
by definition
)
  
  
So
 3x+9 = 3(2k+1)+9   
(
by substitution
)
   
      = 6k+3+9       
(
by distributive law
)
 
 
 
 
 
 
=
 
2
(
3
k
+
6
)
 
 
 
 
 
 
 
(
b
y
 
f
a
c
t
o
r
i
n
g
 
o
u
t
 
a
 
2
)
 
 
 
 
 
 
 
(
*
)
 
 
 
3
k
+
6
 
i
s
 
a
n
 
i
n
t
e
g
e
r
.
 
 
 
(
*
*
)
  
   
Hence
 3x+9 is even
  
      
based on (*), (**) and definition of even integers
.
        
     
    
       (
this is what we needed to show
)
 
5
 
Directions for writing proofs
Directions for writing proofs
 
1)
Write 
the
 theorem
 to be proved.
2)
Clearly mark the 
beginning of your proof
 
with the word 
Proof
.
3)
  Make your proof 
self-contained
.
  
(Identify all variables used in the proof;
  
  state the sources of outside facts).
4)
  Write proofs in 
complete English
      
sentences
.
6
Common mistakes in proofs
Common mistakes in proofs
 
Arguing from examples
Using same letter
   
to mean two different things
Jumping to a conclusion
  
(without adequate reasons)
7
Types of Mathematical
Types of Mathematical
Statements
Statements
 
Theorems:
 Very important statements that
  
have many and varied consequences.
Propositions:
 Less important and
    
consequential.
Corollaries:
 The truth can be deduced
  
  almost immediately
    
from other statements.
Lemmas:
 Don
t have much intrinsic interest
   
but help to prove other
theorems.
8
Divisibility
Divisibility
 
D
e
f
i
n
i
t
i
o
n
:
 
F
o
r
 
n
,
d
 
Z
 
a
n
d
 
d
0
 
w
e
 
s
a
y
 
t
h
a
t
n
 
i
s
 
d
i
v
i
s
i
b
l
e
 
b
y
 
d
 
 
 
i
f
f
 
n
=
d
·
k
 
f
o
r
 
s
o
m
e
 
k
 
Z
 
.
Alternative ways to say:
 
 
n is a multiple of d 
,  
d is a factor of n  
,
 
 
d is a divisor of n   
,  
d divides n 
.
Notation:  
d | n
 .
Examples:  6|48,  5|5, -4|8, 7|0, 1|9 .
9
Properties of Divisibility
Properties of Divisibility
 
F
o
r
 
x
Z
,
 
 
1
|
x
 
.
 
F
o
r
 
x
Z
 
s
.
t
.
 
x
0
,
 
 
x
|
0
 
.
 
F
o
r
 
a
,
b
,
c
Z
,
 
i
f
 
a
|
b
 
a
n
d
 
a
|
c
 
t
h
e
n
 
a
|
(
b
+
c
)
 
.
 
T
r
a
n
s
i
t
i
v
i
t
y
:
 
F
o
r
 
a
,
b
,
c
Z
,
    
  
if
 a|b and b|c  
then
 a|c .
10
Quotient-Remainder Theorem
Quotient-Remainder Theorem
 
T
h
e
o
r
e
m
:
 
F
o
r
 
 
n
Z
 
a
n
d
 
d
Z
+
 
 
!
 
 
 
q
,
r
Z
 
 
 
s
u
c
h
 
t
h
a
t
     
n=d
·q+r
  and  
0≤r<d
.
q
 is called 
quotient
; 
r
 is called 
remainder
.
Notation:
 
q = n 
div
 d
;  
r = n 
mod
 d
.
Examples:
  1) 
53 = 8·6+5. 
Hence
    
53 div 8 = 6; 53 mod 8 = 5.
   
      
2)
  
-29 = 7·(-5)+6.
 
Hence
    
-29 div 7 = -5; -29 mod 7 = 6.
11
Example of using div and mod
Example of using div and mod
 
Last year Halloween was on Tuesday.
 
Q.:
 What day is Halloween this year?
 
Solution: 
There are 366 days between
    
10/31/23 and 10/31/24.
   
  366 
mod
 7 = 2.
  
Thus
, 
if
 10/31/23 was Tuesday
    
then
 10/31/24 is Thursday.
12
Proof Technique:
Proof Technique:
Division into Cases
Division into Cases
 
Suppose at some stage of a proof
  
● we know that
   
A
1
 or A
2
 or A
3
 or … or A
n 
is true;
  
● want to deduce a conclusion C.
Use 
division into cases
:
  
Show A
1
→C, A
2
→C, …, A
n
→C.
  
Conclude that C is true.
13
Division into Cases: Example
Division into Cases: Example
 
P
r
o
p
o
s
i
t
i
o
n
:
 
I
f
 
 
n
Z
 
 
s
u
c
h
 
t
h
a
t
n
e
i
t
h
e
r
 
o
f
 
2
 
o
r
 
3
 
d
i
v
i
d
e
 
n
,
 
 
 
 
 
(
1
)
t
h
e
n
 
 
n
2
 
m
o
d
 
1
2
 
 
=
 
 
1
.
 
 
 
 
 
(
2
)
P
r
o
o
f
:
 
S
u
p
p
o
s
e
 
n
Z
 
s
.
t
.
 
n
e
i
t
h
e
r
 
o
f
 
2
 
o
r
 
3
 
d
i
v
i
d
e
 
n
.
  
By quotient-remainder theorem
,
   
exactly one of the following is true:
  
    
a)
 
n=6k
, 
b)
 
n=6k+1
, 
c)
 
n=6k+2
,  
d)
 
n=6k+3
,
 
 
 
 
e
)
 
n
=
6
k
+
4
,
 
 
f
)
 
n
=
6
k
+
5
 
 
 
 
f
o
r
 
s
o
m
e
 
i
n
t
e
g
e
r
 
k
.
 
 
 
 
 
 
 
 
 
(
3
)
  
n can
t be 6k, 6k+2 or 6k+4 
because
i
n
 
t
h
a
t
 
c
a
s
e
 
2
 
|
 
n
 
 
(
w
h
i
c
h
 
c
o
n
t
r
a
d
i
c
t
s
 
(
1
)
 
)
.
 
 
 
 
 
(
4
)
  
n can
t be 6k+3 because in that case 3 | n
(
w
h
i
c
h
 
c
o
n
t
r
a
d
i
c
t
s
 
(
1
)
 
)
.
 
 
 
 
 
 
(
5
)
Division into Cases:
Division into Cases:
Example(cont.)
Example(cont.)
 
Proof(cont.):
  
Based on (3), (4) and (5),
     
either n=6k+1 or n=6k+5.
  Let
s show 
(2)
 for each of these two cases.
 
 
C
a
s
e
 
1
:
 
 
S
u
p
p
o
s
e
 
n
=
6
k
+
1
.
 
  
Then
 n
2 
= (6k+1)
2
=36k
2
+12k+1  (
by basic algebra
)
 
 
 
 
 
 
 
 
=
 
1
2
(
3
k
2
+
k
)
+
1
 
 
 
 
 
 
 
 
 
(
6
)
 
   
Let
 p=3k
2
+k.  
Then
 p is an integer.
 
   n
2 
= 12p+1 .  ( 
by substitution in (6) 
)
 
   
Hence
 
n
2
 mod 12 = 1
 
by quotient-remainder th-m
.
 
 
 
C
a
s
e
 
2
:
 
S
u
p
p
o
s
e
 
n
=
6
k
+
5
.
 
 
(
e
x
e
r
c
i
s
e
)
 
 
 
 
 
 
 
 
15
Method of Proof by Contradiction
Method of Proof by Contradiction
 
1.
Suppose the statement to be proved is false.
2.
Show that this supposition logically leads to a
contradiction.
3.
Conclude that the statement to be proved is true.
 
Example of proof by contradiction.
Theorem:
 There is no greatest integer.
 
The 
proof
 on the board.
 
We will see several contradiction proofs in graph
theory.
Slide Note
Embed
Share

Explore methods of proof, such as direct proof and proof by contradiction, to establish properties in number theory. Learn about even and odd integers, the method of direct proof, writing proofs effectively, common mistakes to avoid, and types of mathematical statements like theorems, propositions, corollaries, and lemmas. Delve into divisibility concepts in number theory.

  • Proof Techniques
  • Number Theory
  • Direct Proof
  • Even and Odd Integers
  • Mathematical Statements

Uploaded on Sep 28, 2024 | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript


  1. Methods of Proof Proof techniques in this handout Direct proof Division into cases Proof by contradiction In this handout, the proof techniques will be used to prove properties in number theory. 1

  2. Even and Odd Integers Definition: An integer n is even iff an integer k such that n=2k; is odd iff an integer k such that n=2k+1. Ex: If x and y are integers, is even or odd? 7 2 4 + xy x 2 2

  3. Method of Direct Proof To prove a statement: x D if P(x) then Q(x). Suppose x is a particular but arbitrarily chosen element of D for which P(x) is true; Show the conclusion Q(x) is true by using definitions; previously established results; rules of logical inference. 3

  4. Method of Direct Proof (Ex.) Show x Zif x is odd Proof: Suppose x is an arbitrarily chosen odd integer. Then x=2k+1 for some integer k. (by definition) So 3x+9 = 3(2k+1)+9 (by substitution) = 6k+3+9 (by distributive law) = 2(3k+6) (by factoring out a 2) (*) 3k+6 is an integer. Hence 3x+9 is even based on (*), (**) and definition of even integers. (this is what we needed to show) then 3x+9 is even. (**)

  5. Directions for writing proofs 1) Write the theorem to be proved. 2) Clearly mark the beginning of your proof with the word Proof. 3) Make your proof self-contained. (Identify all variables used in the proof; state the sources of outside facts). 4) Write proofs in complete English sentences. 5

  6. Common mistakes in proofs Arguing from examples Using same letter to mean two different things Jumping to a conclusion (without adequate reasons) 6

  7. Types of Mathematical Statements Theorems: Very important statements that have many and varied consequences. Propositions: Less important and consequential. Corollaries: The truth can be deduced almost immediately from other statements. Lemmas: Don t have much intrinsic interest but help to prove other theorems. 7

  8. Divisibility Definition: For n,d Z and d 0 we say that n is divisible by d iffn=d k for some k Z . Alternative ways to say: n is a multiple of d , d is a factor of n , d is a divisor of n , d divides n . Notation: d | n . Examples: 6|48, 5|5, -4|8, 7|0, 1|9 . 8

  9. Properties of Divisibility For x Z, 1|x . For x Zs.t. x 0, x|0 . For a,b,c Z, if a|b and a|c then a|(b+c) . Transitivity: For a,b,c Z, if a|b and b|c then a|c . 9

  10. Quotient-Remainder Theorem Theorem: For n Z andd Z+ ! q,r Z such that n=d q+r and 0 r<d. q is called quotient; r is called remainder. Notation: q = n div d; r = n mod d. Examples: 1) 53 = 8 6+5. Hence 53 div 8 = 6; 53 mod 8 = 5. 2)-29 = 7 (-5)+6.Hence -29 div 7 = -5; -29 mod 7 = 6. 10

  11. Example of using div and mod Last year Halloween was on Tuesday. Q.: What day is Halloween this year? Solution: There are 366 days between 10/31/23 and 10/31/24. 366 mod 7 = 2. Thus, if 10/31/23 was Tuesday then 10/31/24 is Thursday. 11

  12. Proof Technique: Division into Cases Suppose at some stage of a proof we know that A1 or A2 or A3or or An is true; want to deduce a conclusion C. Use division into cases: Show A1 C, A2 C, , An C. Conclude that C is true. 12

  13. Division into Cases: Example Proposition: If n Z such that Proof: Suppose n Z s.t. neither of 2 or 3 divide n. By quotient-remainder theorem, exactly one of the following is true: a) n=6k, b) n=6k+1, c) n=6k+2, d) n=6k+3, e) n=6k+4, f) n=6k+5 for some integer k. (3) n can t be 6k, 6k+2 or 6k+4 because in that case 2 | n (which contradicts (1) ). (4) n can t be 6k+3 because in that case 3 | n (which contradicts (1) ). neither of 2 or 3 divide n, then n2 mod 12 = 1. (1) (2) (5) 13

  14. Division into Cases: Example(cont.) Proof(cont.): Based on (3), (4) and (5), Let s show (2) for each of these two cases. Case 1: Suppose n=6k+1. Then n2 = (6k+1)2=36k2+12k+1 (by basic algebra) = 12(3k2+k)+1 Let p=3k2+k. Then p is an integer. n2 = 12p+1 . ( by substitution in (6) ) Hence n2 mod 12 = 1 by quotient-remainder th-m. Case 2: Suppose n=6k+5. (exercise) either n=6k+1 or n=6k+5. (6)

  15. Method of Proof by Contradiction 1. Suppose the statement to be proved is false. 2. Show that this supposition logically leads to a contradiction. 3. Conclude that the statement to be proved is true. Example of proof by contradiction. Theorem: There is no greatest integer. The proof on the board. We will see several contradiction proofs in graph theory. 15

More Related Content

giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#