## David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution

**Page 49 Problem 1 Answer**

Given ; p ≤ √701

To find : Determine whether the integer 701 is prime by testing all primes

here we will factorize the 701 and test the result if it prime or not and do the sam for 1009

we have p ≤ √701

p ≤ √701 ≤ 27,p = 2,3,5,7,11,13,17,19,23

but none of them divides 701 , thus 701 is prime.

p ≤ √1009 ≤ 32,p = 2,3,5,7,11,13,17,19,23,29,31

but none of them divides 1009 , thus 1009 is prime.

Hence we conclude that both the number 701,1009 are prime

**Page 49 Problem 3 Answer**

Given ; Given that p/n for all primes p ≤ \(\sqrt[3]{n}\),

To find : show that n > 1 is either a prime or the product of two primes

here we will Assume to the contrary that n contains at least three prime factors

assume n = p_{1}p_{2}⋯pk,k ≥ 3

The first three primes factors are p_{1},p_{2},p_{3} then

p_{1} ∣ n,p_{2} ∣ n,p_{3} ∣ n

⟹ p_{1}p_{2}p_{3} ∣ n ⟹ p ≥ p_{1}p_{2}p_{3}

Since p ∤ n for all p ≤ \(\sqrt[3]{n}\) then

p_{1} > \(\sqrt[3]{n}\),p_{2} > \(\sqrt[3]{n}\),p_{3} > \(\sqrt[3]{n}\)

Thus p_{1}p_{2}p_{3} > n contradiction, thus n > 1 is either a prime or the product of two prime

Hence we conclude that if p_{1}p_{2}p_{3} > n contradiction, thus n > 1 is either a prime or the product of two primes.

**Page 49 Problem 4 Answer**

Given ; √p is irrational for any prime p

To find ; Establish the following facts:

here we will asume √p is rational number with p as prime number

Let p is fixed prime number.

Assume that √p is rational,

i.e. √p = \(\frac{k}{l}\) for some positive integers k and l such that gcd(k,l) = 1.

Then must be p = \(\frac{k^2}{l^2}\), also l{2}p = k^{{2}}.

From the last equality, we have that l^{2} and m^{2}.

Therefore, must be l = 1, because gcd(k,l) = 1.

So that, must be p = m^{{2}}, but this is contradiction, because does not exists prime number which is perfect square!

Hence, the proof!

Hence we have proved that p = m^{{2}},but this is contradiction, because does not exists prime number which is perfect square!

Given ; If a is a positive integer and \(\sqrt[n]{a}\) is rational, then \(\sqrt[n]{a}\) must be an integer

To find; Establish the following facts:

If a is a positive integer and \(\sqrt[n]{a}\) is rational,

we need to show that \(\sqrt[n]{a}\) is an integer.

If \(\sqrt[n]{a}\) is rational, then exist the numbers k and l such that \(\sqrt[n]{a}\) = \(\frac{k}{l}\) and gcd(k,l) = 1.

From \(\sqrt[n]{a}\) = \(\frac{k}{l}\) we have that a = \(\frac{k^n}{l^n}\),

also l^{n}a = k^{n}.

Therefore, ln divides k^{n}!

So that, must be l = 1 because gcd(k,l) = 1.

Finally, \(\sqrt[n]{a}\) is an integer!

Hence we conclude that l^{n}a = k^{n}. Therefore, ln divides kn! So that, must be l = 1 because gcd(k,l) = 1.

Finally, \(\sqrt[n]{a}\) is an integer!

We have Given ; n ≥ 2,\(\sqrt[n]{n}\) is irrational.

To find : we have to Establish the following facts:

Here we will use the fact 2^{n} > n

If a is a positive integer and \(\sqrt[n]{a}\) is rational,

we need to show that \(\sqrt[n]{a}\) is an integer.

If \(\sqrt[n]{a}\) is rational

Then exist the numbers k and l such that \(\sqrt[n]{a}\) = \(\frac{k}{l}\) and gcd(k,l) = 1.

From \(\sqrt[n]{a}\) = \(\frac{k}{l}\) we have that a = \(\frac{k^n}{l^n}\), also l^{n}a = k^{n}.

Therefore, l^{n} divides k^{n}!

So that, must be l = 1 because gcd(k,l) = 1.

Finally, \(\sqrt[n]{a}\) is an integer

If \(\sqrt[n]{n}\) is rational for some integer n ≥ 2,

