Transcript Feb 14 LECTURE FOR 250, NUMBER THEORY

Number Theory
and Techniques of Proof
Basic definitions:Parity
• An integer n is called even if, and only if, there exists an integer k such
that n = 2*k.
• An integer n is called odd if, and only if, it is not even.
• Corollary: An integer n is called odd if, and only if, there exists an
integer k such that n = 2*k + 1
• The property of an integer as being either odd or even is known as its
parity.
Arguing the positive: Universal Statements
• Let’s consider the following statement:
“The sum of an odd and an even integer is odd.”
Arguing the positive: Universal Statements
• Let’s consider the following statement:
“The sum of an odd and an even integer is odd.”
• Do you believe this statement?
Yes
No
Arguing the positive: Universal Statements
• Let’s consider the following statement:
“The sum of an odd and an even integer is odd.”
• Do you believe this statement?
Yes
No
• If you believe it, you have to try to prove that it’s true (argue the
positive/affirmative)
Proof, take 1
• Claim to be proven true (we argue its affirmative):
“The sum of an odd and an even integer is odd.”
• Proof:
• Let 𝑛1 be any odd integer. Then, ∃𝑘 ∈ ℤ 𝑛1 = 2 ⋅ 𝑘 + 1 (1)
• Let 𝑛2 be any even integer. Then, 𝑛2 = 2 ⋅ 𝑘 (2)
• By (1) and (2), we have that
𝑛1 + 𝑛2 = 2 ⋅ 𝑘 + 1 + 2 ⋅ 𝑘 = 2𝑘 + 2𝑘 + 1 = 2 ⋅ 2𝑘 + 1 (3).
• We set 2𝑘 = 𝑟. Clearly, 𝑟 ∈ ℤ. (4)
• Substituting (4) into (3) yields: 𝑛1 + 𝑛2 = 2 ⋅ 𝑟 + 1, which means that 𝑛1 + 𝑛2
is odd.
• End of proof.
Proof, take 1
• Claim to be proven true (we argue its affirmative):
“The sum of an odd and an even integer is odd.”
• Proof:
• Let 𝑛1 be any odd integer. Then, ∃𝑘 ∈ ℤ 𝑛1 = 2 ⋅ 𝒌 + 1 (1)
• Let 𝑛2 be any even integer. Then, 𝑛2 = 2 ⋅ 𝒌 (2)
• By (1) and (2), we have that
𝑛1 + 𝑛2 = 2 ⋅ 𝑘 + 1 + 2 ⋅ 𝑘 = 2𝑘 + 2𝑘 + 1 = 2 ⋅ 2𝑘 + 1 (3).
• We set 2𝑘 = 𝑟. Clearly, 𝑟 ∈ ℤ. (4)
• Substituting (4) into (3) yields: 𝑛1 + 𝑛2 = 2 ⋅ 𝑟 + 1, which means that 𝑛1 + 𝑛2
is odd.
• End of proof.
What does this
WHOOPS!
proof actually
prove?
Proof, take 1
• Claim to be proven true (we argue its affirmative):
“The sum of an odd and an even integer is odd.”
• Proof:
• Let 𝑛1 be any odd integer. Then, ∃𝑘 ∈ ℤ 𝑛1 = 2 ⋅ 𝒌 + 1 (1)
• Let 𝑛2 be any even integer. Then, 𝑛2 = 2 ⋅ 𝒌 (2)
• By (1) and (2), we have that
𝑛1 + 𝑛2 = 2 ⋅ 𝑘 + 1 + 2 ⋅ 𝑘 = 2𝑘 + 2𝑘 + 1 = 2 ⋅ 2𝑘 + 1 (3).
• We set 2𝑘 = 𝑟. Clearly, 𝑟 ∈ ℤ. (4)
• Substituting (4) into (3) yields: 𝑛1 + 𝑛2 = 2 ⋅ 𝑟 + 1, which means that 𝑛1 + 𝑛2
is odd.
• End of proof.
What does this
It proves that two
WHOOPS!
proof actually
prove?
consecutive integers sum
to an odd number!
Proof, take 2
• Claim to be proven true (we argue its affirmative):
“The sum of an odd and an even integer is odd.”
• Proof:
• Let 𝑛1 be any odd integer. Then, ∃𝑘1 ∈ ℤ 𝑛1 = 2 ⋅ 𝑘1 + 1 (1)
• Let 𝑛2 be any even integer. Then, ∃𝑘2 ∈ ℤ [𝑛2 = 2 ⋅ 𝑘2 ] (2)
• By (1) and (2), we have that
𝑛1 + 𝑛2 = 2 ⋅ 𝑘1 + 1 + 2 ⋅ 𝑘2 = 2 ⋅ 𝑘1 + 𝑘2 + 1 (3).
• We set 𝑘1 + 𝑘2 = 𝑘. Clearly, 𝑘 is an integer. (4)
• Substituting (4) into (3) yields: 𝑛1 + 𝑛2 = 2 ⋅ 𝑘 + 1, which means that 𝑛1 + 𝑛2
is odd.
• End of proof.
Statements of claims / theorems
• Mathematical claims and theorems can be stated in various different ways!
“The sum of an odd and an even integer is odd.”
“Any two integers of opposite parity sum to an odd number”
“Every pair of integers of opposite parity sums to an odd number”
∀𝑛1 ∈ ℤ2𝑘+1 [ ∀𝑛2 ∈ ℤ2𝑘
𝑛1 + 𝑛2 ∈ 𝑍 2𝑘+1 ]
Statements of claims / theorems
• Mathematical claims and theorems can be stated in various different ways!
“The sum of an odd and an even integer is odd.”
“Any two integers of opposite parity sum to an odd number”
“Every pair of integers of opposite parity sums to an odd number”
∀𝑛1 ∈ ℤ2𝑘+1 [ ∀𝑛2 ∈ ℤ2𝑘
𝑛1 + 𝑛2 ∈ 𝑍 2𝑘+1 ]
Other
ideas?
Your turn, class!
• Let’s split into teams and prove the following claims true:
1. The square of an odd integer is also odd.
2. If 𝑎 is an integer, then 𝑎2 + 𝑎 is even.
Arguing the affirmative of existential
statements
• Two methods:
1. Constructive
2. Non-Constructive
• In “constructive” proofs we either explicitly show or construct an
element of the domain that answers our query.
• In non-constructive proofs (very rare in this class) we prove that it is a
logical necessity for such an element to exist!
• But we neither explicitly, nor implicitly, show or construct such an element!
Our first constructive proof
• Claim: There exists a natural number that you cannot write as a sum
of three squares of natural numbers.
Constructive proofs in Number
Theory (and one nonconstructive one)
Our first constructive proof
• Claim: There exists a natural number that you cannot write as a sum
of three squares of natural numbers.
• Examples of numbers you can write as a sum of three squares:
• 0 = 02 + 02 + 02
• 1 = 12 + 02 + 02
• 2 = 12 + 12 + 02
• Try to find a number that cannot be written as such.
Proof
• The natural number 7 cannot be written as the sum of three squares.
• This we can prove by case analysis:
1. Can’t use 3, since 32 = 9 > 7
2. Can’t use 2 more than once, since 22 + 22 = 8 > 7
3. So, we can use 2, one or zero times.
a) If we use 2 once, we have 7 = 22 + 𝑎2 + 𝑏 2 ≤ 22 + 12 + 12 = 6 < 7
b) If we use 2 zero times, the maximum value is 12 + 12 + 12 = 3 < 7
Your turn, class!
• Let’s split in teams and prove the following theorems:
1. There exists an integer 𝑛 that can be written in two ways as a sum
of two prime numbers.
2. There is a perfect square that can be written as a sum of two other
perfect squares.
3. Suppose 𝑟, 𝑠 ∈ ℤ. Then, (∃𝑘 ∈ ℤ)[ 22𝑟 + 18𝑠 = 2𝑘]
4. There exists an integer 𝑛 that can be written in two ways as a sum
of two cubed integers. (Hard)
Your turn, class!
• Let’s split in teams and prove the following theorems:
1. There exists an integer 𝑛 that can be written in two ways as a sum
of two prime numbers.
2. There is a perfect square that can be written as a sum of two other
perfect squares.
3. Suppose 𝑟, 𝑠 ∈ ℤ. Then,(∃𝑘 ∈ ℤ)[ 22𝑟 + 18𝑠 = 2𝑘]
4. There exists an integer 𝑛 that can be written in two ways as a sum
of two cubed integers. (Hard)
How is the 3rd proof different from the others?
Our first (and last?) non-constructive proof
• Theorem: There exists a pair of irrational numbers 𝑎 and 𝑏 such that
𝑎𝑏 is a rational number.
• Proof: Let 𝑎 = 𝑏 = 2. Since 2 is irrational, 𝑎 and 𝑏 are both
irrational. Is 𝑎𝑏 = ( 2) 2 rational? Two cases:
1. If 2
2. If 2
2
2
is rational, then we have proven the result. Done.
is irrational, then we will name it 𝑐. Then, observe that 𝑐
2
rational, since 𝑐 =
are irrationals, but 𝑐
2
2
2
2
is
2
= 2 = 2 ∈ ℚ. Since both 𝑐 and 2
2 is rational, we are done.
Divisibility
• Let 𝑛 ∈ ℤ and d ∈ ℤ≠0 . Then, we say or denote any one of the following:
d divides n
n is divided by d
d | n
d is a divisor (or factor) of n
n is a multiple of d
𝑛 ≡ 0 (𝑚𝑜𝑑 𝑑)
if, and only if,
∃𝑘 ∈ ℤ [𝑛 = 𝑑 ⋅ 𝑘]
• We sometimes call k the quotient of the division of n by d.
• If d does not divide n, we denote that by 𝑑 ∤ 𝑦 (note the small
strikethrough)
Pop Quizzes
1. 3 | 6
Yes
No
Pop Quizzes
1. 3 | 6 Y
2. 6 | 3
Yes
No
Pop Quizzes
1. 3 | 6 Y
2. 6 | 3 N
3. 10 | 10
Yes
No
Pop Quizzes
1.
2.
3.
4.
3|6Y
6|3N
10 | 10 Y
-10 ∤ 10
Yes
No
Pop Quizzes
1.
2.
3.
4.
5.
3|6Y
6|3N
10 | 10 Y
-10 ∤ 10 N
5|0
Yes
No
Pop Quizzes
1.
2.
3.
4.
5.
6.
3|6Y
6|3N
10 | 10 Y
-10 ∤ 10 N
5|0Y
0|5
Yes
No
Pop Quizzes
1.
2.
3.
4.
5.
6.
3|6Y
6|3N
10 | 10 Y
-10 ∤ 10 N
5|0Y
0|5N
7. ∀𝑝 ∈ 𝐏, 2 ∤ 𝑝
Yes
No
Pop Quizzes
1.
2.
3.
4.
5.
6.
3|6Y
6|3N
10 | 10 Y
-10 ∤ 10 N
5|0Y
0|5N
7. ∀𝑝 ∈ 𝐏, 2 ∤ 𝑝 N (2 ∈ 𝐏)
8. ∼ ∃𝑛 ∈ ℕ𝑜𝑑𝑑 : 𝑛 | 0
Yes
No
Pop Quizzes
1.
2.
3.
4.
5.
6.
3|6Y
6|3N
Yes
10 | 10 Y
-10 ∤ 10 N
5|0Y
0|5N
7. ∀𝑝 ∈ 𝐏, 2 ∤ 𝑝 N (2 ∈ 𝐏)
8. ∼ ∃𝑛 ∈ ℕ𝑜𝑑𝑑 : 𝑛 | 0 N (any non-zero integer divides 0)
No
Universal claims with divisibility
• Let’s all try to prove the affirmative of this claim:
∀𝑎, 𝑏, 𝑐 ∈ ℤ [((𝑎 ≠ 0) ∧ 𝑎 𝑏) ∧ (𝑎 𝑐 ) ⇒ 𝑎 | 𝑏 + 𝑐 ]
Universal claims with divisibility
• Let’s all try to prove the affirmative of this claim:
∀𝑎, 𝑏, 𝑐 ∈ ℤ
𝑎≠0 ∧ 𝑎 𝑏 ∧ 𝑎 𝑐
⇒𝑎 𝑏+𝑐
• Proof:
1. 𝑎 |𝑏 ⇒ ∃𝑟1 ∈ ℤ 𝑏 = 𝑎 ⋅ 𝑟1
2. 𝑎 |𝑐 ⇒ ∃𝑟2 ∈ ℤ 𝑐 = 𝑎 ⋅ 𝑟2
3. From (1) and (2), we have that 𝑏 + 𝑐 = 𝑎 ⋅ 𝑟1 + 𝑎 ⋅ 𝑟2 = 𝑎 ⋅ (𝑟1 + 𝑟2 )
4. So 𝑎 |(𝑏 + 𝑐).
5. Done.
Proof by contradiction
• Sometimes, proving a fact directly is tough.
• In such cases, we can attempt an indirect proof
• The most common type of indirect proof is proof by contradiction
• Briefly: We want to prove a fact 𝑎, so we assume ∼ 𝑎 and hope that we reach
a contradiction (a falsehood).
• Example: We will prove that if a prime number divides an integer 𝒂, it
cannot possible divide 𝒂 + 𝟏.
Proofs by contradiction in
Number Theory
First proof by contradiction
• Claim: Let 𝑝 ∈ 𝐏, 𝑎 ∈ ℕ. Then, if 𝑝 |𝑎, then 𝑝 ∤ 𝑎 + 1 .
First proof by contradiction
• Claim: Let 𝑝 ∈ 𝐏, 𝑎 ∈ ℕ. Then, if 𝑝 |𝑎, then 𝑝 ∤ 𝑎 + 1 .
• Proof:
• Assume that 𝑝 |(𝑎 + 1). Then, this means that ∃𝑟1 ∈ ℤ 𝑎 + 1 = 𝑝 ⋅ 𝑟1 (I)
• We already know that 𝑝 |𝑎 ⇒ (∃𝑟2 ∈ ℤ)[𝑎 = 𝑝 ⋅ 𝑟2 ] (II)
• Substituting (II) into (I) yields: 𝑝 ⋅ 𝑟2 + 1 = 𝑝 ⋅ 𝑟1 ⇒ 𝑝 𝑟1 − 𝑟2 = 1 ⇒ 𝑝 |1
which is a contradiction. Therefore, 𝑝 ∤ 𝑎 + 1 .
Infinitude of primes
• Assume that the primes are finite. Then, we can list them in
ascending order:
𝑝1 , 𝑝2 , … , 𝑝𝑛
Infinitude of primes
• Assume that the primes are finite. Then, we can list them in
ascending order:
𝑝1 , 𝑝2 , … , 𝑝𝑛
Let’s create the number
𝑁 = 𝑝1 ⋅ 𝑝2 ⋅ … ⋅ 𝑝𝑛 + 1
Infinitude of primes
𝑁 = 𝑝1 ⋅ 𝑝2 ⋅ … ⋅ 𝑝𝑛 + 1
Clearly, 𝑁 is bigger than any 𝑝𝑖 . We have two cases:
i.
ii.
N is prime. Contradiction, since 𝑁 is bigger than any prime.
N is composite. This means that N has at least one factor 𝑓. Let’s take the
smallest factor of N, and call it 𝑓𝑚𝑖𝑛 . Then, this number is prime (why?)
Since 𝑓𝑚𝑖𝑛 is prime, it divides 𝑝1 ⋅ 𝑝2 ⋅ … ⋅ 𝑝𝑛 . By the previous theorem, this
means that it cannot possibly divide 𝑝1 ⋅ 𝑝2 ⋅ … ⋅ 𝑝𝑛 + 1 = 𝑁.
Contradiction, since we assumed that 𝑓𝑚𝑖𝑛 is a factor of N.
Therefore, the primes are not finite.
Modular Arithmetic
Modular Arithmetic
• We say that 𝑎 ≡ 𝑏 𝑚𝑜𝑑 𝑚 (read “a is congruent to b mod m”)
means that 𝑚 |(𝑎 − 𝑏).
• Examples:
• 100 ≡ 2 𝑚𝑜𝑑 7
• 91 ≡ 0 𝑚𝑜𝑑 13
• 6 ≡ 2 𝑚𝑜𝑑 4
• Convention: 0 ≤ 𝑏 ≤ 𝑚 − 1
• THINK: Take large number 𝑎, divide by 𝑚, remainder is 𝑏
• Terminology: “Reducing 𝑎 𝑚𝑜𝑑 𝑚”
≡ vs ≡
• In Logic, 𝜑1 ≡ 𝜑2 mean that 𝜑1 and 𝜑2 have the same truth table
(are logically equivalent)
• In Number Theory, 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚), read “a is congruent to
b mod m”) means 𝑚 | 𝑎 − 𝑏 !
≡ vs ≡
• In Logic, 𝜑1 ≡ 𝜑2 mean that 𝜑1 and 𝜑2 have the same truth table
(are logically equivalent)
• In Number Theory, 𝑎 ≡ 𝑏 (𝑚𝑜𝑑 𝑚), read “a is congruent to
b mod m”) means 𝑚 | 𝑎 − 𝑏 !
• THESE TWO ARE VERY DIFFERENT!!!! THEY HAVE
NOTHING TO DO WITH EACH OTHER!
Properties of equivalence
1. If 𝑎1 ≡ 𝑏1 (𝑚𝑜𝑑 𝑚) and 𝑎2 ≡ 𝑏2 (𝑚𝑜𝑑 𝑚), then:
𝑎1 + 𝑎2 ≡ 𝑏1 + 𝑏2 (𝑚𝑜𝑑 𝑚)
Properties of equivalence
1. If 𝑎1 ≡ 𝑏1 (𝑚𝑜𝑑 𝑚) and 𝑎2 ≡ 𝑏2 (𝑚𝑜𝑑 𝑚), then:
𝑎1 + 𝑎2 ≡ 𝑏1 + 𝑏2 𝑚𝑜𝑑 𝑚
Proof:
•
•
•
•
𝑎1 ≡ 𝑏1 𝑚𝑜𝑑 𝑚 ⇒ 𝑚|(𝑎1 − 𝑏1 )
∃𝑟1 ∈ ℤ [𝑎1 − 𝑏1 = 𝑚 ⋅ 𝑟1 ] (I)
Similarly, ∃𝑟2 ∈ ℤ [𝑎2 − 𝑏2 = 𝑚 ⋅ 𝑟2 ] (II)
Therefore, by (I) and (II) we have:
𝑎1 − 𝑏1 + 𝑎2 − 𝑏2 = 𝑚 ⋅ 𝑟1 + 𝑚 ⋅ 𝑟2 ⇒ 𝑎1 + 𝑎2 − 𝑏1 + 𝑏2 = 𝑚 ⋅ 𝑟1 + 𝑟2 ⇒
𝑎1 + 𝑎2 ≡ 𝑏1 + 𝑏2 (𝑚𝑜𝑑 𝑚)
Properties of equivalence
2. If 𝑎1 ≡ 𝑏1 (𝑚𝑜𝑑 𝑚) and 𝑎2 ≡ 𝑏2 𝑚𝑜𝑑 𝑚 , then
𝑎1 ⋅ 𝑎2 ≡ 𝑏1 ⋅ 𝑏2 𝑚𝑜𝑑 𝑚
Properties of equivalence
2. If 𝑎1 ≡ 𝑏1 (𝑚𝑜𝑑 𝑚) and 𝑎2 ≡ 𝑏2 𝑚𝑜𝑑 𝑚 , then
𝑎1 ⋅ 𝑎2 ≡ 𝑏1 ⋅ 𝑏2 𝑚𝑜𝑑 𝑚
• Proof: For you to figure out. Might be in:
•
•
•
•
•
•
Homework
Quiz
Midterm 1
Midterm 2
Final
Any combination of the above
• How many possibilities are there?
First proof revisited
• Recall that we proved that the sum of an even and an odd integer is
odd.
• Note that:
• If 𝑎 is even (so 2 divides it), then 𝑎 ≡ 0 𝑚𝑜𝑑 2
• If 𝑎 is odd, then 𝑎 ≡ 1 𝑚𝑜𝑑 2
• So now we can re-do the proof with modular arithmetic!
Proof with modular arithmetic
• Claim: Any two integers of opposite parity sum to an odd number.
• Proof:
• Since 𝑎1 , 𝑎2 are opposite parity, without loss of generality, assume that
𝑎1 ≡ 0 𝑚𝑜𝑑 2 and 𝑎2 ≡ 1 (𝑚𝑜𝑑 2)
• Using the properties of modular arithmetic, we obtain:
𝑎1 + 𝑎2 ≡ 0 + 1 𝑚𝑜𝑑 2 ≡ 1 (𝑚𝑜𝑑 2)
• Done.
More proofs
• Similarly, you can show that ∀𝑎 ∈ ℕ [𝑎2 + 𝑎 ≡ 0 ( 𝑚𝑜𝑑 2)]
More proofs
• Similarly, you can show that ∀𝑎 ∈ ℕ [𝑎2 + 𝑎 ≡ 0 ( 𝑚𝑜𝑑 2)]
• Proof: ≡ is ≡ (𝑚𝑜𝑑 2) throughout to save space.
• We have two cases:
1. 𝑎 ≡ 0. Then, 𝑎2 + 𝑎 ≡ 02 + 0 ≡ 0. Done.
2. 𝑎 ≡ 1. Then, 𝑎2 + 𝑎 ≡ 12 + 1 ≡ 0. Done.
Advantages of this notation
• Theorem (clumsy): If 𝑥 is such that when you divide x by 4 you get a
remainder of 2, and 𝑦 is such that when you divide y by 4 you get a
remainder of 3, then when you divide 𝑥 ⋅ 𝑦 by 4 you get a remainder
of 2.
Advantages of this notation
• Theorem (clumsy): If 𝑥 is such that when you divide x by 4 you get a
remainder of 2, and 𝑦 is such that when you divide y by 4 you get a
remainder of 3, then when you divide 𝑥 ⋅ 𝑦 by 4 you get a remainder
of 2.
THIS SOUNDS AWFUL!
Advantages of this notation
• Theorem (clumsy): If 𝑥 is such that when you divide x by 4 you get a
remainder of 2, and 𝑦 is such that when you divide y by 4 you get a
remainder of 3, then when you divide 𝑥 ⋅ 𝑦 by 4 you get a remainder
of 2.
THIS SOUNDS AWFUL!
• Theorem (elegant): If 𝑥 ≡ 2 ( 𝑚𝑜𝑑 4) and 𝑦 ≡ 3 ( 𝑚𝑜𝑑 4), then
𝑥 ⋅ 𝑦 ≡ 2 (𝑚𝑜𝑑 4).
Advantages of this notation
• Theorem (clumsy): If 𝑥 is such that when you divide x by 4 you get a
remainder of 2, and 𝑦 is such that when you divide y by 4 you get a
remainder of 3, then when you divide 𝑥 ⋅ 𝑦 by 4 you get a remainder of 2.
THIS SOUNDS AWFUL!
• Theorem (elegant): If 𝑥 ≡ 2 ( 𝑚𝑜𝑑 4) and 𝑦 ≡ 3 ( 𝑚𝑜𝑑 4), then
𝑥 ⋅ 𝑦 ≡ 2 (𝑚𝑜𝑑 4).
• Proof: All ≡ are mod 4. Then:
𝑥 ⋅ 𝑦 ≡ 2 ⋅ 3 ≡ 6 ≡ 2 (𝑚𝑜𝑑 4)
Proofs by contrapositive in
Number Theory
Proof by contraposition
• Applicable to all kinds of statements of type:
∀𝑥 ∈ 𝐷 [𝑃 𝑥 ⇒ 𝑄 𝑥 ]
Proof by contraposition
• Applicable to all kinds of statements of type:
∀𝑥 ∈ 𝐷 [𝑃 𝑥 ⇒ 𝑄 𝑥 ]
• Sometimes, proving the implication in this way is hard.
• On the other hand, proving its contrapositive might be easier:
• ∀𝑥 ∈ 𝑆 [ ∼ 𝑄 𝑥 ⇒∼ 𝑃 𝑥 ]
Examples
• ∀𝑛 ∈ ℤ 𝑛2 ≡ 0 𝑚𝑜𝑑 2 ⇒ 𝑛 ≡ 0 𝑚𝑜𝑑 2
• Proving this directly is somewhat hard
• On the other hand, the contrapositive is child’s (or 250 student’s)
play: ∀𝑛 ∈ ℤ, [ 𝑛 ≢ 0 (𝑚𝑜𝑑 2) ⇒ 𝑛2 ≢ 0 (𝑚𝑜𝑑 2)]
Examples
• ∀𝑛 ∈ ℤ [𝑛2 ≡ 0 ( 𝑚𝑜𝑑 2) ⇒ 𝑛 ≡ 0 ( 𝑚𝑜𝑑 2)]
• Proving this directly is somewhat hard
• On the other hand, the contrapositive is child’s (or 250 student’s)
play: ∀𝑛 ∈ ℤ, [ 𝑛 ≢ 0 (𝑚𝑜𝑑 2) ⇒ 𝑛2 ≢ 0 (𝑚𝑜𝑑 2)
• Proof: Since 𝑛 ≢ 0 (𝑚𝑜𝑑 2), we have that 𝑛 ≡ 1 𝑚𝑜𝑑 2 . So,
𝑛2 ≡ 12 ≡ 1 (𝑚𝑜𝑑 2)
Another example
• If 𝑛2 ≡ 0 (𝑚𝑜𝑑 5), then 𝑛 ≡ 0 (𝑚𝑜𝑑 5)
Another example
• If 𝑛2 ≡ 0 (𝑚𝑜𝑑 5), then 𝑛 ≡ 0 (𝑚𝑜𝑑 5)
• Proof (contrapositive): 𝑛 ≢ 0 (𝑚𝑜𝑑 5) ⇒ 𝑛2 ≢ 0 (𝑚𝑜𝑑 5)
• Cases (all ≡ are mod 5):
a)
b)
c)
d)
𝑛 ≡ 1 ⇒ 𝑛2 ≡ 1 ≢ 0
𝑛 ≡ 2 ⇒ 𝑛2 ≡ 4 ≢ 0
𝑛 ≡ 3 ⇒ 𝑛2 ≡ 9 ≡ 4 ≢ 0
𝑛 ≡ 4 ⇒ 𝑛2 ≡ 16 ≡ 1 ≢ 0
• Done.
A historical proof by
contradiction
Proof that 2 is irrational
• Let’s assume BY WAY OF CONTRADICTION that 2 is rational.
𝑎
• So 2 = , 𝑎, 𝑏 ∈ ℤ, 𝑏 ≠ 0 and 𝑎, 𝑏 do not have common factors.
𝑏
• So 𝑎 = 2 ⋅ 𝑏 ⇒ 𝑎2 = 2𝑏 2 so 𝑎2 ≡ 0 𝑚𝑜𝑑 2 (1)
• By the previous theorem, this means that 𝑎 ≡ 0 (𝑚𝑜𝑑 2)
• So 𝑎 = 2𝑘 for some integer 𝑘. (2)
• Substituting (2) into (1) yields: 2𝑘 2 = 2𝑏 2 ⇒ 𝑏 2 = 2𝑘 2 ⇒
𝑏 2 ≡ 0 𝑚𝑜𝑑 2 ⇒ 𝑏 ≡ 0(𝑚𝑜𝑑 2)
• So both 𝑎 and 𝑏 are both even, have common factor of 2.
• Contradiction.
Proof that 5 is irrational
• Let’s assume BY WAY OF CONTRADICTION that 5 is rational.
𝑎
• So 5 = , 𝑎, 𝑏 ∈ ℤ, 𝑏 ≠ 0 and 𝑎, 𝑏 do not have common factors.
𝑏
• So 𝑎 = 5 ⋅ 𝑏 ⇒ 𝑎2 = 5𝑏 2 so 𝑎2 ≡ 0 𝑚𝑜𝑑 5 (1)
• By the previous theorem, this means that 𝑎 ≡ 0 (𝑚𝑜𝑑 5)
• So 𝑎 = 5𝑘 for some integer 𝑘. (2)
• Substituting (2) into (1) yields: 5𝑘 2 = 5𝑏 2 ⇒ 𝑏 2 = 5𝑘 2 ⇒
𝑏 2 ≡ 0 𝑚𝑜𝑑 5 ⇒ 𝑏 ≡ 0 (𝑚𝑜𝑑 5)
• So both 𝑎 and 𝑏 are both even, have common factor of 5.
• Contradiction.
Proof that 4 is irrational (???)
• Why can we not use this machinery to prove that 4 is irrational
(which is wrong anyway)?
Using the Unique Factorization
Theorem
Unique Factorization: examples
• 91 = 71 × 131
• There is no other way to factor 91 into a product of primes.
• 18 = 21 × 32
• Once again, no other way to factor 18 into a product of primes.
• 7 = 71
• Since 7 is prime, there is trivially no other way to factor it into primes.
• 1000 = 23 × 53
• 1027: prime or not?
Unique Factorization: examples
• 91 = 71 × 131
• There is no other way to factor 91 into a product of primes.
• 18 = 21 × 32
• Once again, no other way to factor 18 into a product of primes.
• 7 = 71
• Since 7 is prime, there is trivially no other way to factor it into primes.
• 1000 = 23 × 53
• 1027: prime or not? Nope! 1027 = 13 × 79
• 1049 = 10491 (1049 is prime)
Statement of Theorem
• Every number 𝑛 ∈ ℕ≥2 can be uniquely factored into a product of
prime numbers 𝑝1 , 𝑝2 , … , 𝑝𝑛 like so:
𝑛=
𝑒1
𝑝1
⋅
𝑒2
𝑝2
⋅ …⋅
• Proving existence is easy (Jason)
• Proving uniqueness is hard (Bill)
𝑒𝑘
𝑝𝑘 ,
𝑒𝑖 ∈ ℕ≥1
What is “uniqueness”?
• By “uniqueness” we mean that the product is unique up to reordering
𝑒
of the factors 𝑝𝑖 𝑖 .
• Examples:
• 30 = 31 × 101 = 101 × 31
• 88 = 23 × 111 = 111 × 23
• 1026 = 21 × 33 × 191 = 21 × 191 × 33 = 191 × 21 × 33 = 33 × 191 ×
21
Proof of 2 ∉ ℚ with PFT
• Proof (once again by contradiction): Assume that 2 ∈ ℚ, so
∃𝑎 ∈ ℤ, 𝑏 ∈
ℤ≠0
𝑎
[ 2= ]
𝑏
Proof of 2 ∉ ℚ with PFT
• Proof (once again by contradiction): Assume that 2 ∈ ℚ, so
𝑎
∃𝑎 ∈ ℤ, 𝑏 ∈
[ 2= ]
𝑏
Let 𝑘1 ∈ ℕ be the largest integer such that 𝑎 = 2𝑘1 ⋅ 𝐴 (By UPFT)
Similarly, let 𝑘2 ∈ ℕ be the largest integer such that 𝑏 = 2𝑘2 ⋅ 𝐵 (By UPFT)
ℤ≠0
Proof of 2 ∉ ℚ with UFT
• Proof (once again by contradiction):
• Assume that 2 ∈ ℚ, so
∃𝑎 ∈ ℤ, 𝑏 ∈
ℤ≠0
Since 2 =
𝑎
,
𝑏
𝑎
[ 2= ]
𝑏
𝑎2 = 2𝑏 2
Proof of 2 ∉ ℚ with UFT
Since 2 =
•
•
•
•
𝑎
,
𝑏
𝑎2 = 2𝑏 2
Let 𝑘1 ∈ ℕ be the largest integer such that 𝑎 = 2𝑘1 ⋅ 𝐴 ⇒ 𝑎2 = 22𝑘1 ⋅ 𝐴2
Let 𝑘2 ∈ ℕ be the largest integer such that 𝑏 = 2𝑘2 ⋅ 𝐵 ⇒ 𝑏 2 = 22𝑘2 ⋅ 𝐵2
Since 𝑘1 , 𝑘2 are largest ints, 𝐴 and 𝐵 are odd, so 𝐴2 , 𝐵2 odd (we proved this)
𝑎2 = 2𝑏 2 ⇒
𝟐𝟐𝒌𝟏 ⋅ 𝑨𝟐 = 𝟐 ⋅ 𝟐𝟐𝒌𝟐 ⋅ 𝑩𝟐 = 𝟐𝟐𝒌𝟐 +𝟏 ⋅ 𝑩𝟐
• Even number of 2s on left side, odd number of 2s on right
• Contradiction.
Proof of 5 ∉ ℚ with UFT
• Proof (by contradiction)
• Assume that 5 ∈ ℚ ⇒
≠0
∃𝑎 ∈ ℤ, 𝑏 ∈ ℤ
𝑎
5=
⇒ (∃𝑎 ∈ ℤ, 𝑏 ∈ ℤ≠0 )[𝑎2 = 5𝑏 2 ]
𝑏
𝑘
𝑘
• Let 𝑘1 , 𝑘2 ∈ ℤ be the largest integers such that 𝑎 = 5 1 ⋅ 𝐴, 𝑏 = 5 2 ⋅ 𝐵.
• Clearly, 𝐴, 𝐵 ≢ 0 (𝑚𝑜𝑑 5), so 𝐴2 , 𝐵2 ≢ 0 (𝑚𝑜𝑑 5) (make sure you’re convinced)
𝒂𝟐 = 𝟓𝒃𝟐 ⇒ 𝟓𝟐𝒌𝟏 ⋅ 𝑨𝟐 = 𝟓𝟐𝒌𝟐 +𝟏 ⋅ 𝑩𝟐
• Even number of 5s on the left, odd on the right.
• Contradiction.
Proof that 4 ∉ ℚ (???) with UFT
• Why can we not use this machinery to prove that 4 is irrational
(which is wrong anyway)?
Speed of Computations
in Number Theory
Basic assumptions
• 𝑎 + 𝑏 and 𝑎 ⋅ 𝑏 have unit cost
• This is not true if 𝑎, 𝑏 are too large
• Jason: Do you mean > 64 bits or something?
• Bill: Nobody cares, just say “large”.
First problem
• How fast can we compute 𝑎𝑛 𝑚𝑜𝑑 𝑚 𝑛, 𝑚 ∈ ℕ ?
1. Obviously, we can compute 𝑎𝑛 = 𝑎 × 𝑎 × ⋯ × 𝑎 and mod that large
𝑛 𝑡𝑖𝑚𝑒𝑠
number by 𝑚.
First problem
• How fast can we compute 𝑎𝑛 𝑚𝑜𝑑 𝑚 𝑛, 𝑚 ∈ ℕ ?
1. Obviously, we can compute 𝑎𝑛 = 𝑎 × 𝑎 × ⋯ × 𝑎 and mod that large
number by 𝑚.
𝑛 𝑡𝑖𝑚𝑒𝑠
• Is this algorithm
Good
Bad
Ugly
?
First problem
• How fast can we compute 𝑎𝑛 𝑚𝑜𝑑 𝑚 𝑛, 𝑚 ∈ ℕ ?
1. Obviously, we can compute 𝑎𝑛 = 𝑎 × 𝑎 × ⋯ × 𝑎 and mod that large
𝑛 𝑡𝑖𝑚𝑒𝑠
number by 𝑚.
• Is this algorithm
Good
Bad
Ugly
?
Because:
• Jason: Numbers can get
above 32 bits, and that’s
a storage and
computation problem.
• Bill: Numbers get “too
freaking large”.
First problem, second approach
2. We could start computing 𝑎 × 𝑎 × … × 𝑎 until the product
becomes larger than 𝑚, reduce and repeat until we’re done.
First problem, second approach
2. We could start computing 𝑎 × 𝑎 ⋯ × 𝑎 until the product becomes
larger than 𝑚, reduce and repeat until we’re done.
• Is this better?
Yes
No
Something
Else
First problem, second approach
2. We could start computing 𝑎 × 𝑎 × ⋯ × 𝑎 until the product
becomes larger than 𝑚, reduce and repeat until we’re done.
• Is this better?
Yes
No
• We no longer produce huge
numbers!
• However, we still need 𝑛
multiplications.
Something
Else
First problem
• How fast can we compute 𝑎𝑛 𝑚𝑜𝑑 𝑚 𝑛, 𝑚 ∈ ℕ ?
We always
need 𝑛 steps
We can do it in
roughly 𝑛 steps
We can do it in
roughly log𝑛 steps
Something Else
First problem
• How fast can we compute 𝑎𝑛 𝑚𝑜𝑑 𝑚 𝑛, 𝑚 ∈ ℕ ?
We always
need 𝑛 steps
We can do it in
roughly 𝑛 steps
We can do it in
roughly log𝑛 steps
Something Else
Example
• Computing 364 𝑚𝑜𝑑 99 in log 2 64 = 6 steps.
• All ≡ are ≡ (mod 99).
• 31 ≡ 3
• 32 ≡ 9
2
2
• 3 ≡ 32
2
≡ 92 ≡ 81
≡
2
2
3
2
≡
3
2
3
2
≡ 3
24
2
• 32 ≡ 9
2
•
3
2
3
•
4
2
3
•3
25
6
≡ 812 ≡ 27
≡ 272 ≡ 36
≡ 362 ≡ 9
≡ 81
Example
• Computing 364 𝑚𝑜𝑑 99 in log 2 64 = 6 steps.
• All ≡ are ≡ (mod 99).
1.
2.
3.
4.
5.
6.
21
3 ≡9
2
32 ≡ 32
3
32
4
2
3
5
2
3
6
32
≡ 92 ≡ 81
≡
2
32
2
≡
3
2
3
2
4
2
3
2
≡
≡ 9
64
• Aha! 3
2
2
=3
≡ 812 ≡ 27
≡ 272 ≡ 36
≡ 362 ≡ 9
≡ 81
26
≡ 81
Good news, bad news
• Good news: By using repeated squaring, can compute
quickly (roughly ℓ = log 2 2ℓ steps)
• Bad news: What if our exponent is not a power of 2?
ℓ
2
𝑎
𝑚𝑜𝑑 𝑚
Example
• Computing 327 𝑚𝑜𝑑 99 with the same method
• All ≡ are ≡ (mod 99).
• 31 ≡ 3
• 32 ≡ 9
2
2
• 3 ≡ 32
•
3
2
3
•
4
2
3
2
≡ 92 ≡ 81
≡
2
2
3
2
≡
3
2
3
2
≡ 812 ≡ 27
≡ 272 ≡ 36
• 327 = 316 × 38 × 32 × 31 ≡ 36 × 27 × 9 × 3
Example (contd.)
• To avoid large numbers, reduce product as you go:
• 327 = 316 × 38 × 32 × 31 ≡ 36 × 27 × 9 × 3 ≡
36 × 27 × 9 × 3 ≡ 81 × 27 ≡ 9
Algorithm to compute
𝑛
𝑎
𝑚𝑜𝑑 𝑚 in log𝑛 steps
• Step 1: Write 𝑛 = 2𝑞1 + 2𝑞2 + ⋯ + 2𝑞𝑟 , 𝑞1 < 𝑞2 < ⋯ < 𝑞𝑟
𝑞1 +2𝑞2 +⋯+2𝑞𝑟
2
𝑎
𝑎𝑛
• Step 2: Note that
=
=
• Step 3: Use repeated squaring to compute:
20
21
𝑞1
2
𝑎
× ⋯×
𝑞𝑟
2
𝑎
22
𝑎 , 𝑎 , 𝑎 , … , 𝑎𝑞𝑟 𝑚𝑜𝑑 𝑚
using 𝑎
2𝑖+1
≡ 𝑎
𝑞1
2
𝑎
2𝑖
2
𝑚𝑜𝑑 𝑚
• Step 4: Compute
× ⋯×
to avoid large numbers
𝑞𝑟
2
𝑎
mod m reducing when necessary
The key step
• The key step is Step #3: Use repeated squaring to compute:
20
21
22
𝑎 ,𝑎 ,𝑎 ,…,𝑎
using
𝑖+1
2
𝑎
≡
• When computing 𝑎
𝑖
2
𝑎
2𝑖+1
2
2𝑞𝑟
𝑚𝑜𝑑 𝑚
𝑚𝑜𝑑 𝑚
mod m, already have computed 𝑎
2𝑖
2
𝑚𝑜𝑑 𝑚
• Note that all numbers are below 𝑚 because we reduce mod m every step of
the way
• So 𝑎
2𝑖
2
is unit cost and anything mod m is also unit cost!
Second problem: Greatest Common Divisor
(GCD)
• If 𝑎, 𝑏 ∈ ℕ≠0 , then the GCD of 𝑎, 𝑏 is the largest non-zero integer 𝑛
such that 𝑛 |𝑎 and 𝑛 | 𝑏
Second problem: Greatest Common Divisor
(GCD)
• If 𝑎, 𝑏 ∈ ℕ≠0 , then the GCD of 𝑎, 𝑏 is the largest non-zero integer 𝑛
such that 𝑛 |𝑎 and 𝑛 | 𝑏
• What is the GCD of…
• 10 and 15?
Second problem: Greatest Common Divisor
(GCD)
• If 𝑎, 𝑏 ∈ ℕ≠0 , then the GCD of 𝑎, 𝑏 is the largest non-zero integer 𝑛
such that 𝑛 |𝑎 and 𝑛 | 𝑏
• What is the GCD of…
• 10 and 15? 5
• 12 and 90?
Second problem: Greatest Common Divisor
(GCD)
• If 𝑎, 𝑏 ∈ ℕ≠0 , then the GCD of 𝑎, 𝑏 is the largest non-zero integer 𝑛
such that 𝑛 |𝑎 and 𝑛 | 𝑏
• What is the GCD of…
• 10 and 15? 5
• 12 and 90? 6
• 20 and 29?
Second problem: Greatest Common Divisor
(GCD)
• If 𝑎, 𝑏 ∈ ℕ≠0 , then the GCD of 𝑎, 𝑏 is the largest non-zero integer 𝑛
such that 𝑛 |𝑎 and 𝑛 | 𝑏
• What is the GCD of…
•
•
•
•
10 and 15? 5
12 and 90? 6
20 and 29? 1 (20 and 29 are called co-prime or relatively prime)
153 and 181
Second problem: Greatest Common Divisor
(GCD)
• If 𝑎, 𝑏 ∈ ℕ≠0 , then the GCD of 𝑎, 𝑏 is the largest non-zero integer 𝑛
such that 𝑛 |𝑎 and 𝑛 | 𝑏
• What is the GCD of…
•
•
•
•
10 and 15? 5
12 and 90? 6
20 and 29? 1 (20 and 29 are called co-prime or relatively prime)
153 and 181 17
Euclid’s GCD algorithm
• Recall: If 𝑎 ≡ 0 (𝑚𝑜𝑑 𝑚) and 𝑏 ≡ 0 𝑚𝑜𝑑 𝑚 , then 𝑎 − 𝑏 ≡ 0 𝑚𝑜𝑑 𝑚
• The GCD algorithm finds the greatest common divisor by executing this
recursion (assume a > b):
𝐺𝐶𝐷 𝑎, 𝑏 = 𝐺𝐶𝐷 𝑎, 𝑏 − 𝑎
Until its arguments are the same.
Greatest Common Divisor (GCD)
• Recall: If 𝑎 ≡ 0 (𝑚𝑜𝑑 𝑚) and 𝑏 ≡ 0 𝑚𝑜𝑑 𝑚 , then 𝑎 − 𝑏 ≡ 0 𝑚𝑜𝑑 𝑚
• The GCD algorithm finds the greatest common divisor by executing this
recursion (assume a > b):
𝐺𝐶𝐷 𝑎, 𝑏 = 𝐺𝐶𝐷 𝑎, 𝑏 − 𝑎
Until its arguments are the same.
• Question: If we implement this in a programming language, it can only be
done recursively
Yes
(why)
No
(Why)
Something Else
(What)
Greatest Common Divisor (GCD)
• Recall: If 𝑎 ≡ 0 (𝑚𝑜𝑑 𝑚) and 𝑏 ≡ 0 𝑚𝑜𝑑 𝑚 , then 𝑎 − 𝑏 ≡ 0 𝑚𝑜𝑑 𝑚
• The GCD algorithm finds the greatest common divisor by executing this
recursion:
𝐺𝐶𝐷 𝑎, 𝑏 = 𝐺𝐶𝐷 𝑎, 𝑏 − 𝑎
Tail recursion
Until its arguments are the same.
• Question: If we implement this in a programming language, it can only be
done recursively
left = a;
Yes
(why)
No
(Why)
Something Else
(What)
right = b;
while(left != right){
if(left > right)
left = left – right;
else
right = right - left;
}
print "GCD is: " left; // Or right
GCD example
• GCD(18, 100) =
GCD(18, 100 – 18) = GCD(18, 82)=
GCD(18, 82 – 18 = GCD(18, 64) =
GCD(18, 64 – 18) = GCD(18, 46) =
GCD(18, 46 – 18) = GCD(18, 28) =
GCD(18, 28 – 18) = GCD(18, 10) =
GCD(18 - 10, 10) = GCD(8, 10)=
GCD(8, 10 - 8)= GCD(8, 2) =
GCD(8 - 2, 2) = GCD(6, 2) =
GCD(6 - 2, 2) = GCD(4, 2) =
GCD(4- 2, 2) = GCD(2, 2) = 2
GCD example
• GCD(18, 100) =
GCD(18, 100 – 18) = GCD(18, 82)=
GCD(18, 82 – 18 = GCD(18, 64) =
GCD(18, 64 – 18) = GCD(18, 46) =
GCD(18, 46 – 18) = GCD(18, 28) =
GCD(18, 28 – 18) = GCD(18, 10) =
GCD(18 - 10, 10) = GCD(8, 10)=
GCD(8, 10 - 8)= GCD(8, 2) =
GCD(8 - 2, 2) = GCD(6, 2) =
GCD(6 - 2, 2) = GCD(4, 2) =
GCD(4- 2, 2) = GCD(2, 2) = 2
Given integers 𝑎, 𝑏 with 𝑎 > 𝑏 (without loss of
generality), approximately how many steps does
this algorithm take?
a steps
b steps
a-b steps
Something Else
GCD example
• GCD(18, 100) =
GCD(18, 100 – 18) = GCD(18, 82)=
GCD(18, 82 – 18 = GCD(18, 64) =
GCD(18, 64 – 18) = GCD(18, 46) =
GCD(18, 46 – 18) = GCD(18, 28) =
GCD(18, 28 – 18) = GCD(18, 10) =
GCD(18 - 10, 10) = GCD(8, 10)=
GCD(8, 10 - 8)= GCD(8, 2) =
GCD(8 - 2, 2) = GCD(6, 2) =
GCD(6 - 2, 2) = GCD(4, 2) =
GCD(4- 2, 2) = GCD(2, 2) = 2
Given integers 𝑎, 𝑏 with 𝑎 > 𝑏 (without loss of
generality), approximately how many steps does
this algorithm take?
a steps
a-b steps
b steps
Something Else
Roughly
𝑎
𝑏
Can we do better?
• GCD(18, 100) =
GCD(18, 100 – 18) = GCD(18, 82)=
GCD(18, 82 – 18 = GCD(18, 64) =
GCD(18, 64 – 18) = GCD(18, 46) =
GCD(18, 46 – 18) = GCD(18, 28) =
GCD(18, 28 – 18) = GCD(18, 10) =
GCD(18 - 10, 10) = GCD(8, 10)=
GCD(8, 10 - 8)= GCD(8, 2) =
GCD(8 - 2, 2) = GCD(6, 2) =
GCD(6 - 2, 2) = GCD(4, 2) =
GCD(4- 2, 2) = GCD(2, 2) = 2
Yes
No
Something
Else
Can we do better?
• GCD(18, 100) =
Yes
No
Something
Else
GCD(18, 100 – 18) = GCD(18, 82)=
GCD(18, 82 – 18 = GCD(18, 64) =
GCD(18, 64 – 18) = GCD(18, 46) =
GCD(18, 100 – 5 x 18)
GCD(18, 46 – 18) = GCD(18, 28) =
GCD(18, 28 – 18) = GCD(18, 10) =
GCD(18, 100) =
GCD(18, 100 – 5 x 18) = GCD(18, 10) =
GCD(18 - 10, 10) = GCD(8, 10)=
GCD(18 – 10, 10) = GCD(8, 10) =
GCD(8, 10 - 8)= GCD(8, 2) =
GCD(8, 10 - 8) = GCD(8, 2) =
GCD(8 - 2, 2) = GCD(6, 2) =
GCD(8 – 3 x 2, 2) = GCD(2, 2) = 2
GCD(8 – 3 x 2, 2)
GCD(6 - 2, 2) = GCD(4, 2) =
GCD(4- 2, 2) = GCD(2, 2) = 2
From 10 to 4 steps!
How fast is this new algorithm?
• Given non-zero integers 𝑎, 𝑏 with 𝑎 > 𝑏, roughly how many steps
does this new algorithm take to compute GCD(a, b)?
𝑎
𝑏2
𝑎
loga
Something Else
How fast is this new algorithm?
• Given non-zero integers 𝑎, 𝑏 with 𝑎 > 𝑏, roughly how many steps does
this new algorithm take to compute GCD(a, b)?
𝑎
𝑏2
𝑎
• In fact, it takes log 𝜙 𝑎, where 𝜙 =
loga
1+ 5
2
Something Else
is the golden ratio.
• Proof by Gabriel Lamé in 1844, considered to be the first ever result in
Algorithmic Complexity theory.