## 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 n^{2} − 2,

2 = 2^{2} − 2

7 = 3^{2} − 2

23 = 5^{2} − 2

47 = 7^{2} − 2

79 = 9^{2} − 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 + a^{2}, 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+a^{2}, 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 n^{3}−1 is 7

To prove the given of the assertions

We have n = 2

Therefore, 7 = 2^{3} − 1

= 8 − 1

= 7

So, 7 is of the form n^{{3}}−1.

Now for n > 2,n^{3} − 1 = (n−1)(n^{2}+n+1)

Since, n > 2 ⟹ n−1 > 1 so (n−1)∣(n^{3}−1).

Thus, n^{3}−1 can not be a prime.

We conclude that n^{3}−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 = a^{2}, a ∈ z.

If a = 3k ⇒ 3p + 1 = 9k^{2}.

9k^{2} – 3p = 3(3k^{2}-p)

So, 3|1 a contradiction.

So a must be of the form 3k+1 or 3k+2.

Now 3p + 1 = a^{2}

3p = a^{2} – 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 n^{2}−4 is 5

To find ; Prove each of the assertions below:

5 = 3^{2} – 5 = 5

So, 5 is of the form n^{{2}}-4.

For n > 5, n^{2}-4 > 0.

Since n > 3 ⇒ n^{2} – 4 = (n-2)(n+2).

So (n-2) > 1 and it is a factor of n^{{2}} – 4,

So n^{2} – 4 can not be prime.

Hence we conclude that (n−2) > 1 and it is a factor of n^{2}−4, so n^{2}−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∣(p^{2}+2) ⟹ p^{2}+2 is composite.

– If p = 3k + 2

⟹ p + 1

= 3(k+1)

⟹ 3∣(p+1)

⟹ 3∣(p−1)(p+1) + 3

So, 3∣(p^{2}+2) ⟹ p^{2}+2 is composite.

Hence we have proved that 3∣(p^{2}+2) ⟹ p^{2}+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 ∣ p^{2}−q^{2}

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∣p^{2}−q^{2}⋯

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 p^{2}−q^{2},

= 16r^{2} + 8r + 1 − 16r^{2} − 8s − 1 = 8(2r^{2}+r−2s^{2}−s)

so 8∣p^{2}−q^{2}

– If p = 4r+3 and q = 4s+3.

So p^{2} − q^{2 }= 16r^{2} + 24r + 9 − 16r^{2} − 24s − 9 = 8(2r^{2}+3r−2s^{2}−3s),

so 8∣p^{2}−q^{2}

– If p = 4r + 1 and q = 4s + 3.

So p^{2} − q^{2} = 16r^{2} + 8r + 1 − 16r^{2} − 24s − 9

8(2r^{2}+r−2s^{2}−3s−1)

so 8∣p^{2}−q^{2}

Thus in all cases 8∣(p−q)(p+q) ⟹ 8∣p^{2} − q^{2}⋯(1),(2)

From and since gcd(8,3) = 1 ⟹ 24∣p^{2}−q^{2}

Hence we have conclude that in all cases 8∣(p−q)(p+q) ⟹ 8∣p^{2}−q^{2}⋯

From (1),(2) and since gcd(8,3) = 1

⟹ 24∣p^{2}−q^{2}

**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 = 2^{4} + 1

and 257 = 2^{8} + 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 n^{2} + 1; for example, 257 = 16^{2} + 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 n^{2}+1;

257 = 16^{2} + 1

1^{2} + 1 = 2

2^{2} + 1 = 5

4^{2} + 1 = 17

6^{2} + 1 = 37

10^{2} + 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 p^{2}−1 or p^{2}+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

⟹ p^{2}−1 = 100q^{2} + 20q

= 10(10q^{2}+2q)

⟹ 10∣(p^{2}−1)

– If r = 3,

p = 10q + 3

⟹ p^{2}+1

= 100q^{2} + 60q + 10

10(10q^{2}+6q+1)

⟹ 10∣(p+−1)

– If r = 7,

p = 10q + 7

⟹ p^{2}+1

= 100q^{2} + 140q + 50

10(10q^{2}+14q+5)

⟹ 10∣(p^{2}+1).

– If r = 9,

p = 10q + 9

p^{2}−1 = 100q^{2} + 180q + 80

