Class Notes
(811,335)

Canada
(494,663)

University of Toronto St. George
(42,887)

Mathematics
(2,710)

MAT246H1
(19)

Regina
(8)

Lecture

# MAT246 Lecture7.pdf

by
OneClass798

Unlock Document

University of Toronto St. George

Mathematics

MAT246H1

Regina

Fall

Description

MAT246 Lecture 7 (2012-10-31)
Chinese remainder theorem/The mathematical classic of Sunzi:
If , then
, where and are relatively primes.
Case of two equations:
, are relatively primes
is multiplicative inverse of , , that is
Bezout’s identity: let a and b be integers, not both zero, and . Then there exist integers x and y
such that:
Since, , then
=>
Since then
Since , then
Ex1: solve
Known that
=>
Thus, , then
Thus, the general solution is 19+56k
Ex2: solve
Known that
Thus, , then
Since
Since
since
That is,
Thus, the general solution is 233+105k
If k=-2, the minimum solution is 233-2 105=23
Theorem: two simultaneous congruences are only solvable when
. The solution is unique module if and are relatively primes
Proof: by the generalization of Euclidean algorithm.
Since =>
That is,
Suppose there exist integers s and t satisfying , then
=> =>
Ex3. solve
Since , 8-2=6 is divisible by 3,is solvable.
Known that MAT246 Lecture 7 (2012-10-31)
Step1: Suppose there exist integers s and t satisfying , then
, thus
That is,
Step2: , then
Thus,
Step3:
That is, the general solution is -16+36k=20+26k
Theorem: are solvable only when
. The solution is unique modulo
Ex4. Solve
From Ex3, the general solution for is n=20+36k.
Then the problem is solving
Since , 20-12=8 is divisible by 4, is solvable
Known that
Step1. Suppose there exist integers s and t satisfying , then
Thus,
Step2. : , then
Thus,
Step3.
That is, the general solution is 236+252k
Ex5. Solve
Known that
Thus, the general solution to the first five equations is .
Then, solve
Since , 1-0=1 is divisible by 1,is solvable
Known that
Step1. Suppose there exist integers s and t satisfying , then
Thus,
Step2.
Thus,
Step3.
That is, the general solution is -119+420k MAT246 Lecture 7 (2012-10-31)
Ex6. Solve
Known that
Since , 3-7=-4 is divisible by 1, is solvable
Step1: Suppose there exist integers s and t satisfying , then
Thus,
Step2. , then
Thus,
Step3.
That is, the general solution is
Ex7. Solve
From Ex6, the general solution for is
Then the problem is solving
Known that
Since , 4-40=-36 is divisible by 1, is solvable
Step1: Suppose there exist integers s and t satisfying , then
Thus,
Step2. , then
Thus,
Step3.
That is, the general solution is
Ex8. Solve
Known that
Since , 7-1=6 is divisible by 3, is solvable
Step1. Suppose there exist integers s and t satisfying , then
Step2. , then
Thus,
Step3.
That is, the general solution is MAT246 Lecture 7 (2012-10-31)
The complex numbers
Definition 9.1.1: a polynomial is an expression of the form , where n is a
natural number and the are numbers with . The are called the coefficients of the polynomial.
The natural number n, the highest power to which x occurs in the polynomial, is called the degree of the
polynomial. If , the polynomial is simply , which is called a constant polynomial.
Definition 9.

More
Less
Related notes for MAT246H1