Then using result from part b it must be integer

From the fact \(\sqrt[n]{n}\) > 1 and preceding fact,

we obtain that \(\sqrt[n]{n}\) ≥ 2.

So that, must be n ≥ 2^{n}.

Further, from the fact n < 2^{n} we have the contradiction!

Finally, \(\sqrt[n]{n}\) is irrational!

Hence we obtain that \(\sqrt[n]{n}\) ≥ 2. It must be n ≥ 2^{n}. from the fact n < 2^{n} we have the contradiction

Finally, \(\sqrt[n]{n}\) is irrational!

**Page 49 Problem 6 Answer**

Given : Proof of the infinitude of primes.

To find : missing details in given proof.

We will find it.

Here,

Assume only finite numbers p_{1},…,p_{n}

Let A be the product of any r these primes.

So,

A = p_{a1}⋅…⋅p_{ar},a_{i} ∈ {1,2,…,n}

Consider

B = \(\frac{p_1 \cdot \ldots \cdot p_n}{A}\)

= \(\frac{p_1 \cdot \ldots \cdot p_n}{p_{a_1} \cdot \ldots \cdot p_{a_r}}\)

= p_{b1}……..p_{bs}

Where a_{i} ≠ b_{j}

So that,

{a_{i}∣i=1,…,r}∩{b_{j}∣j=1,…,s}=∅

and

{a_{i}∣i=1,…,r}∪{b_{j}∣j=1,…,s}={p_{i}∣i=1,…,n}

Hence, A and B have no common factors.

Then each p_{k} of p_{1},p_{2},…,p_{n} divides either A or B, but not both. Since, A > 1,B > 1, then A + B > 1

Therefore, A + B has a prime divisor different from any of the p_{i}, which is a contradiction.

Therefore, We completed the given proof..

**Page 49 Problem 7 Answer**

Given : Euclid’s proof

To do : Modify the given proof.

Here,

The modify proof is :

Let N > 1 then there exists q (prime number) divide N, since all primes numbers contained in p! = p(p−1)⋯3⋅2⋅1

Now,

q = p_{i} for some i.

Then q∣p_{i} ⟹ q∣1 ⟹ q ≤ 1 which is contradiction.

Hence, there are infinitely many primes.

Therefore,

Modified proof is stated above.

**Page 49 Problem 8 Answer**

Given : Proof of the infinitude of primes.

To do : Give another proof of the infinitude of primes.

Here,

The another proof of the infinitude of primes:

Let p_{i} ≥ 2 for all i, thus N > 1, then there exists q prime number divides N.

But p_{1},p_{2},⋯,p_{n} are all prime numbers, thus q = p_{i} for some i

If q = p_{i} then q ∣ N and q ∣ p_{i}

Then p_{i} = q ∣ p_{2}p_{3}⋯p_{i-1}p_{i+1}⋯p_{n }thus

p_{i} ∣ p_{k},2 ≤ k ≤ n is a contradiction.

Hence,

The set of prime numbers is infinite.

Therefore,

Another proof of the infinitude of primes is given above.

**Page 50 Problem 9 Answer**

Given : n>2

WE have to prove that there exists a prime p satisfying n < p < n!

We will prove it.

Here,

Let n be an integer such that n > 2, then n!−1 > 1.

Now,

If n!−1 is prime number, we can choose p = n!−1.

From the facts

n!−1 > 2n−1 = n+n−1 > n+1 > n and

n!−1 < n!, we get that n < p < n!−1.

Now,

If n!−1 is not prime, then it has a prime divisor p. Prime divisor p must be bigger than n, because for all positive integer k such that k ≤ n we have k∣n! and they can not be divisors of n!−1.

Hence,

From the facts p∣(n!−1) and n!−1is not prime, we get that p < n!−1.

So , exist prime number p such that n < p < n!−1 < n!

Therefore,

if n > 2, then there exists a prime p satisfying n < p < n!

Given : n > 1,

We have to show that every prime divisor of n!+1 is an odd integer that is greater than n

We will show it.

Here,

Let n be an integer such that n > 1

Then all prime divisors of n!+1 must be bigger than n, because for all positive integer k such that k ≤ n

So, we have k∣n! and they can not be divisors of n! + 1.

Therefore,

For n > 1,every prime divisor of n! + 1 is an odd integer that is greater than n.

**Page 50 Problem 10 Answer**

