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 = p1p2⋯pk,k ≥ 3
The first three primes factors are p1,p2,p3 then
p1 ∣ n,p2 ∣ n,p3 ∣ n
⟹ p1p2p3 ∣ n ⟹ p ≥ p1p2p3
Since p ∤ n for all p ≤ \(\sqrt[3]{n}\) then
p1 > \(\sqrt[3]{n}\),p2 > \(\sqrt[3]{n}\),p3 > \(\sqrt[3]{n}\)
Thus p1p2p3 > n contradiction, thus n > 1 is either a prime or the product of two prime
Hence we conclude that if p1p2p3 > 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 l2 and m2.
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 lna = kn.
Therefore, ln divides kn!
So that, must be l = 1 because gcd(k,l) = 1.
Finally, \(\sqrt[n]{a}\) is an integer!
Hence we conclude that lna = kn. 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 2n > 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 lna = kn.
Therefore, ln divides kn!
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 ≥ 2n.
Further, from the fact n < 2n we have the contradiction!
Finally, \(\sqrt[n]{n}\) is irrational!
Hence we obtain that \(\sqrt[n]{n}\) ≥ 2. It must be n ≥ 2n. from the fact n < 2n 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 p1,…,pn
Let A be the product of any r these primes.
So,
A = pa1⋅…⋅par,ai ∈ {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}}\)
= pb1……..pbs
Where ai ≠ bj
So that,
{ai∣i=1,…,r}∩{bj∣j=1,…,s}=∅
and
{ai∣i=1,…,r}∪{bj∣j=1,…,s}={pi∣i=1,…,n}
Hence, A and B have no common factors.
Then each pk of p1,p2,…,pn 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 pi, 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 = pi for some i.
Then q∣pi ⟹ 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 pi ≥ 2 for all i, thus N > 1, then there exists q prime number divides N.
But p1,p2,⋯,pn are all prime numbers, thus q = pi for some i
If q = pi then q ∣ N and q ∣ pi
Then pi = q ∣ p2p3⋯pi-1pi+1⋯pn thus
pi ∣ pk,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 qn be the smallest prime that is strictly greater than Pn = p1p2⋯pn+1
It has been conjectured that the difference qn−(p1p2⋯pn) always a prime.
We have to confirm this for the first five values of n.
Here,
We have , qn be the smallest prime that is strictly greater than Pn = p1p2⋯pn + 1
It has been conjectured that the difference qn − p1p2⋯pn is always a prime.
Now,
We want to confirm this for the first five values of n:
p1 = 2
p2 = 3
p3 = 5
p7,p5 = 11
So,
P1 = 2 + 1 ⇒ 3 ⟹ q1 ⇒ 5,
⇒ q1 − p1 = 5 − 2 ⇒ 3 is prime.
P2 = 2⋅3 + 1 ⇒ 7 ⟹ q2 ⇒ 11,
⇒ q2 − p1p2 = 11 − 6 ⇒ 5 is prime.
P3 = 2⋅3⋅5 + 1 ⇒ 31 ⟹ q3 ⇒ 37,
⇒ q3 − p1p2p3 = 37 − 30 ⇒ 7 is prime.
P4 = 2⋅3⋅5⋅7 + 1 ⇒ 211 ⟹ q4 ⇒ 223,
⇒ q4 − p1p2p3p4 = 223 − 210 ⇒ 13 is prime.
P5 = 2⋅3⋅5⋅7⋅11 + 1 ⇒ 2311 ⟹ q5 ⇒ 2333,
q5 − p1p2p3p4p5 = 2333 − 2310 ⇒ 23 is prime.
Therefore,
The difference qn – (p1p2….pn) always a prime.
Page 50 Problem 12 Answer
Given : pn is the nth prime number,
We have to establish each of the given statements: pn > 2n−1 for n ≥ 5.
Here,
The statement is correct for n = 5(p5 ⇒ 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 pk+1 − pk ≥ 2 (in other way if pk+1 = pk+1, then pk+1 is even)
Hence,
We get that
pk+1 ≥ pk + 2 > 2k−1 + 2 = 2(k+1)−1
Therefore,
pn > 2n−1 for n ≥ 5
Given : pn is the nth prime number,
We have to show that none of the integers
Pn = p1p2⋯pn + 1 is a perfect square.
We will show it by a contradiction.
Here,
Integer p2…pn is odd, so that exist an positive integer k such that p2…pn = 2k + 1,
Then we get that Pn is given of the form
Pn = 2(2k+1) + 1
= 4k + 3
Now,
If this integer is a perfect square, then exist an odd integer m = 2l + 1 (because Pn is odd)
such that Pn = m2.
Then we get next situation Pn = 4k + 3
= (2l+1)2
= 4l2 + 4l + 1
i.e. 4k + 2 = 4l2 + 4l
As we can see, 4 ∣ 4l2 + 4l but 4∤4k+1 which we have a contradiction.
Therefore,
None of the integers Pn = p1p2⋯pn+1 is a perfect square.
Given : pn 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 p1p2…pn-1 we have that p1p2…pn-1A = p2p3…pn-1+p1p3…pn-1+…+p1p2…pn-2+ \(\frac{p_1 p_2 \cdots p_{n-1}}{p_n}\) is an integer.
Also
p1p2…pn-1A − p2p3…pn-1 − p1p3…pn-1−…−p1p2…pn-2 = \(\frac{p_1 p_2 \cdots p_{n-1}}{p_n}\) is an integer too.
Hence, pn ∣ p1p2…pn-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 Rn∣Rm
We will use above information.
Here,
We have, n∣m, then exists an integer k > 0 such that m = kn.
So, repunit Rm is given of the form :
Rm = Rkn
= 11…1
= 10(k-1)nRn + 10(k-2)nRn+…+10nRn + Rn
Hence,
It is not hard to see that Rn ∣ Rm
Therefore,
If n ∣ m, then Rn ∣ Rm
Given : d ∣ Rn and d ∣ Rm
We have to show that d ∣ Rn+m
We will use above information.
Here,
We have, d ∣ Rn and d ∣ Rm, we need to show that d ∣ Rn+m.
Now,
Repunit Rm+n is given by : \(R_{m+n}=11 \ldots 1\)
= \(11 \ldots 1 \overbrace{00 \ldots 0}^n+\underbrace{1 \ldots 1}\)
= 10mRn + Rm
Hence,
It is not hard to see that d ∣ Rm+n.
Therefore,
If d ∣ Rn and d ∣ Rm, then d ∣ Rn+m
Given : gcd(n,m) = 1
We have to show that gcd(Rn,Rm) = 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 :
Rm-n = Rm−10m-nRn
Hence,
It is not hard to conclude that gcd(Rm,Rn) = gcd(Rm-n,Rn).
If we repeat this procedure k times, we get that
gcd(Rm,Rn) = gcd(Rm-n,Rn)
= …
= gcd(Rm-kn,Rm)
= gcd(Rr,Rm)
Now, using Theorem 2.1. we get that n = k1r + r1 for some integers 0 < k−1 and 0 ≤ r1 < r.
Then using preceding procedure we get that gcd(Rm,Rn) = gcd(Rr,Rm)
= gcd(Rr,Rr1)
As we can see our procedure is based on Euclidean algorithm, so after using it several times, we obtain
gcd(Rm,Rn) = Rgcd(m,n)
= R1
= 1
Now,
If gcd(Rm,Rn) = 1,
then gcd(m,n) = 1.
If d = gcd(m,n),
then using result from part b) we have that Rd ∣ Rm and Rd ∣ Rn.
So, Rd ∣ gcd(Rm,Rn) = 1
⇒ d = 1
Therefore,
If gcd(n,m) = 1,
then gcd(Rn,Rm) = 1
Page 50 Problem 14 Answer
We have to obtain the prime factors of the repunit R10
We will use result : If n ∣ m, then Rn ∣ Rm
Here,
We have, R2, R5 ∣ R10.
So, we repunit R10 is given of the form
R10 = R2⋅R5⋅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 R2 = 11 are prime numbers,
So, we need to obtain the prime factors of R5 = 11111.
Prime factors of this number are 271 and 41.
Hence,
R10 = 11⋅41⋅271⋅9091
Therefore,
R10 = 11⋅41⋅271⋅9091