4.3 Primes and Greatest Common Divisors

Question 1

What is prime and composite:

Whats 1?

Verify composite:

Answer 1

An integer p greater than 1 is called prime if the only positive factors of p are 1 and p.
A positive integer that is greater than 1 and is not prime is called composite.

The integer 1 is not prime, because it has only one positive factor.

Note also that an integer n is composite if and only if there exists an integer a such that a ∣ n and 1 < a < n.

Question 2

THE FUNDAMENTAL THEOREM OF ARITHMETIC:

Answer 2

Every integer greater than 1
can be written uniquely as a prime or as the product of two or more primes, where the prime
factors are written in order of nondecreasing size.

Question 3

Theorem 2:
Show given integer is prime:

Prove it:

Its application in the book?

Answer 3

If n is a composite integer, then n has a prime divisor less than or equal to √n

-it follows that an integer is prime if it is not divisible by any prime less
than or equal to its square root.

1 < a < n
n = ab
If a > √n and b > √n, then ab > √n ⋅√n = n, 
which is a contradiction. 
Consequently, a ≤ √n or b ≤ √n.

Brute Force Algo, Trial Division.

Question 4

Prime Factorisation of n:

Answer 4

Begin by dividing n by successive primes, starting with the smallest prime, 2. If n has a prime
factor, then by Theorem 3 a prime factor p not exceeding √n will be found. So, if no prime factor
not exceeding √n is found, then n is prime. Otherwise, if a prime factor p is found, continue
by factoring n∕p. Note that n∕p has no prime factors less than p. Again, if n∕p has no prime
factor greater than or equal to p and not exceeding its square root, then it is prime. Otherwise,
if it has a prime factor q, continue by factoring n∕(pq). This procedure is continued until the
factorization has been reduced to a prime.

7007 = 7 ⋅ 1001 = 7 ⋅ 7 ⋅ 143 = 7 ⋅ 7 ⋅ 11 ⋅ 13

Question 5

The sieve of Eratosthenes:

Answer 5

The sieve of Eratosthenes is used to find all primes not exceeding a specified positive integer.
For instance, n = 100.

Note that composite integers not exceeding 100 must have a prime factor not exceeding 10.
Because the only primes less than 10 are 2, 3, 5, and 7, the primes not exceeding 100 are these
four primes and those positive integers greater than 1 and not exceeding 100 that are divisible
by none of 2, 3, 5, or 7.

List 1 - 100.
To begin the sieving process, the integers
that are divisible by 2, other than 2, are deleted.
3 next largest number left, similar process with 3. then by 5,7.
All remaining integers except 1 are prime now.

Question 6

Theorem 3:
Cardinality of Primes ?

prove it

Answer 6

There are infinitely many primes.

Proof by contradiction.

Question 7

Mersenne primes:

Answer 7

There is an ongoing quest to discover larger and larger prime numbers; for almost all the last 300 years, the largest prime known has been an integer of the special form
2^p − 1, where p is also prime. (Note that 2^n − 1 cannot be prime when n is not prime).

The reason that the largest known prime has usually been a Mersenne prime is that there is an extremely efficient test, known as the Lucas–
Lehmer test, for determining whether 2^p − 1 is prime. Furthermore, it is not currently possible
to test numbers not of this or certain other special forms anywhere near as quickly to determine
whether they are prime.

Question 8

THE DISTRIBUTION OF PRIMES

THE PRIME NUMBER THEOREM:

Answer 8

The ratio of 𝜋(x), the number of primes not exceeding x, and x∕ ln x approaches 1 as x grows without bound. (Here ln x is the natural logarithm
of x.)

The prime number
theorem tells us that the number of primes not exceeding x can be approximated by x∕ ln x.

Question 9

the odds that a randomly selected positive integer less than n is prime are:

Answer 9

(n∕ ln n)∕n

= 1∕ ln n.

Question 10

bit operations to determine whether a positive integer n is prime?

Answer 10

O((log n)^6) bit operations to determine whether a positive integer n is prime.

Question 11

Cunningham numbers:

Answer 11

There is a communal effort on
the Internet to factor large numbers, especially those of the special form k^n ± 1, where k is a
small positive integer and n is a large positive integer (such numbers are called Cunningham
numbers). At any given time, there is a list of the “Ten Most Wanted” large numbers of this type
awaiting factorization.

Question 12

PRIMES AND ARITHMETIC PROGRESSIONS