Let q_{n} be the smallest prime that is strictly greater than P_{n} = p_{1}p_{2}⋯p_{n}+1

It has been conjectured that the difference q_{n}−(p_{1}p_{2}⋯p_{n}) always a prime.

We have to confirm this for the first five values of n.

Here,

We have , q_{n} be the smallest prime that is strictly greater than P_{n} = p_{1}p_{2}⋯p_{n} + 1

It has been conjectured that the difference q_{n} − p_{1}p_{2}⋯p_{n} is always a prime.

Now,

We want to confirm this for the first five values of n:

p_{1} = 2

p_{2} = 3

p_{3} = 5

p_{7},p_{5} = 11

So,

P_{1} = 2 + 1 ⇒ 3 ⟹ q_{1} ⇒ 5,

⇒ q_{1} − p_{1} = 5 − 2 ⇒ 3 is prime.

P_{2} = 2⋅3 + 1 ⇒ 7 ⟹ q_{2} ⇒ 11,

⇒ q_{2} − p_{1}p_{2} = 11 − 6 ⇒ 5 is prime.

P_{3} = 2⋅3⋅5 + 1 ⇒ 31 ⟹ q_{3} ⇒ 37,

⇒ q_{3} − p_{1}p_{2}p_{3} = 37 − 30 ⇒ 7 is prime.

P_{4} = 2⋅3⋅5⋅7 + 1 ⇒ 211 ⟹ q_{4} ⇒ 223,

⇒ q_{4} − p_{1}p_{2}p_{3}p_{4 }= 223 − 210 ⇒ 13 is prime.

P_{5} = 2⋅3⋅5⋅7⋅11 + 1 ⇒ 2311 ⟹ q_{5} ⇒ 2333,

q_{5} − p_{1}p_{2}p_{3}p_{4}p_{5} = 2333 − 2310 ⇒ 23 is prime.

Therefore,

The difference q_{n} – (p_{1}p_{2}….p_{n}) always a prime.

**Page 50 Problem 12 Answer**

Given : p_{n} is the nth prime number,

We have to establish each of the given statements: p_{n} > 2n−1 for n ≥ 5.

Here,

The statement is correct for n = 5(p_{5 }⇒ 11>2⋅5−1 ⇒ 9).

Now,

If we consider that this statement is true for an arbitrary integer k > 5 and show that this statement is correct for k+1, then using the principle of induction we have that this statement is true for an arbitrary integer n ≥ 5.

Now,

If we assume that this statement is true for an arbitrary integer k > 5, then from the fact p_{k+1} − p_{k} ≥ 2 (in other way if p_{k+1} = pk+1, then p_{k+1} is even)

Hence,

We get that

p_{k+1} ≥ p_{k} + 2 > 2k−1 + 2 = 2(k+1)−1

Therefore,

p_{n} > 2n−1 for n ≥ 5

Given : p_{n} is the nth prime number,

We have to show that none of the integers

P_{n} = p_{1}p_{2}⋯p_{n} + 1 is a perfect square.

We will show it by a contradiction.

Here,

Integer p_{2}…p_{n} is odd, so that exist an positive integer k such that p_{2}…p_{n} = 2k + 1,

Then we get that P_{n} is given of the form

P_{n} = 2(2k+1) + 1

= 4k + 3

Now,

If this integer is a perfect square, then exist an odd integer m = 2l + 1 (because P_{n} is odd)

such that P_{n} = m^{2}.

Then we get next situation Pn = 4k + 3

= (2l+1)^{2}

= 4l^{2} + 4l + 1

i.e. 4k + 2 = 4l^{2} + 4l

As we can see, 4 ∣ 4l^{2} + 4l but 4∤4k+1 which we have a contradiction.

Therefore,

None of the integers P_{n} = p_{1}p_{2}⋯p_{n}+1 is a perfect square.

Given : p_{n} is the nth prime number

We have to show that the sum \(\frac{1}{p_1}+\frac{1}{p_2}+\cdots+\frac{1}{p_n}\) is never an integer.

We will show it by a contradiction.

Here Let A = \(\frac{1}{p_1}+\frac{1}{p_2}+\cdots+\frac{1}{p_n}\).

Now,

Consider that A is an integer,

Then after multiplying it with p_{1}p_{2}…p_{n-1} we have that p_{1}p_{2}…p_{n-1}A = p_{2}p_{3}…p_{n-1}+p_{1}p_{3}…p_{n-1}+…+p_{1}p_{2}…p_{n-2}+ \(\frac{p_1 p_2 \cdots p_{n-1}}{p_n}\) is an integer.

