Scribd
Upload
7 views24 pages

Number Theory: Divisibility & Primes

Chapter 1 covers fundamental concepts in number theory, including divisibility, the Euclidean algorithm, and properties of prime numbers. It explains the division algorithm and the significance of greatest common divisors, as well as introduces twin primes and the number of factors of a prime squared. Key properties of divisibility and prime numbers are also outlined.

Uploaded by

rickybir05
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
7 views24 pages

Number Theory: Divisibility & Primes

Chapter 1 covers fundamental concepts in number theory, including divisibility, the Euclidean algorithm, and properties of prime numbers. It explains the division algorithm and the significance of greatest common divisors, as well as introduces twin primes and the number of factors of a prime squared. Key properties of divisibility and prime numbers are also outlined.

Uploaded by

rickybir05
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Chapter 1: Number Theory

Contents
• Divisibility and Factorization
• Divisibility
• Greatest Common Divisors
• Euclidean Algorithm
• Primes: Prime Numbers
• Unique Prime Factorization
Divisibility and Factorization

• We say that a nonzero b divides a if a = mb for some m, where a, b,


and m are integers. That is, b divides a if there is no remainder on
division.

• The notation b a is commonly used to mean b divides a. Also, if b a,


we say that b is a divisor of a.
Properties of Divisibility

Subsequently, we will need some simple properties of divisibility for


integers, which are as follows:

• If a |1, then a = ±1.

• If a |b and b| a, then a = ±b.

• Any b ≠ 0 divides 0.

• If a |b and b |c, then a |c:


The Division Algorithm
Given any positive integer n and any nonnegative integer a, if we divide a
by n, we get an integer quotient q and an integer remainder r that obey the
following relationship:

a = qn + r

0≤r < n
Example
THE EUCLIDEAN ALGORITHM

• One of the basic techniques of number theory is the Euclidean


algorithm, which is a simple procedure for determining the greatest
common divisor of two positive integers.

• Two integers are relatively prime if and only if their only common
positive integer factor is 1. (co-prime)
Residue classes
Fundamental Theorem of Arithmetic
It is easy to determine the greatest common divisor of two positive integers if
we express each integer as the product of primes
Properties of Prime Numbers
• Every number greater than 1 can be divided by at least one prime
number.

• Every even positive integer greater than 2 can be expressed as the


sum of two primes.

• Except 2, all other prime numbers are odd.

• Two prime numbers are always coprime to each other.


Identify the twin primes among the given pair of
numbers:(1, 3), (3, 5), (13, 19), (1, 2)
• As know that the number 1 is neither prime nor composite. Hence, we can ignore
the pairs (1, 3) and (1, 2).

• As we know, twin prime numbers are the pair of prime numbers with a difference of
2.

• Here, (3, 5) is a pair of prime numbers with a difference of 2 (i.e) 5 – 3 = 2.

• Whereas (13, 19) is also a pair of prime numbers, in which the difference between
them is not equal to 2.

• Hence, (3, 5) is a twin prime


If “p” is the prime number, find the number of
factors p2 has.

As we know, p2 can be written as the product of p and P. (i.e., p×p).


Hence, the factors of p2 are 1, p and p2.

For example, let us take p = 2, the factors of 2 are 1, 2 and 4.

Therefore, p2 has exactly three factors.


To solve

You might also like