Unit 7 Basic Number Theory

CSC 201: Unit 7 Basic Number
Theory
1
Subunit 7(a) Divisibility and congruences
2
Divisibility
•Let and be integers with . We say that divides and
write provided that there exists an integer such that .
Whenever , we also say the following
• is a factor of
• is a multiple of
• is divisible by
• is a divisor of .
a|b
If does not divide , we write ⁄
|
For example, but 2 ⁄ 5.
3
Basic property of divisibility
• Suppose
a, b, c, m, and n are integers with
Suppose also that and . Then, .
Proof: We are given that and
for some integers r and s. Thus,
But this means that since is an integer.
4
The division algorithm
•Division
algorithm: Let a be an integer and let d
be a positive integer. Then, there exist unique
integers q and r such that and
Proof: Let . Then, so that Let . Then, r is an
integer with and
This proves the existence part of our result.
5
Proof of division algorithm (continued)
•To prove uniqeness, suppose that there exist

integers and with and Then, . Also,
qd  r  q1d  r1 (1)
 r  r1  (q1  q )d
| r  r1 |  | q1  q || d |  | q1  q | d (since d  0)
 | q1  q |  1 since | r  r1 |  d .
Since q and q1 are integers, it follows that
q1  q  0 so that q1  q. Equation (1) now gives r1  r.
6
Quotient and remainder
• In the division algorithm, q is called the
quotient and r is called the remainder (when a
is divided by d). We write q = a div d and
r = a mod d.
For example, 9 = 101 div 11 and
2 = 101 mod 11.
• Another example: -4 = -11 div 3 and
1 = -11 mod 3.
7
Congruences
• Definition:
If a and b are integers and m is a
positive integer, we say that a is congruent to b
modulo m and we write provided that
• For example, but
8
Properties of congruences
• Let
m be a positive integer and let a, b and c
be integers. Then,
(i)
(ii) If then
(iii) If and then
Proof : Exercise
9
Further properties of congruences
• Let
m be a positive integer and let a, b, c, and d be
integers. If and then
(i) and
(ii)
Proof: We prove (ii) and leave the proof of (i)
as an exercise. We have
Since and , it follows (from the basic property of

divisibility) that .
10
Generalizations
• Using
the last property and mathematical
induction, we easily obtain the following:
• Let m be a positive integer and let be
integers. If for each i with then and .
• Let m and k be positive integers and let a and b
be integers. If then
11
Example 1
• Show
that .
Solution: Note that
25  32  9 (mod 41)
 (25 ) 2  (9) 2  81  1 (mod 41)
Hence, 210  1 (mod 41)
 (2 )  (1) (mod 41)
10 2 2
i. e. 2  1 (mod 41)
20
This means that 41 | (2  1)

20
12
Example 2
• Find the remainder when is divided by 12.
Solution: Note that . It follows that ,, etc. In other
words, for every positive integer n with . Hence,
1! 2 ! 3! 4 ! 5!   100! 1  2  6  0    0  9 (mod 12)

This means that 1! 2! 3!   100! 12q  9 for some integer q.
Hence, the remainder when 1! 2! 3!   100! is divided by 12
is 9.
13
Subunit 7(b) Primes
14
Prime numbers
• Definition:
A positive integer p with is called
a prime provided that its only positive divisors
are 1 and p. A positive integer great than 1
which is not prime is called composite.
• The first few primes are 2, 3, 5, 7, 11, 13, 17,
19.
• Note that an integer n with is composite if and
only if there is an integer a with and
15
Prime factorization
• Theorem 1: Every positive integer greater
than 1 is a prime or a product of two or more
primes.
• For example, 3  3
8  2(2)(2)
12  2(2)(3)
15  3(5)
16
Proof of Theorem 1
• Let
be the statement that n is a prime or a product
of two or more primes. We have to prove that is
true for all positive integers n with . We will do this
by strong induction.
Basic step: Note that is true since 2 is a
prime.
Induction step: let k be an integer with
and suppose that is true for every integer j
with . There are two possibilities for k.
17
Proof of Theorem 1 (continued)
•Case
1: If k is prime then is true.
Case 2: If k is composite, then there exist integers a
and b with and and . By our assumption, and are true.
So, a is a prime or a product of at least two primes and
the same is true for b. Thus, is a product of at least two
primes so that is true.
We have shown that for any integer , if is true for
every integer j with then must be true. Together with
the fact that is true, It follows that is true for every
integer n greater than 1.
18
Unique factorization
• It can be proved that the prime factorization,
whose existence is guaranteed by Theorem 1,
is unique up to ordering. The proof of this is
harder and requires some further background
material.
19
A useful result
• Theorem
2: If n is composite, then n has a
prime divisor p with
Proof: If n is composite, then by Theorem 1, n is
a product of at least two primes. If all these
primes were greater than , we would have
which is impossible. Hence, there is at least one
prime divisor of n which is less than or equal to
.
20
Example 3
• Show
that 101 is prime.
Solution: If 101 was composite, it would be
divisible by a prime less than or equal to . The
primes less than or equal to are 2, 3, 5 and 7.
None of these divide 101. Hence, 101 is prime.
21
Infinitude of primes
• Theorem
3: There are infinitely many primes.
Proof: Suppose there are finitely many
primes . Let . Then, N has a prime divisor by
Theorem 1. So, there is an integer j with such
that . Since , we get , i.e. which is impossible
since is prime. Hence, there are infinitely many
primes.
22
The Goldbach conjecture
• Consider the following:
4  2  2, 6  3  3, 8  3  5
10  3  7, 12  5  7, 14  3  11
16  3  13, 18  5  13, 20  7  13.
From this it appears that every even integer
greater than two is the sum of two primes. This
was conjectured by Goldbach in the 18 th century.
It is still not proved.
23

Unit 7 Basic Number Theory

Uploaded by

Copyright:

Available Formats

Unit 7 Basic Number Theory

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Unit 7 Basic Number Theory

Uploaded by

Copyright:

Available Formats

CSC 201: Unit 7 Basic Number

But this means that since is an integer.

•To prove uniqeness, suppose that there exist

Since and , it follows (from the basic property of

This means that 41 | (2  1)

1! 2 ! 3! 4 ! 5!   100! 1  2  6  0    0  9 (mod 12)

You might also like