MATHEMATICS
week 5
TERM TEST 1 THIS FRIDAY:
Test 1 Friday Feb. 10, 5-7 pm. various locations; information posted
Early seating: 3:30-5:00, BA 1210
Details will be communicated to those who apply (later this evening, Wed.)
Help hours: myself Tues and Thurs 3:30-4:30,
Oliver: Wed. 1:30-2:30 zoom
Aidan: Friday (see announcement) zoom
Esmeralda: Friday PG 2:30-3:30
WHAT IS A ROW OF THE MULTIPLICATION TABLE?
Which is the row in front 2 ?
Which is the row corresponding to 3?
The nature of these rows are discussed in the
tutorial document.
And will also appear in the test.
FEEDBACKS ARE OUT
General comment:
“Approaches are too mechanical” (not enough soul, not enough intuitive understanding) , and
“often people have memorized a cliché argument, from beginning to end” (lack of analytical thinking)
Lecture quiz 2: for a given > 1, assume all natural numbers 1 < < have a prime divisor, prove must have a prime divisor as well.
Marker’s comments:
“Probably at least half went through an entire induction proof, and proved the statement for n+1
rather than n. Some were trying to use the statement for n to prove it for n+1, which no one did
successfully. That's why they need complete induction... ”
PMI VS PCMI
PS1 Q7 was specifically asking to use PCMI, but majority did make the assumption of
PCMI, but didn’t use it; instead, they presented a proof by PMI.
The proof of PMI was harder and longer, less intuitive, and common in the literature,
so many students’ proofs were similar !
The power of PCMI was tested in Q7: a stronger principle can make the argument a
bit shorter, more intuitive and more efficient.
PS1 QUESTIONS 3C AND 4B
Q 3c:
“Students needed to recognize that one cannot use properties of normal arithmetic on
fractions because those properties rely in this very proof, as well as the next few parts.
So students who “divided by m on both sides” or attempted a similar operation without
reference to a cancellation law lost marks. The most common error, however, was failing
to cite the UNIQUENESS of the solution n/m to the equation mx=n. Without this
uniqueness you cannot conclude that two solutions to the equation are equal.”
Q 4b: “most people eliminated 0,2,4,6,8,5. Many tried to eliminate 1 and 9 separately,
I think it is hard to do that clearly, more or less they lost a portion of marks for logical
errors.”
COMMENTS ON Q2 AND Q8 ARE YET TO ARRIVE
CONCLUSION OF FEEDBACK COMMENTS
The plan is to keep on proving very easy facts as part of a `theory toolbox’ in order to:
1. prove ideas, and to add them as theorems to enrich the theory
2. apply theory to simplify computation (be aware of smallest pieces of `theory’; they
form a logical structure for making decision at the time of computation.)
3. gradually connecting our arguments to our intuitive knowledge (the soul of our
knowledge)
Please carefully read the questions, understand the logical structure, and answer as
simple and as focused as possible by using your own intuitive knowledge, and
Avoid the desire to make things complicated: memorizing big structures and mindlessly
copying them down as answers, thinking that you have written something formal. The
proofs must be yours!
TYPE OF UNIVERSITY EDUCATION
Longer lasting Skills vs memorizing well prepared packages of information
Reflective and analytical skills
Theory building, and using of theory for practical problem solving
Gradually connecting the intuitive knowledge to formal presentation
This means establishing a healthy channel between
‘the thinking you’ and ‘your audience’
TERM TEST 1: EXPECTATIONS
Type of questions:
short arguments, very close to the definitions, statements of the theorems, and basic
properties; make sure to have a practical understanding of definitions and basic
facts about various concepts.
Steps of a proof are asked in an earlier question, so be aware of the whole page,
not a single question.
Arguments cut from a larger proof; a larger argument is made of smaller pieces;
learn them that way.
use of theory to do computations instead of brute force.
Theory is being developed in the same paper; use it.
THEME OF THIS WEEK’S TUTORIALS: SOLVING EQUATIONS
Solving ≡ ( ):
Infancy: (chapter 3) use multiplication table! This way of solving equation is by consulting the
multiplication tables.
High school: using basic Algebra:
Cancellation Law: (chapter 4, for mod prime) solve the equation by repeated cancellation, and
repeatedly changing numbers in mod so that the cancellation becomes apparent. Eventually,
and in stages, cancel . Eg: solve 5 ≡ 17 ( 19)
University math: Field operations and properties:
Using multiplicative inverse: (chapters 4, 5, and still in mod prime) this could also include
applications of Fermat’s theorem in chapter 5.
More Advance: Reducing the strong field assumptions
Relatively prime: (Chapter 7, mod non-prime) Euler’s ideas and using Diophantine equations.
CHAPTER 4:
FUNDAMENTAL
THEOREM OF
ARITHMETIC
The Fundamental theorem of Arithmetic (FTA) is an existence
and uniqueness principle.
Such principles guide us and give us assurance that our steps
in the formal thinking, and our mechanical steps in
computations are formally justified.
FTA: any > 1 is prime or can be written as a product of
prime numbers; furthermore, this list of prime numbers is
unique.
This principle allows us to study the relationship between a
number and its factors.
IMPORTANT ALGEBRAIC CONSEQUENCES OF FTA
Here is a list of consequences of FTA:
1. The only prime factors of = are and .
for prime numbers , , , | implies = or = .2. ≡ ( ) implies ≡ ( ) (a cancelation law) (conditions on a?)3. ≡ 0 ( ) implies ≡ 0 or ≡ 0 ( )
4. Solutions to ! − 1 ≡ 0 ( ) are ≡ 1 or ≡ −1 ( )5. ≡ ( ) has a unique solution (conditions on a?)
CANONICAL FORM/ FACTORIZATION
Make sure to develop a working knowledge of this way of presenting a number !
What is ‘a working knowledge’?
Pay attention to the examples that may use this format .
COROLLARY 0 OF FTA
IMMEDIATE COROLLARY OF COROLLARY 0
This corollary is numbered Corollary 13, but it is immediate at this stage:
Corollary 13: Prove for > 1 and distinct prime numbers and ,
IF | and | THEN |.
Implications of this corollary are important in modular arithmetic:
IF a ≡ , and a ≡ ( ) then ≡ ( )
Why is this important? It extends the mod …
OTHER COROLLARIES OF FTA (DIFFERENT POINTS OF VIEWS)
Question1: Prove that for prime numbers , the number = has exactly and as
its prime factors (no other possible prime factors.)
What is the difference between Corollary 1 and this Question?
COROLLARY 4: (THIS IS COROLLARY 4.1.3)
For integers and and a prime , ⇒ |, ℎ.
Proof:
DIFFERENT VERSIONS OF COROLLARY 4
COROLLARIES 10-12, CANCELLATION IN MOD P
COROLLARY 4, REVISITED
NEGATION OF LOGICAL STATEMENTS
¬∀ ≡ ∃ ¬ ¬∃ ≡ ∀ ¬ ¬ ∧ ≡ ¬ ∨ ¬¬ ∨ ≡ ¬ ∧ ¬¬ ⟹ ≡ ∧ ¬
CONTRAPOSITION OF COR. 4
PROOF OF FTA
Proof of Existence appeared in chapter 2:
PROOF OF UNIQUENESS USING WOP
PROOF OF FTA CONT’D
PROOF OF FTA CONT’D
Since ! ≠ ! assume ! < !, and define
PROOF OF FTA CONT’D
QUESTION ABOUT THE PROOF
Question : In the last paragraph of the proof, how did we conclude that since ! is s divisor
of it has to be a prime factor of ?
See corollary 0 of FTA… did we use this corollary in the body of the proof?!
A MISUNDERSTANDING
CHAPTER 5: FERMAT’S AND WILSON’S THEOREMS
ℤ! IS A FINITE FIELD
FACTS ABOUT ℤ! CARRIED OVER FROM CHAPTER 4
Chapter 5 rests upon these facts from chapters 3,4:
This uniqueness is in mod p.
FACTS CONT’D
FOUR QUESTIONS ABOUT SOLVING AN EQUATION
FOUR QUESTIONS …
COMBINATORIAL ARGUMENT FOR EXISTENCE OF A SOLUTION
A Combinatorial Principle: (a version of pigeonhole principle)
COROLLARY OF THIS PRINCIPLE WHEN SOLVING ≡ 1
Solving ≡ 1 in ℤ! means finding a number in the list {1, … , − 1} that satisfies the equation.
Examine the row numbered of the multiplication table; this is what we see:
And why all numbers in the list {1, … , − 1} must appear in row in front of ?
Is there a solution to our equation ≡ 1? How to find the solution?
CONSEQUENCES OF OUR ARGUMENT
Existence and uniqueness of the multiplicative inverse:
UNIQUENESS OF MULTIPLICATIVE INVERSE IN MOD P
Doe this argument really use prime modulus?
CONSEQUENCES OF UNIQUENESS OF MULTIPLICATIVE INVERSE
WILSON’S THEOREM
Question 9 revisited: for a prime , − 1 ! = − 2 ! ( − 1), and note that all
numbers between 2 and ( − 2) are pairwise multiplicative inverses of each other, so − 2 ! ≡ 1 ( )
Note: remember does not divide ! + 1 (why?) nor does it divide − 1 ! (why?)
MORE CONSEQUENCES
DIOPHANTINE EQUATIONS
UNIQUENESS OF MULTIPLICATIVE INVERSE CONT’D
FERMAT’S LITTLE THEOREM
FERMAT’S CONT’D
INVESTIGATING THE CONDITIONS AND EXAMPLES
WILSON’S THEOREMS CONVERSE
Let’s see Wilson’s Theorem as follows:
IF is prime THEN | − 1 ! + 1
The converse would be
IF | − 1 ! + 1 THEN is prime
Is the converse true?
Contrapositive of the converse is
IF is composite, THEN does not divide − 1 ! + 1. is this true?
WILSON’S THEOREMS CONVERSE
Let’s see Wilson’s Theorem as follows:
IF is prime THEN | − 1 ! + 1
The converse would be
IF | − 1 ! + 1 THEN is prime
Is the converse true?
Contrapositive of the converse is
IF is composite, THEN does not divide − 1 ! + 1. is this true?
PROOF OF THEOREM 5.2.2
Proof by cases:
obvious case: there are < such that = (finish the proof that | − 1 ! )
Less obvious case: there isn’t < such that = . Then = " for some prime .
(why?)
But then 2 < . (why?)
And so, < 2 < " (why?) and 2 < ,
Finally, 2 | − 1 ! (why?)
Conclude that | − 1 !
CONVERSE TO WILSON’S THEOREM