Class Notes
(808,146)

Canada
(493,092)

University of Toronto St. George
(42,760)

Mathematics
(2,710)

MAT246H1
(19)

Regina
(8)

Lecture

# MAT246 Lecture4.docx

Unlock Document

University of Toronto St. George

Mathematics

MAT246H1

Regina

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