Class Notes (808,146)
Mathematics (2,710)
MAT246H1 (19)
Regina (8)
Lecture

# MAT246 Lecture4.docx

4 Pages
227 Views

School
University of Toronto St. George
Department
Mathematics
Course
MAT246H1
Professor
Regina
Semester
Fall

Description
MAT246 Lecture4 (2012-10-03)  Ex1. Find the remainder when 5! ∙ 181 − 866 ∙ 322 is divided by 6. 5! ∙ 181 − 866 ∙ 322 ≡ 0 ∙ 181 − 2 ∙ 2 mod 6 ≡ −4 mod 6 ≡ 2 mod 6 ) The remainder when 5! ∙ 181 − 866 ∙ 322 divided by 6 is 2.  Ex2. Is 2598+ 3 divisible by 15? Divisible by 15 means divisible by 3 and 5. 4 4 149 596 2 ≡ 1 mod 15 =>) (2 ) ≡ 1 mod 15 => 2 ≡ 1 mod 15 ) 596 2 598 598 => 2 ∙ 2 ≡ 4 mod 15 => 2 ≡ 4 mod 15 => 2 + 3 ≡ 4 + 3 = 7 (mod 15) That is, 2598+ 3 is not divisible by 15. The remainder when 2 598 + 3 divided by 15 is 7.  Ex3. Suppose p is a prime number, p does not divide a, ax ≡ 1 mod p . Does it have a solution? Let p=5, a=3, then 3x ≡ 1 mod 5 ) Thus, 3x=6 => x=2. That is, there is at least one solution for this statement. MAT246 Lecture4 (2012-10-03) The Fundamental Theorem of Arithmetic 217 92 15 111 145 12 5 13 ∙ 37 ∙ 41 and 19 ∙ 29 ∙ 43 ∙ 47 are they equal? No based on the fundamental theorem of arithmetic. Theorem 4.1.1: every natural number greater than can be written as a product of primes, and the expression of a number as a product of primers is unique except for the order of the factors. Proof: Part 1: “every natural number greater than can be written as a product of primes” is proved in Theorem 2.2.4. Part 2 : “the expression of a number as a product of primers is unique except for the order of the factors”, which mean uniqueness. This can be done by contradiction. Suppose there is a number that can be written as a product of primes in two different ways. Let us consider a set of such number. By our assumption this set is not empty. By WOP, there exists a smallest natural number N with that property. N = 𝑝 1 2∙∙ 𝑝 𝑟 𝑞 𝑞 1 2 𝑞 , 𝑠here each of the 𝑝 and 𝑞 𝑖 𝑗 are primes and 𝑝 ≠ 𝑞 𝑖 𝑗 (since if there exists any 𝑝 = 𝑖 , t𝑗e common factor could be divided from both sides of the equation, leaving a smaller number than N, which supposes to be the smallest). Since 𝑝 ≠ 𝑞 , thus 𝑝 ≠ 𝑞 . Then suppose 𝑝 < 𝑞 . 𝑖 𝑗 1 1 1 1 Let M = N − 𝑝 𝑞 1 2 𝑞 > 𝑠, that is M is natural number less than N. Since N = 𝑝 𝑝 1 2 𝑝 , 𝑟hen, M = 𝑝 𝑝 ∙∙1 2 − 𝑝 𝑟 ∙∙∙1 2= 𝑝 (𝑠 ∙∙∙ 1 −2𝑞 ∙∙∙𝑟𝑞 ) 2 𝑠 Since N = 𝑞 𝑞 1 2 𝑞 , 𝑠hen, M = 𝑞 𝑞 ∙∙1 2 − 𝑝 𝑠 ∙∙∙1 2= (𝑞 𝑠 𝑝 )(𝑞1∙∙∙ 1 ) 2 𝑠 Known that 𝑝 is 1 divisor of M, and 𝑝 is not e1ual to any of 𝑞 ,…,𝑞 . That is2 𝑠 𝑞 − 𝑝 = 𝑝 𝑘 for some integer k. Then, 𝑞 = 𝑝 + 𝑝 𝑘 = 𝑝 (1 + 𝑘). Thus, 𝑞 is divisible 1 1 1 1 1 1 1 1 by 𝑝 . Since 𝑝 and 𝑞 are distinct primes, this impossible. 1 1 1 That is, the assumption is not true. The original statement is true. Corollary 4.1.2: every natural number n greater than 1 has a canonical factorization into 𝛼 𝛼 𝛼 primes; that is, n has a unique representation in the form n = 𝑝 1𝑝 2 ∙∙∙ 𝑛𝑛, where 𝑝 is𝑖a 1 2 prime, 𝑝 is less than 𝑝 for each i, and each 𝛼 is a natural number. 𝑖 𝑖:1 𝑖 Corollary 4.1.3: if p is a prime number and a and b are natural numbers such that p divides ab, then p divides at least one of a and b. (that is, if a prime divides a product then it divides at least one of the factors.) MAT246 Lecture4 (2012-10-03) Fermat’s Theorem Theorem 5.1.1: if p is a prime and a is not divisible by p, and if ab ≡ ac mod p , then ) b ≡ c mod p .) Proof: ab ≡ ac mod p ) => ab − ac ≡ 0 mod p ) => a(b − c) ≡ 0 mod p ) Since a is not divisi
More Less

Related notes for MAT246H1

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.