Answer 12

Every odd integer is in one of the two arithmetic progressions 4k + 1 or 4k + 3, k = 1, 2, …. Because we know that there are infinitely
many primes, we can ask whether there are infinitely many primes in both of these arithmetic
progressions?

Every arithmetic progression ak + b, k = 1, 2, …, where a and b have no common factor greater than one, contains infinitely many primes.

Proved by Drichilet, proof is out of scope.

Question 13

Are there long arithmetic progressions made up of just primes?

Answer 13

In the 1930s, the legendary and
prolific mathematician Paul Erdos conjectured that for

every positive integer n greater than two,
there is an arithmetic progression of length n made up entirely of primes.

In 2006, Ben Green and Terence Tao were able to prove this conjecture. Their proof, considered to be a mathematical
tour de force, is a nonconstructive proof that combines powerful ideas from several advanced
areas of mathematics.

Question 14

Goldbach’s Conjecture:

We know its true for how many?

In the process of proving it we established what?

Answer 14

The conjecture that every even integer n, n > 2,
is the sum of two primes.
checked for all positive even integers up to
4 ⋅ 10^18.
In the process of proving it we established the following:
- every even integer greater than 2 is the sum of at most six primes
(proved in 1995 by O. Ramare) and
- that every sufficiently large positive integer is the sum of a prime and a number that is either prime or the product of two primes (proved in 1966 by J. R.
Chen).

Question 15

There are many conjectures asserting that there are infinitely many primes of certain special
forms

Answer 15

A conjecture of this sort is the conjecture that there are infinitely many primes of the
form n^2 + 1, where n is a positive integer. For example, 5 = 2^2 + 1, 17 = 4^2 + 1, 37 = 6^2 + 1, and so on. The best result currently known is that there are infinitely many positive integers n
such that n^2 + 1 is prime or the product of at most two primes (proved by Henryk Iwaniec in 1973
using advanced techniques from analytic number theory, far beyond the scope of this book).

Question 16

The Twin Prime Conjecture

Answer 16

Twin primes are pairs of primes that differ by 2, such as 3 and 5, 4967 and 4969.
The strongest result proved concerning twin primes is that there are infinitely many pairs p and p + 2, where p is prime and p + 2 is prime or the product
of two primes (proved by J. R. Chen in 1966).

Let P(n) be the statement that there are infinitely many pairs of primes that differ by exactly
n. The twin prime conjecture is the statement that P(2) is true.

Question 17

Bounded Gap Conjecture:.

Answer 17

Let P(n) be the statement that there are infinitely many pairs of primes that differ by exactly
n. 
Bounded gap asserts that there is an integer N for which P(N) is true.
Yitang Zhang, showed that there is an integer N < 70,000,000 such that P(N) is true.
Later team (with tao ) showed that N ≤ 6.

Question 18

Greatest Common Divisor:

Answer 18

Let a and b be integers, not both zero. The largest integer d such that d ∣ a and d ∣ b is called
the greatest common divisor of a and b. The greatest common divisor of a and b is denoted
by gcd(a, b).

Question 19

Relatively Prime:

Answer 19

The integers a and b are relatively prime if their greatest common divisor is 1.

Question 20

Pairwise relatively prime:

Answer 20

The integers a1, a2, … , an are pairwise relatively prime if gcd(ai, aj) = 1 whenever 1 ≤ i

Question 21

How to find GCD?

Make sure its right.

Answer 21

