David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution
Page 43 Problem 1 Answer
Given ;There are infinitely many primes of the form n{2}−2
To find : Exhibit five such primes.
There are infinitely many primes of the form n2 − 2,
2 = 22 − 2
7 = 32 − 2
23 = 52 − 2
47 = 72 − 2
79 = 92 − 2
Hence the list of the prime number are of the given form n{2}−2. 2,7,23,47,79.
Page 43 Problem 2 Answer
Given ; Every positive integer can be written in the form p + a2, where p is either a prime or 1, and a ≥ 0.
To find : Give an example to show that the following conjecture is not true:
Here We will give an example to show that the following conjecture is not true:
Every positive integer can be written in the form p+a2, where p is either a prime or 1.
Take x = 25, hence 25
= 0 + 25
= 21 + 4
= 9 + 16
= 16 + 9
But none of 0,4,9 and 16 is prime or 1
Hence we have shown that Every positive integer can be written in the form p + a{2} conjecture is not true: when x = 25
Page 43 Problem 3 Answer
Given ; Any prime of the form 3n+1 is also of the form 6m+1
To find : Prove each of the assertions below:
here we know that If a = 3n + 1 ⟹ 3 ∤ a,a ≠ 2,
so a is an odd prime not divisible by 3 .
By Division Algorithm, a = 6m + r,0 ≤ r < 6.
-r ≠ 0,since if r = 0
⟹ a = 6m⟹3∣a
−r≠2, since if r = 2 ⟹ a
= 6m + 2 = 2(3m+1)
⟹ 2 ∣ a
– r≠3, since if r = 3 ⟹ a.
= 6m + 3
= 3(2m+1)
⟹ 3 ∣ a
– r ≠ 4, since if r = 4 ⟹ a
= 6m + 4
= 2(3m+2)
⟹ 2 ∣ a
– r ≠ 5, since if r = 5.
a = 6m + 5
= 3(2m+1) + 2
⟹ 2 ∣ a
So, r must be 1 .
Hence we have proved that if r = 1 Any prime of the 3n+1 form is also of the form 6m+1
Given ; Each integer of the form 3n+2 has a prime factor of this form.
To find : Prove each of the assertions below:
let a be the integer of the form 3n + 2,a = 3n + 2.
Let p be the prime factor of a, then p = 3r + 1 or 3r+2.
Assume that every prime factor of a has the form 3r+1,
then a also has the form 3r+1, since the product of two or more numbers of the form 3r+1 is also of the form 3r+1,
i.e (3m+1)(3n+1) = 9nm + 3m + 3n + 1 = 3(3nm+m+n) + 1
So, a must have at least one prime factor of the form 3n+2, if not, a can not be of the form 3n+2.
Hence we conclude that if, a must have at least one prime factor of the form 3n+2, if not, a can not be of the form 3n+2.
Given ; The only prime of the form n3−1 is 7
To prove the given of the assertions
We have n = 2
Therefore, 7 = 23 − 1
= 8 − 1
= 7
So, 7 is of the form n{3}−1.
Now for n > 2,n3 − 1 = (n−1)(n2+n+1)
Since, n > 2 ⟹ n−1 > 1 so (n−1)∣(n3−1).
Thus, n3−1 can not be a prime.
We conclude that n3−1 can not be a prime.
Given ; The only prime P for which 3p+1 is a perfect square is p = 5.
To find ; Prove each of the assertions below:
3.5 + 1 = 16 is a perfect square.
Now assume for prime p, 3p + 1 = a2, a ∈ z.
If a = 3k ⇒ 3p + 1 = 9k2.
9k2 – 3p = 3(3k2-p)
So, 3|1 a contradiction.
So a must be of the form 3k+1 or 3k+2.
Now 3p + 1 = a2
3p = a2 – 1
⇒ p = (a-1)(a+1)
If a = 3k+1
p = \(\frac{(a-1)(a+1)}{3}\)
= \(\frac{(3 k)(3 k+2)}{3}\)
p = k(3k+2) a contradiction, since p is prime.
If a = 3k+2
p = \(\frac{(a-1)(a+1)}{3}\)
= \(\frac{(3 k+1)(3 k+3)}{3}\)
p = (k+1)(3k+1). a contradiction, since p is prime. Thus 3p+1 cannot be a perfect square.
Hence we conclude that p=(k+1)(3k+1). a contradiction, since p is prime. Thus 3p+1 can not be a perfect square
Given ; The only prime of the form n2−4 is 5
To find ; Prove each of the assertions below:
5 = 32 – 5 = 5
So, 5 is of the form n{2}-4.
For n > 5, n2-4 > 0.
Since n > 3 ⇒ n2 – 4 = (n-2)(n+2).
So (n-2) > 1 and it is a factor of n{2} – 4,
So n2 – 4 can not be prime.
Hence we conclude that (n−2) > 1 and it is a factor of n2−4, so n2−4 can not be prime.
Page 43 Problem 4 Answer
Given : If p ≥ 5 is a prime number,
To find ; show that p{2}+2 is composite.
But p on the form p = 3k + 1 or p = 3k + 2.
– If p = 3k + 1.
⟹ p−1 = 3k
⟹ 3∣(p−1)
⟹ 3∣(p−1)(p+1) + 3
So, 3∣(p2+2) ⟹ p2+2 is composite.
– If p = 3k + 2
⟹ p + 1
= 3(k+1)
⟹ 3∣(p+1)
⟹ 3∣(p−1)(p+1) + 3
So, 3∣(p2+2) ⟹ p2+2 is composite.
Hence we have proved that 3∣(p2+2) ⟹ p2+2 is composite.
Page 43 Problem 8 Answer
Given ; If p ≥ q ≥ 5 and p and q are both primes
To find ; prove that 24 ∣ p2−q2
Here we know p, q are odd primes. then they take one of these forms 3k+1 or 3k+2.
– If p = 3k+1 and q = 3m+1.
So p − q = 3(k−m).
⟹ 3∣(p−q)
⟹ 3∣(p−q)(p+q)
– If p = 3k+2 and q = 3m+2.
So p−q = 3(k−m).
⟹ 3∣(p−q)
⟹ 3∣(p−q)(p+q)
– If p = 3k+1 and q = 3m+2.
So p+q = 3(k+m)+3.
⟹ 3∣(p+q)
⟹ 3∣(p−q)(p+q)
Thus in all cases 3∣(p−q)(p+q) ⟹ 3∣p2−q2⋯
Now since p, q are primes, they take one of these forms 4r+1 or 4s+3.
– If p = 4r+1 and q = 4s+1.
So p2−q2,
= 16r2 + 8r + 1 − 16r2 − 8s − 1 = 8(2r2+r−2s2−s)
so 8∣p2−q2
– If p = 4r+3 and q = 4s+3.
So p2 − q2 = 16r2 + 24r + 9 − 16r2 − 24s − 9 = 8(2r2+3r−2s2−3s),
so 8∣p2−q2
– If p = 4r + 1 and q = 4s + 3.
So p2 − q2 = 16r2 + 8r + 1 − 16r2 − 24s − 9
8(2r2+r−2s2−3s−1)
so 8∣p2−q2
Thus in all cases 8∣(p−q)(p+q) ⟹ 8∣p2 − q2⋯(1),(2)
From and since gcd(8,3) = 1 ⟹ 24∣p2−q2
Hence we have conclude that in all cases 8∣(p−q)(p+q) ⟹ 8∣p2−q2⋯
From (1),(2) and since gcd(8,3) = 1
⟹ 24∣p2−q2
Page 43 Problem 9 Answer
Given ; An unanswered question is whether there are infinitely many primes that are 1 more than a power of 2 , such as 5 = 2{2}+1
To find ; Find two more of these primes.
We have 5 = 2{2}+1
17 = 24 + 1
and 257 = 28 + 1.
Hence we have found 2 more prime that are 17,257.
Given : A more general conjecture is that there exist infinitely many primes of the form n2 + 1; for example, 257 = 162 + 1
To find : Exhibit five more primes of this type.
Here put the value of n = 1, 2, 4, 6, 8 to find the prime number in the given form
we have n2+1;
257 = 162 + 1
12 + 1 = 2
22 + 1 = 5
42 + 1 = 17
62 + 1 = 37
102 + 1 = 101
Hence we have found 5 more prime in the form of n{2}+1 that s are 2,5,17,37,101
Page 43 Problem 10 Answer
Given ; . If p ≠ 5 is an odd prime
To find : prove that either p2−1 or p2+1 is divisible by 10.
here we will put the value of r and try to find that the given integers are divisible by 10
we know that p is odd prime, then by Division Algorithm p = 10q + r,
r = 1,3,7,9
– If r = 1,.
p = 10q + 1
⟹ p2−1 = 100q2 + 20q
= 10(10q2+2q)
⟹ 10∣(p2−1)
– If r = 3,
p = 10q + 3
⟹ p2+1
= 100q2 + 60q + 10
10(10q2+6q+1)
⟹ 10∣(p+−1)
– If r = 7,
p = 10q + 7
⟹ p2+1
= 100q2 + 140q + 50
10(10q2+14q+5)
⟹ 10∣(p2+1).
– If r = 9,
p = 10q + 9
p2−1 = 100q2 + 180q + 80
= 10(10q2+18q+8)
⟹ 10∣(p2−1)
In all cases either 10∣(p2−1) or 10∣(p2+1)
Hence we conclude that In all cases either 10∣(p2−1) or 10∣(p2+1) is divisible by 10.
Page 43 Problem 12 Answer
Given; 1234, 10140 and 36000
To find the prime factorization of the given integers
The given integers are 1234, 10140, and 36000.
1234 = 2.617
10140 = 22.5.3.132
36000 = 25.53.32
The prime factorization of the given integer is:
1234 = 2⋅617
10140 = 22⋅5⋅3⋅132
36000 = 25⋅53⋅32
Page 43 Problem 13 Answer
Given : If n > 1 is an integer not of the form 6k+3
To find ; prove that n{2}+2{n} is composite.
here we will try to find in all the cases that the number is composite or not
By division we have n = 2k
n = 2k+1
– If n is even, n = 2k so, (2k)2 + 22k = 4k2 + 4k
⟹ 2∣n2 + 2n
Thus n2 + 2n is composite.
– If n is odd, then n = 6k+1 or n = 6k+5
– If n = 6k + 1
n ≡ 1(3)
n2 ≡ 1(3)
and 2 ≡ −1(3)
2n ≡ −1(3) (since n is odd )
So, n2 + 2n ≡ 0(3)
Thus n2 + 2n is composite.
– If n = 6k + 5
n ≡ 2(3)
n2 ≡ 4 ≡ 1(3)
and 2 ≡ −1(3)
2n ≡ −1(3) (since n is odd )
So, n2 + 2n ≡ 0(3)
Thus n2+2n is composite.
Therefore in all cases we have that n2 + 2n, is composite.
Hence we conclude that n2+2n is composite.
Therefore in all cases we have that n{2}+2{n}, is composite.
Page 44 Problem 14 Answer
Given ; 6 = 29 − 23 = 137 − 131 = 599 − 593 = 1019 − 1013 = ⋯
To find : Express the integer 10 as the difference of two consecutive primes in 15 ways.
Here we will subtract 10 from all the given stes to find two consecutive numbers
We have 6 = 29 − 23 = 137 − 131 = 599 − 593 = 1019 − 1013 = ⋯
10 = 23 − 13 = 149 − 139 = 191 − 181
= 41 − 31 = 251 − 241 = 293 − 283
= 47 − 37 = 347 − 337 = 419 − 409
= 71 − 61 = 431 − 421 = 557 − 547
= 83 − 73 = 701 − 691 = 113 − 103
Hence we have Express the integer 10 as the difference of two consecutive primes in 15 ways. is given by
10 = 23 − 13 = 149 − 139 = 191 − 181
= 41 − 31 = 251 − 241 = 293 − 283
= 47 − 37 = 347 − 337 = 419 − 409
= 71 − 61 = 431 − 421 = 557 − 547
= 83 − 73 = 701 − 691 = 113 − 103
Page 44 Problem 15 Answer
Given ; A square if and only if in the canonical form of a all the exponents of the primes are even integers
To find ; Prove that a positive integer a > 1 is square
pi is prime. So, a = k2 = (p1r1p2r2….psrs)2
= (p12r1p22r2….ps2rs)
So, all the exponents are even.
i.e a = (p12m1 p22m2….. ps2ms)
a = (p1m1 p2m2…..psms)2
So, a is a square
Hence we conclude that a = (p1m1p2m2⋯psms)2 So, a is a square.
Page 44 Problem 16 Answer
Given ; An integer is said to be square-free if it is not divisible by the square of any integer greater than 1
To prove:
An integer n > 1 is square-free if and only if n can be factored into a product of distinct primes.
Assume n is square-free then for any a ∈ Z,a2∤n
Assume pr ∈ Z ∋ n = prp1p2⋯pn
r > 1 ⟹ r = 2 + s,s ≥ 0
Then \(\frac{n}{p^2}=\frac{p^{2+s} p_1 p_2 \cdots p_n}{p^2}\)
\(\frac{p^2 p^s p_1 p_2 \cdots p_n}{p^2}\)which is a contradiction.
Thus r must equal 1.
Assume n is a product of distinct primes
n = p1p2⋯pn
Assume ∃ a ∈ Z ∋ a2 ∣ n since a2 is square then a2 = q12r1q22r2⋯qs2rs contradiction
Hence we conclude that if n is a product of distinct primes n = p1p2⋯pn assume ∃ a ∈ Z ∋ a2 ∣ n since a2 is square then a2 = q12r1q22r2⋯qs2rs contradiction
Given ; An integer is said to be square-free if it is not divisible by the square of any integer greater than 1
To find ; Every integer n > 1 is the product of a square-free integer and a perfect square.
Here we have n = q12r1q22r2⋯qs2rs
,ri = 2pi + ri,
r = 0,1
n = q12p1+r1q22p2+r2⋯qs2ps+rs
= (q1r1q2r2⋯qsrs)(q1p1q2p2⋯qsps)2
Thus every integer is a product of a square free and a perfect square.
Hence we conclude that every integer is a product of a square free and a perfect square
Page 44 Problem 17 Answer
Given ; k ≥ 0 and m is an odd integer.
To find ; Verify that any integer n can be expressed as n = 2{k}m
here we will find whether m is odd or even if its odd then n = \(\prod_{i=1}^r p_i^{\alpha_i}=2^0 \prod_{i=1}^r p_i^{\alpha_i}=2^0 m\)
We know that by Fundamental theorem of Arithmetics
n = p1α1p2αs⋯psαs, either n is even or n is odd.
– If n is even then 2∣n or ∃ pj = 2 ∋ 1 ≤ i ≤ r
⇒ n = 2αj \(\prod_{i=1, i \neq j}^r p_i^{\alpha_i}\)
Thus, n = 2αjm (where m = \(\prod_{i=1, i \neq j}^r p_i^{\alpha_i}\) is odd.)
-If n is odd, then n = \(\prod_{i=1}^r p_i^{\alpha_i}\)
= [/latex]2^0 \prod_{i=1}^r p_i^{\alpha_i}[/latex]
= 20m
(where m = \(\prod_{i=1}^r p_i^{\alpha_i}\) is odd)
Hence we conclude that If n is odd, then
n = \(\prod_{i=1}^r p_i^{\alpha_i}=2^0 \prod_{i=1}^r p_i^{\alpha_i}=2^0 m\)
(where m = \(\prod_{i=1}^r p_i^{\alpha_i}\) is odd)
Page 44 Problem 18 Answer
Given ; Numerical evidence makes it plausible that there are infinitely many primes p such that is also prime. p + 50
To find ; List 15 of these primes.
we will start with 3 as a prime number and add 50 to get desired solution
we have prime p such that p + 50 is also a prime
(3,53) (47,97) (107,157) (11,61) (47,97)
(17,67) (17,67) (23,73) (29,79) (53,103)
(59,109) (83,133) (101,151) (107,157) (113,163)
Hence all the 15 prime number in the form p such that p + 50
(3,53) (47,97) (107,157) (11,61) (47,97)
(17,67) (17,67) (23,73) (29,79) (53,103)
(59,109) (83,133) (101,151) (107,157) (113,163)
Page 44 Problem 19 Answer
Given ; A positive integer n is called square-full, or powerful, if p2 ∣ n or every prime factor p of n , if n is square full
To find ; show that it can be written in the form n = a2b3, with a and b positive integers.
here we will show first whether kmi are odd (so kmi ≥ 3). and kn are even,
let n = p1k1⋯ prkr since n is square full, ki ≥ 2.
\(p_1^{k_1} \cdots p_r^{k_r}=q_{m_1}^{k_{m 1}} \cdots q_{m_s}^{k_{m s}} q_{n_1}^{k_{n 1}} \cdots q_{n_t}^{k_{t t}}\)Where kmi are odd (so kmi ≥ 3). and kni are even,
so kni = 2vi
n = \(q_{m_1}^{k_{m 1}} \cdots q_{m_s}^{k_{m s}}\left(q_{n_1}^{v_1} \cdots q_{n_t}^{v_t}\right)\)
= \(q_{m_1}^{k_{m 1}} \cdots q_{m_s}^{k_{m s}}\left(q_{n_1}^{v_1} \cdots q_{n_t}^{v_t}\right)^2\)
= \(q_{m_1}^{k_{m 1}} \cdots q_{m_s}^{k_{m s}}(g)^2, where g = (\left(q_{n_1}^{v_1} \cdots q_{n_t}^{v_t}\right))\)
since kmi is odd and ≥ 3, so kmi−3 is even.
n = \(q_{m_1}^3 \cdots q_{m_s}^3\left(q_{m_1}^{m-3} \cdots q_{m_s}^{m-3}\right)\left(g^2\right)\)
Let mi−3 = 2wi,
qm1⋯qms = b
∴ n = \(b^3\left(q_{m_1}^{2 w_1} \cdots q_m^{2 w_s}\right)\left(g^2\right)\)
Let f = \(q_{m_1}^{w_1} \cdots q_{m_s}^{w_s}\)
then n = b3f2g2
Let a = fg, then, n = a2b3
Hence we conclude that if kmi is odd and ≥ 3,so kmi − 3 is even.
n = \(q_{m_1}^3 \cdots q_{m_s}^3\left(q_{m_1}^{m-3} \cdots q_{m_s}^{m-3}\right)\left(g^2\right)\)
mi − 3 = 2wi,
qm1⋯qms = b
∴ n = \(b^3\left(q_{m_1}^{2 w_1} \cdots q_m^{2 w_s}\right)\left(g^2\right)\)
f = \(q_{m_1}^{w_1} \cdots q_{m_s}^{w_s}\)
then n = b3f2g2
a = fg, then, n = a{2}b{3}
Hence proved