= 10(10q^{2}+18q+8)

⟹ 10∣(p^{2}−1)

In all cases either 10∣(p^{2}−1) or 10∣(p^{2}+1)

Hence we conclude that In all cases either 10∣(p^{2}−1) or 10∣(p^{2}+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 = 2^{2}.5.^{3}.13^{2}

36000 = 2^{5}.5^{3}.3^{2}

The prime factorization of the given integer is:

1234 = 2⋅617

10140 = 2^{2}⋅5⋅3⋅13^{2}

36000 = 2^{5}⋅5^{3}⋅3^{2}

**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} + 2^{2k} = 4k^{2} + 4k

⟹ 2∣n^{2} + 2^{n}

Thus n^{2} + 2^{n} is composite.

– If n is odd, then n = 6k+1 or n = 6k+5

– If n = 6k + 1

n ≡ 1(3)

n^{2} ≡ 1(3)

and 2 ≡ −1(3)

2^{n} ≡ −1(3) (since n is odd )

So, n^{2} + 2^{n} ≡ 0(3)

Thus n^{2 }+ 2^{n} is composite.

– If n = 6k + 5

n ≡ 2(3)

n^{2} ≡ 4 ≡ 1(3)

and 2 ≡ −1(3)

2^{n} ≡ −1(3) (since n is odd )

So, n^{2} + 2^{n} ≡ 0(3)

Thus n^{2}+2^{n} is composite.

Therefore in all cases we have that n^{2} + 2^{n}, is composite.

Hence we conclude that n^{2}+2^{n} 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

p_{i} is prime. So, a = k^{2} = (p_{1}^{r1}p_{2}^{r2}….p_{s}^{rs})^{2
}

= (p_{1}^{2r1}p_{2}^{2r2}….p_{s}^{2rs})

So, all the exponents are even.

i.e a = (p_{1}^{2m1} p_{2}^{2m2}….. p_{s}^{2ms})

a = (p_{1}^{m1} p_{2}^{m2}…..p_{s}^{ms})^{2}

So, a is a square

Hence we conclude that a = (p_{1}^{m1}p_{2}^{m2}⋯p_{s}^{ms})^{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,a^{2}∤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 = p_{1}p_{2}⋯p_{n}

Assume ∃ a ∈ Z ∋ a^{2} ∣ n since a^{2} is square then a^{2} = q_{1}^{2r1}q_{2}^{2r2}⋯q_{s}^{2rs} contradiction

Hence we conclude that if n is a product of distinct primes n = p_{1}p_{2}⋯p_{n} assume ∃ a ∈ Z ∋ a^{2} ∣ n since a^{2} is square then a^{2} = q_{1}^{2r1}q_{2}^{2r2}⋯q_{s}^{2rs} 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 = q_{1}^{2r1}q_{2}^{2r2}⋯q_{s}^{2rs}

,r_{i} = 2p_{i} + r_{i},

r = 0,1

n = q_{1}^{2p1+r1}q_{2}^{2p2+r2}⋯q_{s}^{2ps+rs}

= (q_{1}^{r1}q_{2}^{r2}⋯q_{s}^{rs})(q_{1}^{p1}q_{2}^{p2}⋯q_{s}^{ps})^{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 = p_{1}α_{1}p_{2}α_{s}⋯p_{s}α_{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^{αj}m (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 p^{2} ∣ 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 = a^{2}b^{3}, with a and b positive integers.

here we will show first whether kmi are odd (so k_{mi} ≥ 3). and k_{n} are even,

let n = p_{1k}_{1}⋯ p_{rkr} since n is square full, k_{i} ≥ 2.

Where k_{mi} are odd (so k_{mi} ≥ 3). and k_{ni} are even,

so k_{ni} = 2v_{i}

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 k_{mi} is odd and ≥ 3, so k_{mi}−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 m_{i}−3 = 2w_{i},

q_{m1}⋯q_{ms} = 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 = b^{3}f^{2}g^{2}

Let a = fg, then, n = a^{2}b^{3}

Hence we conclude that if k_{mi} is odd and ≥ 3,so k_{mi} − 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)\)

m_{i} − 3 = 2w_{i},

q_{m1}⋯q_{ms} = 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 = b^{3}f^{2}g^{2}

a = fg, then, n = a^{{2}}b^{{3}}

Hence proved