gcd(a, b) = p1^[min(a1, b1). p2 ^[min(a2, b2)] ⋯ pn ^[min(an, bn)]
This integer does divide both a and b, because the power of
each prime in the factorization does not exceed the power of this prime in either the factorization
of a or that of b. Further, no larger integer can divide both a and b, because the exponents of
the primes in this factorization cannot be increased, and no other primes can be included.

Prime factorizations can also be used to find the least common multiple of two integers.

Question 22

Least Common Multiple:

how to find it?

Answer 22

The least common multiple of the positive integers a and b is the smallest positive integer that
is divisible by both a and b. The least common multiple of a and b is denoted by lcm(a, b).

lcm(a, b) = p1^[max(a1, b1)].p2^[max(a2, b2)] ⋯ p^[max(an, bn)]

This formula is valid because
a common multiple of a and b has at least max(ai, bi) factors of pi in its prime factorization, and
the least common multiple has no other prime factors besides those in a and b.

Question 23

relationship between the greatest common divisor and least common
multiple of two integers:

Answer 23

Let a and b be positive integers. Then

ab = gcd(a, b) ⋅ lcm(a, b).

Question 24

Concept: The Euclidean Algorithm

Answer 24

gcd(91, 287).
First, divide 287, the larger of the two integers, by 91, the smaller, to obtain
287 = 91 ⋅ 3 + 14.
Any divisor of 91 and 287 must also be a divisor of
287 − 91 ⋅ 3 = 14. Also, any divisor of 91
and 14 must also be a divisor of 287 = 91 ⋅ 3 + 14. Hence, the greatest common divisor of 91
and 287 is the same as the greatest common divisor of 91 and 14. This means that the problem
of finding gcd(91, 287) has been reduced to the problem of finding gcd(91, 14).
Next, divide 91 by 14 to obtain
91 = 14 ⋅ 6 + 7.
It follows that gcd(91, 14) = gcd(14, 7).
Continue by dividing 14 by 7, to obtain
14 = 7 ⋅ 2.
gcd(14, 7) = 7

Question 25

The Euclidean algorithm is based on the following result about greatest common divisors
and the division algorithm:

Answer 25

Let a = bq + r, where a, b, q, and r are integers. Then gcd(a, b) = gcd(b, r).

Question 26

ALGORITHM 1 The Euclidean Algorithm.

Complexity:

Answer 26

procedure gcd(a, b: positive integers)
x := a
y := b
while y ≠ 0
    r := x mod y
    x := y
    y := r
return x{gcd(a, b) is x}

greatest common divisor is the last nonzero remainder in the sequence of divisions

Eventually a remainder of zero occurs in this sequence of successive divisions, because the
sequence of remainders a = r0 > r1 > r2 > ⋯ ≥ 0 cannot contain more than a terms.

number of divisions required to find the greatest common divisor of a and b,
where a ≥ b, is O(log b)

Question 27

BEZOUT’S THEOREM ´

Answer 27

If a and b are positive integers, then there exist integers s and t
such that gcd(a, b) = sa + tb.

Question 28

Bezout coefficients and identity :

Answer 28

If a and b are positive integers, then integers s and t such that gcd(a, b) = sa + tb are called
Bezout coefficients ´ of a and b.
The equation gcd(a, b) = sa + tb is called Bezout’s identity ´ .

Question 29

Method 2 to find gcd as linear combination:

extended Euclidean algorithm

Answer 29

set s0 = 1, s1 = 0,
 t0 = 0, and t1 = 1 and let
sj = sj−2  −  qj−1sj−1 and tj = tj−2  −   qj−1tj−1
for j = 2, 3, … , n, where the qj are the quotients in the divisions used when the Euclidean algorithm finds gcd(a, b)

gcd(a, b) = sna + tnb

Question 30

Method 1:

Answer 30

Forward pass then backward pass.
gcd(252, 198) = 18
252 = 198 ⋅ 1 + 54
198 = 54 ⋅ 3 + 36
54 = 36 ⋅ 1 + 18
36 = 18 ⋅ 2 + 0.

We find that
18 = 54 − 1 ⋅ 36.
The second division tells us that
36 = 198 − 3 ⋅ 54.
and so gives us:

18 = 4 ⋅ 252 − 5 ⋅ 198

Question 31

Lemma 2, about divisibility when gcd(a, b) = 1 and

a|bc

Answer 31

If a, b, and c are positive integers such that gcd(a, b) = 1 and a ∣ bc, then a ∣ c.

and proof

Question 32

LEMMA 3

generalization of Lemma 2

Answer 32

If p is a prime and p ∣ a1a2 ⋯ an, where each ai is an integer, then p ∣ ai for some i.

Question 33

THEOREM 7

proof:

Congruence and getting rid of same number from both sides.

Answer 33

Let m be a positive integer and let a, b, and c be integers. If ac ≡ bc (mod m) and
gcd(c, m) = 1, then a ≡ b (mod m).

Proof: Because ac ≡ bc (mod m), m ∣ ac − bc = c(a − b). By Lemma 2, because gcd(c, m) = 1,
it follows that m ∣ a − b. We conclude that a ≡ b (mod m).

Question 34

Proof (of the uniqueness of the prime factorization of a positive integer):

Answer 34

Page 288

Proof by contradiction, using lemma 3.