Also

p_{1}p_{2}…p_{n-1}A − p_{2}p_{3}…p_{n-1} − p_{1}p_{3}…p_{n-1}−…−p_{1}p_{2}…p_{n-2} = \(\frac{p_1 p_2 \cdots p_{n-1}}{p_n}\) is an integer too.

Hence, p_{n }∣ p_{1}p_{2}…p_{n-1}, then we have contradiction.

Therefore,

The sum \(\frac{1}{p_1}+\frac{1}{p_2}+\cdots+\frac{1}{p_n}\) is never an integer.

**Page 50 Problem 13 Answer**

Given : n∣m

We have to show that R_{n}∣R_{m}

We will use above information.

Here,

We have, n∣m, then exists an integer k > 0 such that m = k_{n}.

So, repunit R_{m} is given of the form :

R_{m} = R_{kn}

= 11…1

= 10^{(k-1)n}R_{n} + 10^{(k-2)n}R_{n}+…+10^{n}R_{n} + R_{n}

Hence,

It is not hard to see that R_{n }∣ R_{m}

Therefore,

If n ∣ m, then R_{n }∣ R_{m}

Given : d ∣ R_{n} and d ∣ R_{m}

We have to show that d ∣ R_{n+m}

We will use above information.

Here,

We have, d ∣ R_{n} and d ∣ R_{m}, we need to show that d ∣ R_{n+m}.

Now,

Repunit R_{m+n} is given by : \(R_{m+n}=11 \ldots 1\)

= \(11 \ldots 1 \overbrace{00 \ldots 0}^n+\underbrace{1 \ldots 1}\)

= 10^{m}R_{n} + R_{m}

Hence,

It is not hard to see that d ∣ R_{m+n}.

Therefore,

If d ∣ R_{n} and d ∣ R_{m}, then d ∣ R_{n+m}

Given : gcd(n,m) = 1

We have to show that gcd(R_{n},R_{m}) = 1

We will use above information.

Here,

We have, gcd(m,n) = 1 and m ≥ n.

Now,

By using Theorem 2.1. we have that m = kn + r for some integers 0 < k and 0 ≤ r < n.

Repunit Rm−n is given of the form :

R_{m-n} = R_{m}−10^{m-n}R_{n}

Hence,

It is not hard to conclude that gcd(R_{m},R_{n}) = gcd(R_{m-n},R_{n}).

If we repeat this procedure k times, we get that

gcd(R_{m},R_{n}) = gcd(R_{m-n},R_{n})

= …

= gcd(R_{m-kn},R_{m})

= gcd(R_{r},R_{m})

Now, using Theorem 2.1. we get that n = k_{1}r + r_{1} for some integers 0 < k−1 and 0 ≤ r_{1} < r.

Then using preceding procedure we get that gcd(R_{m},R_{n}) = gcd(R_{r},R_{m})

= gcd(R_{r},R_{r1})

As we can see our procedure is based on Euclidean algorithm, so after using it several times, we obtain

gcd(R_{m},R_{n}) = R_{gcd(m,n)}

= R_{1}

= 1

Now,

If gcd(R_{m},R_{n}) = 1,

then gcd(m,n) = 1.

If d = gcd(m,n),

then using result from part b) we have that R_{d} ∣ R_{m} and R_{d} ∣ R_{n}.

So, R_{d} ∣ gcd(R_{m},R_{n}) = 1

⇒ d = 1

Therefore,

If gcd(n,m) = 1,

then gcd(R_{n},R_{m}) = 1

**Page 50 Problem 14 Answer**

We have to obtain the prime factors of the repunit R_{10}

We will use result : If n ∣ m, then R_{n }∣ R_{m}

Here,

We have, R_{2}, R_{5} ∣ R_{10}.

So, we repunit R_{10} is given of the form

R_{10} = R_{2}⋅R_{5}⋅k for some positive integer k.

Now,

From last result we get that K = \(\frac{R_{10}}{R_2 \cdot R_5}\)

= 9091

Integers 9091 and R_{2} = 11 are prime numbers,

So, we need to obtain the prime factors of R_{5} = 11111.

Prime factors of this number are 271 and 41.

Hence,

R_{10} = 11⋅41⋅271⋅9091

Therefore,

R_{10} = 11⋅41⋅271⋅9091