David Burton

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

David Burton Elementary Number Theory Chapter 3 Exercise 3.2 Solutions

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₁p₂⋯pk,k ≥ 3

The first three primes factors are p₁,p₂,p₃ then

p₁ ∣ n,p₂ ∣ n,p₃ ∣ n

⟹ p₁p₂p₃ ∣ n ⟹ p ≥ p₁p₂p₃

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

p₁ > \(\sqrt[3]{n}\),p₂ > \(\sqrt[3]{n}\),p₃ > \(\sqrt[3]{n}\)

Thus p₁p₂p₃ > n contradiction, thus n > 1 is either a prime or the product of two prime

Hence we conclude that if p₁p₂p₃ > 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² and m².

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ⁿa = kⁿ.

Therefore, ln divides kⁿ!

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

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

Hence we conclude that lⁿa = kⁿ. 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

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ⁿa = kⁿ.

Therefore, lⁿ divides kⁿ!

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ⁿ.

Further, from the fact n < 2ⁿ we have the contradiction!

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

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

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

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.2 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₁,…,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₁,p₂,…,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..

Solutions To Chapter 3 Exercise 3.2 Burton Number Theory

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.

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.2 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₁,p₂,⋯,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₂p₃⋯p_i-1p_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.

Primes And Their Distribution Exercise 3.2 Answers David Burton

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.2 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.

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.2 Page 50 Problem 10 Answer

Let q_n be the smallest prime that is strictly greater than P_n = p₁p₂⋯p_n+1

It has been conjectured that the difference q_n−(p₁p₂⋯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₁p₂⋯p_n + 1

It has been conjectured that the difference q_n − p₁p₂⋯p_n is always a prime.

Now,

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

p₁ = 2

p₂ = 3

p₃ = 5

p₇,p₅ = 11

So,

P₁ = 2 + 1 ⇒ 3 ⟹ q₁ ⇒ 5,

⇒ q₁ − p₁ = 5 − 2 ⇒ 3 is prime.

P₂ = 2⋅3 + 1 ⇒ 7 ⟹ q₂ ⇒ 11,

⇒ q₂ − p₁p₂ = 11 − 6 ⇒ 5 is prime.

P₃ = 2⋅3⋅5 + 1 ⇒ 31 ⟹ q₃ ⇒ 37,

⇒ q₃ − p₁p₂p₃ = 37 − 30 ⇒ 7 is prime.

P₄ = 2⋅3⋅5⋅7 + 1 ⇒ 211 ⟹ q₄ ⇒ 223,

⇒ q₄ − p₁p₂p₃p₄ = 223 − 210 ⇒ 13 is prime.

P₅ = 2⋅3⋅5⋅7⋅11 + 1 ⇒ 2311 ⟹ q₅ ⇒ 2333,

q₅ − p₁p₂p₃p₄p₅ = 2333 − 2310 ⇒ 23 is prime.

Therefore,

The difference q_n – (p₁p₂….p_n) always a prime.

Chapter 3 Exercise 3.2 Burton Number Theory Key

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.2 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₅ ⇒ 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₁p₂⋯p_n + 1 is a perfect square.

We will show it by a contradiction.

Here,

Integer p₂…p_n is odd, so that exist an positive integer k such that p₂…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².

Then we get next situation ​Pn = 4k + 3

= (2l+1)²

= 4l² + 4l + 1
​
i.e. 4k + 2 = 4l² + 4l

As we can see, 4 ∣ 4l² + 4l but 4∤4k+1 which we have a contradiction.

Therefore,

None of the integers P_n = p₁p₂⋯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₁p₂…p_n-1 we have that p₁p₂…p_n-1A = p₂p₃…p_n-1+p₁p₃…p_n-1+…+p₁p₂…p_n-2+ \(\frac{p_1 p_2 \cdots p_{n-1}}{p_n}\) is an integer.

Also

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

Hence, p_n ∣ p₁p₂…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.

How To Solve Chapter 3 Exercise 3.2 Burton Number Theory

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.2 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)nR_n + 10^(k-2)nR_n+…+10ⁿ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^mR_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-nR_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₁r + r₁ for some integers 0 < k−1 and 0 ≤ r₁ < 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
​
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

Burton Number Theory Primes Exercise 3.2 Solutions

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.2 Page 50 Problem 14 Answer

We have to obtain the prime factors of the repunit R₁₀

We will use result : If n ∣ m, then R_n ∣ R_m

Here,

We have,  R₂, R₅ ∣ R₁₀.

So, we repunit R₁₀ is given of the form

R₁₀ = R₂⋅R₅⋅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₂ = 11 are prime numbers,

So, we need to obtain the prime factors of R₅ = 11111.

Prime factors of this number are 271 and 41.

Hence,

R₁₀ = 11⋅41⋅271⋅9091

Therefore,

R₁₀ = 11⋅41⋅271⋅9091

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

7 = 3² − 2

23 = 5² − 2

47 = 7² − 2

79 = 9² − 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², 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², 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

David Burton Elementary Number Theory Chapter 3 Exercise 3.1 Solutions

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.1 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³−1 is 7

To prove the given of the assertions

We have n = 2

Therefore,​ 7 = 2³ − 1

= 8 − 1

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

Now for n > 2,n³ − 1 = (n−1)(n²+n+1)

Since, n > 2 ⟹ n−1 > 1 so (n−1)∣(n³−1).

Thus, n³−1 can not be a prime.

We conclude that n³−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², a ∈ z.

If a = 3k ⇒ 3p + 1 = 9k².

9k² – 3p = 3(3k²-p)

So, 3|1 a contradiction.

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

Now 3p + 1 = a²

3p = a² – 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²−4 is 5

To find ; Prove each of the assertions below:

5 = 3² – 5 = 5

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

For n > 5, n²-4 > 0.

Since n > 3 ⇒ n² – 4 = (n-2)(n+2).

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

So n² – 4 can not be prime.

Hence we conclude that (n−2) > 1 and it is a factor of n²−4, so n²−4 can not be prime.

Solutions To Chapter 3 Exercise 3.1 Burton Number Theory

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.1 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) ⟹ p²+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) ⟹ p²+2 is composite.

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

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²−q²⋯

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²−q²,

= 16r² + 8r + 1 − 16r² − 8s − 1 = 8(2r²+r−2s²−s)
​
so  8∣p²−q²

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

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

so 8∣p²−q²

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

So ​p² − q² = 16r² + 8r + 1 − 16r² − 24s − 9

8(2r²+r−2s²−3s−1)
​
so 8∣p²−q²

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

From and since gcd(8,3) = 1 ⟹ 24∣p²−q²

Hence we have conclude that in all cases 8∣(p−q)(p+q) ⟹ 8∣p²−q²⋯

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

⟹ 24∣p²−q²

How To Solve Chapter 3 Exercise 3.1 Burton Number Theory

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.1 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⁴ + 1

and 257 = 2⁸ + 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² + 1; for example, 257 = 16² + 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²+1;

257 = 16² + 1
​
​1² + 1 = 2

2² + 1 = 5

4² + 1 = 17

6² + 1 = 37

10² + 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²−1 or p²+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²−1 = 100q² + 20q

= 10(10q²+2q)

⟹ 10∣(p²−1)
​
– If ​r = 3,

p = 10q + 3

⟹ p²+1

= 100q² + 60q + 10
​
​10(10q²+6q+1)

⟹ 10∣(p+−1)
​
– If ​r = 7,

p = 10q + 7

⟹ p²+1

= 100q² + 140q + 50
​
​10(10q²+14q+5)

⟹ 10∣(p²+1).
​
– If ​r = 9,

p = 10q + 9

p²−1 = 100q² + 180q + 80

= 10(10q²+18q+8)

⟹ 10∣(p²−1)
​
In all cases either 10∣(p²−1) or 10∣(p²+1)

Hence we conclude that In all cases either 10∣(p²−1) or 10∣(p²+1) is divisible by 10.

Solutions Guide For Chapter 3 Exercise 3.1 Burton Number Theory

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.1 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².5.³.13²

36000 = 2⁵.5³.3²

The prime factorization of the given integer is:
​
1234 = 2⋅617

10140 = 2²⋅5⋅3⋅13²

36000 = 2⁵⋅5³⋅3²

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^2k = 4k² + 4k

⟹ 2∣n² + 2ⁿ
​
Thus n² + 2ⁿ is composite.

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

– If n = 6k + 1

n ≡ 1​(3)

n² ≡ 1​(3)

and 2 ≡ −1​(3)

2ⁿ ≡ −1​(3) (since n is odd )

So, n² + 2ⁿ ≡ 0​(3)

Thus n² + 2ⁿ is composite.

– If n = 6k + 5

n ≡ 2​(3)

n² ≡ 4 ≡ 1​(3)

and 2 ≡ −1​(3)

2ⁿ ≡ −1​(3) (since n is odd )

So, n² + 2ⁿ ≡ 0​(3)

Thus n²+2ⁿ is composite.

Therefore in all cases we have that n² + 2ⁿ, is composite.

Hence we conclude that n²+2ⁿ is composite.

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

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.1 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² = (p₁^r₁p₂^r₂….p_s^rs)²

= (p₁^2r₁p₂^2r₂….p_s^2r_s)

So, all the exponents are even.

i.e a = (p₁^2m₁ p₂^2m₂….. p_s^2m_s)

a = (p₁^m₁ p₂^m₂…..p_s^m_s)²

So, a is a square

Hence we conclude that a = (p₁^m₁p₂^m₂⋯p_s^m_s)² So, a is a square.

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.1 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²∤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}\)

which is a contradiction.

Thus r must equal 1.

Assume n is a product of distinct primes

n = p₁p₂⋯p_n

Assume ∃ a ∈ Z ∋ a² ∣ n since a² is square then a² = q₁^2r₁q₂^2r₂⋯q_s^2r_s contradiction

Hence we conclude that if n is a product of distinct primes n = p₁p₂⋯p_n assume ∃ a ∈ Z ∋ a² ∣ n since a² is square then a² = q₁^2r₁q₂^2r₂⋯q_s^2r_s 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₁^2r₁q₂^2r₂⋯q_s^2r_s

,r_i = 2p_i + r_i,

r = 0,1
​
​n = q₁^2p₁+r₁q₂^2p₂+r₂⋯q_s^2p_s+r_s

= (q₁^r₁q₂^r₂⋯q_s^r_s)(q₁^p₁q₂^p₂⋯q_s^p_s)²

​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

Exercise 3.1 Burton Elementary Number Theory Problem Walkthrough

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₁α​₁p₂α​_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^α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)

David Burton Elementary Number Theory Solutions Chapter 3 Primes And Their Distribution Exercise 3.1 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² ∣ 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²b³, with a and b positive integers.

here we will show first whether km​i are odd (so k_mi ≥ 3). and k_n are even,

let n = p_1^k1⋯ p_r^kr 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³f²g²

Let a = fg, then, n = a²b³

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³f²g²

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

Hence proved

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers

Page 24 Problem 1 Answer

Here ,we have to show that (-a)|b, a|(-b), and (-a)|(-b)

Let a∣b then ∃ c ∋ a⋅c = b
​
⟹ a⋅c = (−a)⋅(−c) = b ⟹ (−a)∣b

⟹ −(a⋅c) = −b = a⋅(−c) ⟹ a∣(−b)

⟹ −(a⋅c) = −b = (−a)⋅c ⇒ (−a)∣(−b)

Thus, we show that (−a)∣b, a∣(−b), and (−a)∣(−b).

David Burton Elementary Number Theory Chapter 2 Exercise 2.3 Solutions

Page 24 Problem 2 Answer

Here, we have to verify that if a∣b then a∣bc

Let a∣b then ∃x ∋ a⋅x = b

∴ ac = bc ⟹ a ∣ bc

Thus, we verified that if a ∣ b, then a ∣ bc

Here, we have to verify that if a∣b and a∣c then a²∣ bc

Let a∣b and a∣c then, ∃ x,y ∋ ax = b,ay = c

∴ (ax)(ay) = bc = a²xy ⟹ a² ∣ bc

Thus, we verified that if a∣b and a∣c, then a² ∣ bc

Here, we have to verify that a∣b if and only if ac ∣ bc, where c ≠ 0

Let a∣b then ∃ x ∋ ax = b,

∴ acx = bc = a²xy ⟹ ac ∣ bc

Now, let ac ∣ bc then ∃ x ∋ acx = bc

Since, c ≠ 0 ∴ ax = b ⟹ a ∣ b

Thus, we verified that a∣b if and only if ac ∣ bc, where c ≠ 0

Here, we have to verify that if a ∣ b and c ∣ d, then ac ∣ bd

Let a∣b and c∣d then, ∃ x, y ∋ ax = b,cy = d

∴ (ax)(cy) = ac(xy) = bd ⟹ ac ∣ bd.

Thus, we verified that a ∣ b and c ∣ d then, ac ∣ bd

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.3 Page 24 Problem 4 Answer

Here, we have to use mathematical induction to establish the divisibility statements, 8∣52n + 7.It’s given that 5^2(k+1) + 7 = 5²(5^2k+7) + (7−5²⋅7).

For n = 1:5²ⁿ + 7 = 25 + 7 = 32 and 8 ∣ 32.Suppose it’s true for n = k then we want to prove it for n = k + 1.

Let 8 ∣ 5^2k + 7 ∴ ∃ x ∋ 8x = 5^2k + 7

Now, for n = k + 1

​5^2(k+1) + 7 = 5²⋅5^2k + 7

= 5²(5^2k+7) − 5²⋅7 + 7

= 5²(8x) − 5² − 7(5²−1)

= 5²(8x) − 7(24)

= 8x(25) − 8(7⋅3)

= 8(25x−21)

∴ 8 ∣ 5^k+1

Thus, by mathematical induction for n ≥ 1,8 ∣ 5ⁿ

Thus, we have to use mathematical induction to establish the divisibility statements 8 ∣ 5²ⁿ + 7

Here, we have to use mathematical induction to establish the divisibility statements, 15 ∣ 2⁴ⁿ − 1

For, n = 1 : 2⁴ − 1 = 16 − 1 = 15 and 15 ∣ 15.Suppose it’s true for n = k then we want to prove it for n = k + 1.

Let 15 ∣ (2^4k−1) ∴ ∃ x ∋ 15x = 2^4k − 1

Now, for n = k + 1

2^4(k+1) − 1 = 2⁴⋅2^4k − 1 + 2⁴ − 2⁴

= 2⁴(2^4k−1) + (2⁴−1)

= 2⁴(15x) + 15

= 15(x2⁴+1)

∴ 15 ∣ 2^4(k+1) − 1
​
Thus, by mathematical induction for n ≥ 1,15 ∣ 2⁴ⁿ − 1

Thus, we use mathematical induction to establish the divisibility statements, 15 ∣ 2⁴ⁿ − 1

Here, we have to use mathematical induction to establish the divisibility statements, 5 ∣ 3³ⁿ⁺¹ + 2ⁿ⁺¹

For n = 1 : 3³⁺¹ + 2² = 81 + 4 = 85 and 5 ∣ 85. Suppose it’s true for n = k then we want to prove it for n=k+1.

Let 5 ∣(3^3k+1 + 2^k+1) ∴ ∃ x ∋ 5x = 3^3k+1 + 2^k+1

Now for n = k + 1

3^3(k+1)+1 − 2^k+2 = 3^3k+4 − 2^k+2

= 3³⋅3^3k+1 + 2⋅2^k+1 + 3⋅2^k+1 − 3³⋅2^k+1

= 3³(3^3k+1 + 2^k+1) − 2^k+1(3³−2)

= 3³(5x) − 2^k+1(25)

= 5(x3³ − 5⋅2^k+1)

∴ 5 ∣ (3³ⁿ⁺¹ + 2ⁿ⁺¹)
​
Thus, by mathematical induction for n ≥ 1, 5 ∣ 2⁴ⁿ − 1

Thus, we use mathematical induction to establish the divisibility statements, 5 ∣ 2⁴ⁿ−1

Here, we have to use mathematical induction to establish the divisibility statements, 21 ∣ 4ⁿ⁺¹ + 5^2n-1

For ,n = 1: 4² + 5¹ = 21 and 21 ∣ 21.Suppose, it’s true for n = k then we want to prove it for n = k + 1.

Let 21 ∣ (4^k+1+5^2k-1) ∴ ∃ x ∋ 21x = 4^k+1 + 5^2k-1

Now, for n = k + 1

​4^3(k+2) − 5^2(k+1)−1 = 4^k+2 − 5^2k+1

= 4⋅4^k+1 + 5²⋅5^2k-1 + 4⋅5^2k-1− 4⋅5^2k-1

= 4(4^k+1 + 5^2k-1) + 21(5^2k-1)

= 4(21x) + 21(5^2k-1)

= 21(4x+5^2k-1)

∴ 21 ∣ (4^(k+1)+1 + 5^2(k+1)-1)
​
Thus, by mathematical induction for n ≥ 1, 21∣(4^k+1 + 5^2k+1)

Thus, we use mathematical induction to establish the divisibility statements, 21 ∣ 4ⁿ⁺¹ + 5^2n-1

Here, we have to use mathematical induction to establish the divisibility statements, 24 ∣ 2⋅7ⁿ + 3⋅5ⁿ−5

Now we want to prove by mathematical induction that 24 ∣ 4⋅7^k + 20 for s = 1: 4⋅7¹ + 20 = 48 and 24 ∣ 48

Suppose it’s true for k = s then we want to prove it for k=s+1

Let 24 ∣ 4⋅7^s + 20 ∴ ∃ x ∋ 24x = 4⋅7^s + 20

Now, for n = k + 1

​4⋅7^s+1 + 20 = 7(4⋅7^s)+20

= 7(4⋅7^s+20) + 20 − 140

= 7(24y) − 24⋅5

∴ ∃ q ∋ 24q = 4⋅7^k + 20
​
∴ eq (1) = 5(24x) + 24q

Thus, by mathematical induction for n ≥ 1,24 ∣ 2⋅7ⁿ + 3⋅5ⁿ−5

Thus, we use mathematical induction to establish the divisibility statements, 24 ∣ 2⋅7ⁿ + 3⋅5ⁿ−5

Solutions To Chapter 2 Exercise 2.3 Burton Number Theory

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.3 Page 24 Problem 5 Answer

Here, we have to prove that for any integer a one of the integers a,a+2,a+4 is divisible by 3

From the division algorithm, we know that every a is on the form 3q, 3q+1 or 3q+2

Case 1: Suppose a = 3q, then a is divisible by 3

Case 2: Suppose a = 3q + 1,then a + 4 = 3q + 6 = 3(q+2),then a+2 is divisible by 3

Case 3: Suppose a = 3q + 2,then a+4 = 3q + 6 = 3(q+2).Thus a+1 is divisible by 3

therefore for any integer a,any of the forms a,a+2 or a+4 is divisible by 3

Thus, we prove that for any integer a one of the integers a, a+2, a+4 is divisible by 3

Page 25 Problem 6 Answer

Here, we have to verify that 2∣a(a+1), and 3∣a(a+1)(a+2)

According to the division algorithm, every a is of the form 2q or 2q+1

Case 1: If a = 2q then a + 1 = 2q + 1, since a is even ⟹ 2∣a ⟹ 2∣a(a+1)

Case 2 : If a = 2q + 1 then

a + 1 = 2q + 2 = 2(q+1), since a + 1 is even ⟹ 2∣a+1 ⟹ 2∣a(a+1)

According to division algorithm, every a is of the form 3q,3q+1 or 3q+2

Case 1 : If a = 3q then

3∣a ⟹ 3∣a(a+1)(a+2)

Case 2 : If a = 3q + 1 then,

a + 2 = 3q + 3 = 3(q+1),thus

3 ∣a + 2 ⟹ 3∣a(a+1)(a+2)

Case 3: If a = 3q + 2,then

a + 1 = 3q + 3 = 3(q+1),thus

3∣a + 1 ⟹ 3∣a(a+1)(a+2)

Thus, we verify that 2∣a(a+1), and 3∣a(a+1)(a+2).

Here, we have to verify that 3∣a(2a²+7)

According to the division algorithm, every a is of the form, 3q,3q+1, or 3q+2

Case 1 : If a = 3q then,3 ∣ a ⟹ 3∣a(2a²+7)

Case 2: If a = 3q + 1 then, a² = 9q² + 6q + 1, ​

​⟹ 2a² + 7 = 2(9q²+6q+1) + 7

= 18q² + 12q + 9 = 3(6q²+4q+3)

thus 3∣∣2a² + 7 ⟹ 3∣∣a(2a²+7)
​
Case 3: If a = 3q + 2 then, a² = 9q² + 12q + 4, ​

​⟹ 2a² + 7 = 2(9q²+12q+4) + 7

= 18q² + 24q + 15 = 3(6q²+8q+5)

Thus 3 ∣ 2a² + 7 ⟹ 3 ∣ a(2a²+7)

Thus, we verified 3 ∣ a(2a²+7)

Here, we have to verify that if a is odd ,then 32 ∣ (a²+3)(a²+7)

According to the division algorithm, every a is in the form 4q + r​ ∋ 0 ≤ r ≤ 3. But a is odd then the only possible forms of a are 4q+1 or 4q+3

Case 1 : If a = 4q + 1, then a² = 16q² + 8q + 1

⟹ a² + 3 = 16q² + 8q + 4 = 4(4q²+2q+1)​⋯(1)

a² + 7 = 16q² + 8q + 8 = 8(2q²+q+1)​⋯(2)

From (1) and (2)

(a²+3)(a²+7) = [4(4q²+2q+1)][8(2q²+q+1)]

​= 32(4q²+2q+1)(2q²+q+1)

Thus 32 ∣ (a²+3)(a²+7)

Case 2 : If a a = 4q + 3 then,

a² = 16q² + 24q + 9
​
​⟹ a² + 3 = 16q² + 24q + 12 = 4(4q²+6q+3)​⋯(1)

a² + 7 = 16q² + 24q + 16 = 8(2q²+3q+2)​⋯(2)
​
from (1) and (2)

(a²+3)(a²+7) = [4(4q²+6q+3)][8(2q²+3q+2)]

​= 32(4q²+6q+3)(2q²+3q+2)

Thus 32 ∣ (a²+3)(a²+7)

Thus, we verified if a is odd ,then 32∣(a²+3)(a²+7)

Page 25 Problem 7 Answer

Here, we have to prove that if a and b are both odd integers, then 16 ∣ a⁴ + b⁴ − 2

Since a and b are both odd integers then a = 2r + 1 and b = 2s + 1 where k, l ∈ Z.

Now,

a⁴ + b⁴ – 2 = (2r+1)⁴ + (2s+1)⁴ – 2

= \(\left(\begin{array}{l}
4 \\
0
\end{array}\right)(2 r)^4+\left(\begin{array}{l}
4 \\
1
\end{array}\right)(2 r)^3+\left(\begin{array}{l}
4 \\
2
\end{array}\right)(2 r)^2+\left(\begin{array}{l}
4 \\
3
\end{array}\right)(2 r)+1\)

+\(\left(\begin{array}{l}
4 \\
0
\end{array}\right)(2 s)^4+\left(\begin{array}{l}
4 \\
1
\end{array}\right)(2 s)^3+\left(\begin{array}{l}
4 \\
2
\end{array}\right)(2 s)^2+\left(\begin{array}{l}
4 \\
3
\end{array}\right)(2 s)+1-2\)

= 16(r⁴+s⁴) + 32(r³+s³) + 24r² + 8r + 24s² + 8s

to prove that 16 ∣ a⁴ + b⁴ − 2 we just need 16 ∣ 24r² + 8r

If r is odd then r = 2k + 1,then
​
​24(2k+1)² + 8(2k+1)

= 96k² + 96k + 24 + 16k + 8

= 96k² + 96k + 16k + 32

= 16(8k²+8k+k+2)
​
If r is even then r = 2k,thus

24(2k)² + 8(2k) = 96k² + 16k = 16(8k²+k)

Thus, 16 ∣ 24r² + 8r, similarly 16 ∣ 24s² + 8s

∴ 16 ∣ a⁴ + b⁴ − 2

Thus, we prove that if a and b are both odd integers, then 16 ∣ a⁴ + b⁴ − 2

Divisibility Theory Exercise 2.3 Answers David Burton

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.3 Page 25 Problem 8 Answer

Here, we have to prove that the sum of the squares of two odd integers cannot be a perfect square.

Let a and b be odd integers, then a = 2r + 1 and b = 2s + 1 for some r, s ∈ Z.

Now,

a² + b² = (2r+1)² + (2s+1)² = 4r² + 4r + 1 + 4s² + 4s + 1 = 4(r²+s²+r+s) + 2 = 4k + 2

where, k = r² + s² + r + s

Suppose a² + b² is a perfect square, then a² + b² = c² = 4k + 2 = 2(2k+1)

Then c² is even ⇒ c is even, so c = 2m ⟹ c² = 4m² = 4l where l = m²

Thus, a² + b² = c² ⟹ 4k + 2 = 4l,this contradict the uniqueness of division algorithm, ∴ a² + b² ≠ c² if a, b are odd

Thus, we proved that the sum of the squares of two odd integers cannot be a perfect square.

We have to prove that the product of four consecutive integers is 1 less than a perfect square.

Consider the four consecutive integers be k, k+1, k+2 and k+3

The product of these integers will be,
​
k(k+3)(k+1)(k+2) = (k²+3k)(k²+3k+2)

=((k²+3k+1)−1)((k²+3k+1)+1)

= (k²+3k+1)² − 12

Now let​(k²+3k+1) = p where p is some integer.

Hence (k²+3k+1)² = p²

Therefore we have,

k(k+3)(k+1)(k+2) = p² − 1

Hence we have proved that the product of four consecutive integers is 1 less than a perfect square.

Page 25 Problem 9 Answer

We have to establish that the difference of two consecutive cubes is never divisible by 2.

Consider the two consecutive numbers be a and a+1

Here ∤ symbolize does not divide and ∣ means does divide.

We have to prove 2 ∤ (a+1)³ − a³

Solving (a+1)³ − a³ we get,
​
(a+1)³ − a³ = a³ + 3a² + 3a + 1 − a³

= 3a² + 3a + 1

= 3a(a+1) + 1
​
Now,

if a is even then,
​
2 ∣ a

⇒ 2 ∣ a(a+1)
​
if a is odd, then a+1 is even, then,

2 ∣ a + 1

⇒ 2 ∣ a(a+1)
​
So 2 ∣ a(a+1)

Therefore,

x ∈ Z, 2x = a(a+1)

Thus,
​
3a(a+1) + 1 = 3(2x)+1

= 2(3x) + 1
​
which is odd.

Hence 2∤(a+1)³ − a³.

Hence we have proved that 2 ∤ (a+1)³ − a³.

Page 25 Problem 10 Answer

We have to show that

gcd(a,0) = ∣a∣

gcd(a,a) = ∣a∣

gcd(a,1) = 1

Sincea∣0 and a∣a,then ∣a∣ is a common divisor of a and 0.

Now, let b be another common divisor of a,0.

Then,
​
b ∣ a

⇒ ∣b∣ ≤ ∣a∣
​
Thus ∣a∣ is the greatest common divisor of a and 0.

Since a∣a, then ∣a∣ is a common divisor of a. Now, let b be another common divisor of a and a.

Then,
​
b ∣ a

⇒ ∣b∣ ≤ ∣a∣
​
Thus ∣a∣ is the greatest common divisor of a and a.

Since 1∣a and 1∣1,then 1 is a common divisor of a and 1.

Now, let b be another common divisor of a,1.

Then,
​
b ∣ 1

⇒ ∣b∣ ≤ 1
​
Thus 1 is the greatest common divisor of a and 1.

Hence we have proved that,
​
​gcd(a,0) = ∣a∣

gcd(a,a) = ∣a∣

gcd(a,1) = 1

Burton Number Theory Divisibility Exercise 2.3 Solutions

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.3 Page 25 Problem 12 Answer

We have to prove that, for a positive integer n and any integer a, gcd(a,a+n) divides n and hence,gcd(a,a+1) = 1

Here a|b means a divides b

Let gcd(a,a+1) = d, then d|a and d|a+n

But we know that gcd(a, a+n) divides any linear combination of a and a+n.

Thus

d|(a+n) – a

⇒ d|n

Now, let gcd(a, a+1) = t

Therefore,

t|a + 1 – a

⇒ t|a

⇒ t ≤ 1

⇒ t = 1

Hence we have proved that for a positive integer n and any integer a,gcd(a,a+n) divides n and hence,gcd(a,a+1) = 1

Page 25 Problem 13 Answer

We are given integers a and b.

We have to prove that there exist integers x and y for which c = ax + by if and only ifgcd(a,b)∣c.

Let us assume c = ax + by,

Now let gcd(a,b) = d,

then d∣a and d∣b

thus there exists,
​
​t,l in Z

a = dt

b = dl
​
Therefore,
​
c = ax + by

= dtx + dly

= d(tx+ly)

d∣c

Hence we have proved that there exist integers x and y for which c = ax + by if and only if gcd(a,b)∣c.

Given: Integers a and b, we have to prove:

If there exists integers x and y for which ax + by = gcd(a,b), then gcd(x,y) = 1

Let us assume gcd(a,b)∣c and let gcd(a,b) = d.

This implies c = fd for some f∈Z.

Then, ∃ s,r ∈ Z∋.

d = sa + rb

This implies:
​
c = fd

= f(sa+rb)

= (fs)a + (fr)b

= xa + yb
​
Where, ​x = fs

y = fr

Proved that if there exists integers x and y for which ax + by = gcd(a,b), then gcd(x,y) = 1.

Page 25 Problem 15 Answer

We are given thata and b are integers, not both of which are zero.

We have to prove that gcd(2a−3b,4a−5b) divides b and hence,gcd(2a+3,4a+5) = 1

We have,
​
−2(2a−3b) + (4a−5b) = −4a + 6b + 4a − 5b

−2(2a−3b) + (4a−5b) = b
​
Thus gcd(2a−3b,4a−5b) ∣ b.

Since​ 2(2a+3)−(4a+5) = 4a + 6 − 4a − 5

= 1
​
Thus gcd(2a+3,4a+5) ∣ 1 ⟹ gcd(2a+3,4a+5) = 1

Hence we have proved that gcd(2a−3b,4a−5b) divides b and hence,gcd(2a+3,4a+5) = 1

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.3 Page 25 Problem 17 Answer

We have to prove that the expression(3n)!/(3!)² is an integer for all n ≥ 0.

For n = 1, we have,

Hence the result is true for n = 1

Now let us assume that the result is true for n = k we have,

\(\frac{(3 \cdot 1) !}{(3 !)^1}\) = l, l is any integer

Now we have to prove that the result is true for n = k + 1

we have,

= \(\frac{(3 k) !}{(3 !)^k} \cdot \frac{(3 k+3)(3 k+2)(3 k+1)}{6}\)

= \(l \cdot \frac{(k+1)(3 k+2)(3 k+1)}{2}\)

Now,

If k is even then,
​
k = 2r

⇒ 3k + 2 = 6r + 2

= 2(3r+1)
​
and hence 2 ∣ 3k + 2

If k is odd then,
​
k = 2r + 1

⇒ k + 1 = 2r + 2

= 2(r+1)
​
and hence 2∣k + 1

Therefore we conclude \(\frac{(k+1)(3 k+2)(3 k+1)}{2}\) is an integer, therefore \(\frac{(3(k+1)) !}{(3 !)^{k+1}}\) is an integer.

So by mathematical induction we have, (3n)!/(3!)ⁿ is an integer for all n ≥ 0.

We have proved that the expression(3n)!/(3!)​ⁿ is an integer for all n ≥ 0.

Page 25 Problem 18 Answer

We are given a statement,

The product of any three consecutive integers is divisible by 6.

We have to prove the above statement.

Here a|b means a divides b

Let the three consecutive integers be

n, (n+1), (n+2).

Since 6 = 2.3 and gcd(2,3) = 1

If n is even, then,

2|n

⇒ 2|n(n+1)(n+2)

If n is odd, then n+1 is even and hence,

2|(n+1)

⇒ 2|n(n+1)(n+2)

Now, by division algorithm, n = 3k+r, 0 ≤ r < 3.

If n = 3k + 1, then,

n+2 = 3k+3

= 3(k+1)

and thus

3|(n+1)

⇒ 3|n(n+1)(n+2)

If n – 3k + 2, then

n+1 = 3k+3

= 3(k+1)

and thus

3|(n+1)

⇒ 3|n(n+1)(n+2)

Therefore we have

2|n(n+1)(n+2) and 3|n(n+1)(n+2), thus 6|n(n+1)(n+2)

We have proved that the product of any three consecutive integers is divisible by 6.

Elementary Number Theory Burton Chapter 2 Exercise 2.3 Explanations

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.3 Page 25 Problem 19 Answer

We are given,

If a is an arbitrary integer, then 6 ∣ a(a²+11).

We have to establish the given assertion.

By division algorithm, a = 6q + r, 0 ≤ r < 6

If r = 0,

​⟹ a = 6q

⟹ 6∣a

So, 6∣a(a²+11).
​

If r = 1,

​
​⟹ a = 6q + 1

⟹ (a²+11) = 36q² + 12q + 12

= 6(6q²+2q+2)

So, 6∣(a²+11)

⟹ 6∣a(a²+11)
​
If r = 2

​⟹ a = 6q + 2

= 2(3q+1)
​

So,
​
2∣a and (a²+11)

(a²+11) = 36q² + 24q + 15

= 3(12q²+8q+5)

So, 3∣(a²+11)⟹6∣a(a²+11)

⟹ 6a(a²+11)
​
If r = 3

​⟹ a = 6q + 3

= 3(2q+1)

So, 3∣a

(a²+11) = 36q² + 36q + 20

(a²+11) = 2(18q²+18q+10)

So,

2∣(a²+11) ⟹ 6∣a(a²+11)
​
If r = 4

​​⟹ a = 6q + 4

= 2(3q+2)
​
So,

2∣a and (a²+11)
​
(a²+11) = 36q² + 24q + 27

= 3(12q²+8q+9)

So, 3∣(a²+11) ⟹ 6∣a(a²+11)

⟹ 6a(a²+11)
​
If r = 5,

​⇒ a = 6q + 5

⇒ (a²+11) = 36q² + 60q + 36

= 6(6q²+10q+6)

So, 6∣(a²+11)

⇒ 6 ∣ a(a²+11)
​
Therefore in all cases 6 ∣ a(a²+11)

We have proved that if a is an arbitrary integer, then 6∣a(a²+11).

We are given,

If a is an order integer, then 24 ∣ a(a²−1)

We have to establish the given assertion.

Since a is odd then a is in the form
​
a = 4k + 1 or

a = 4k + 3

= 4k−1.
​
Let​ a = 4k + 1

⟹ a² = 16k² + 8k + 1

= 8(2k²+k) + 1
​
so, a²= 8m + 1 where

m = 2k² + k.

Thus,​a(a²−1) = (4k+1)(8m+1)

= 32km+8m

= 8(4km+m).
​
So 8∣a(a²−1)​⋯(1)

Similarly if a = 4k−1,k ∈ Z.

If r = 0

​⇒ 3∣a

⇒ 3∣a(a²−1).
​
If r = 1

​⇒ a = 3q + 1

⇒ a² − 1 = 9q² + 6q

= 3(3q²+2q).
​
So,​3∣(a²−1)

⟹ 3a(a²−1)
​
If r = 2

​⟹ a = 3q + 2

⟹ a²−1 = 9q² + 12q + 3

= 3(3q²+4q+1).
​
So,​ 3∣(a²−1)

⟹ 3a(a²−1)
​
Since,

gcd(8,3) = 1

24 ∣ a(a²−1)

We have proved that If a is an odd integer, then 24|a(a²-1).

We are given that a and b are odd integers.

We have to prove that 8∣(a²−b²)

Assuming that a,b are odd integers, then we have three cases,

If ​a = 4k+1

b = 4m+1
​
then,
​
a²−b² = (16k²+8k+1)−(16m²+8m+1)

= 16(k²−m²)+8(k−m)

= 8(2(k²−m²)+(k−m)).
​
Hence 8∣a²−b²

If​ a = 4k−1

b = 4m−1
​
then,
​
a²−b² = (16k²−8k+1)−(16m²−8m+1)

= 16(k²−m²)−8(k−m)

= 8(2(k²−m²)−(k−m))
​
Hence 8∣a²−b²

If​ a = 4k−1

b = 4m + 1
​
then,
​
a² − b² = (16k²−8k+1) − (16m²+8m+1)

= 16(k²−m²) + 8(k+m)

= 8(2(k²−m²) + (k+m)).
​
Hence 8∣a²−b²

Therefore we conclude that 8∣a²−b²

We have proved that if a and b are odd integers, then 8∣(a²−b²)

We are given an assertion,

If a is an integer not divisible by 2 or 3, then 24∣(a²+23).

We have to prove the assertion.

As a is not divisible by 2, then a is odd. Thus a=4k+1 or 4k−1

Since a is not divisible by 3,Thus a = 3q + 1 or 3q + 2

Therefore we have four cases.

Case 1

If​ a = 4k + 1

= 3q + 1
​
So,
​
(a²+23) = (16k²+8k+24)

(a²+23) = 8(2k²+k+3)
​
Thus 8∣(a²+23)…(1)

Also,
​
(a²+23) = 9q² + 6q + 24

(a²+23) = 3(3q³+2q+8)
​
Thus 3∣(a²+23)…(2)

Therefore from(1) and (2) we have, 24∣(a²+23)

Case 2

If​ a = 4k−1

= 3q + 2
​
So,
​
(a²+23) = (16k²−8k+24)

= 8(2k²−k+3).
​
Thus 8∣(a²+23)…(1)

Also,
​
(a²+23) = 9q² + 12q + 27

(a²+23) = 3(3q³+4q+9)
​
Thus 3∣(a²+23)…(2)

Therefore from(1) and (2) we have, 24∣(a²+23)

Case 3

If a = 4k + 1

= 3q + 2
​
So,
​
(a²+23) = (16k²+8k+24)

(a²+23) = 8(2k²+k+3)
​
Thus 8∣(a²+23)…(1)

Also,
​
(a²+23) = 9q² + 12q + 27

(a²+23) = 3(3q³+4q+9)
​
Thus 3∣(a²+23)…(2)

Therefore from(1) and (2) we have,

24∣(a²+23)

Case 4

If ​a = 4k − 1

= 3q + 1

So,
​
(a²+23) = (16k²−8k+24)

= 8(2k²−k+3).
​
Thus 8∣(a²+23)…(1)

Also,
​
(a²+23) = 9q² + 6q + 24

(a²+23) = 3(3q²+2q+8)
​
Thus 3∣(a²+23)…(2)

Therefore from(1) and (2) we have,

24∣(a²+23)

Therefore we conclude that 24∣(a²+23)

Hence we have proved that if a is an integer not divisible by 2 or 3, then 24∣(a²+23).

We have to prove that if a is an arbitrary integer, then 360∣a²(a²−1)(a²−4).

We have,
​
a²(a²−1)(a²−4) = a²(a+1)(a−1)(a+2)(a−2)

= (a−2)(a−1)(a)(a+1)(a+2)(a)
​
Also 360 = 5 × 9 × 8 where5,8,9 are relatively prime.

Now we know that(a−2)(a−1)(a)(a+1)(a+2) is divisble by 24 and 120, and therefore it′s divisble by 8 and 5

Also,(a−2)(a−1)(a) and (a+1)(a+2)(a) are both divisible by 6 and so are both divisible by 3.

Thus(a−2)(a−1)(a)(a+1)(a+2)(a) is divisible by 9.

Therefore,
​
5⋅8⋅9∣a²(a²−1)(a²−4)

⇒ 360∣a²(a²−1)(a²−4)

We have proved that if a is an arbitrary integer, then 360∣a²(a²−1)(a²−4).

Page 25 Problem 20 Answer

We are given,

gcd(a,b) = 1

gcd(a,c) = 1

We have to prove that gcd(a,bc) = 1

We have,
​
​gcd(a,b) = 1

gcd(a,c) = 1
​
Therefore,
​
1 = ax + by

1 = af + ct
​
for some x,y,f,t in Z

Hence we have,
​
1 = (ax+by)(af+ct)

= a²xf + abyf + acxt + bcyt

= a(axf+byf+cxt) + bcyt

= ak₁+ bck₂

Therefore a, bc are relatively prime.

Hence, gcd(a,bc) = 1

We have proved that if,
​
gcd(a,b) = 1,

and gcd(a,c) = 1,

then gcd(a,bc) = 1

We are given,

gcd(a,b) = 1

c∣a

We have to prove gcd(b,c) = 1

We have gcd(a,b) = 1

Therefore ax + by = 1 for some x,y in Z

Also as c∣a

There exist as in Z such that cs=a, where cs belongs to Z

Therefore,

cst + bf = 1

Thus gcd(b,c) = 1

We have proved that if gcd(a,b) = 1 and c∣a then, gcd(b,c) = 1

We have to prove that if gcd(a,b) = 1 then,

gcd(ac,b) = gcd(c,b)

Let gcd(c,b) = d, then there exists x,y in Z such that,

d = cx + by.

Since d∣c there existsn such that dn = c, and so we have,
​
d(na) = ca⟹d∣ca

⇒ d∣ca.
​
Now let k∣ac and k∣b, then there exists m such that km = b, therefore

d = cx + kmy.

Since gcd(a,b) = 1, there exists p,q such that,

ap + bq = 1

Therefore,
​
apc + bqc = c

⇒ d = (apc+bqc)x + kmy

d = acpx + knqcx + kmy
​
Butk∣ac

Hence there existsr such that kr = ac

Therefore,
​
d = krpx + knqcx + kny

d = k(rpx+nqcx+ny)
​
And hence k∣d and therefore gcd(c,b) = gcd(ac,b)

We have proved that if gcd(a,b) = 1 then,

gcd(ac,b) = gcd(c,b)

We are given,

gcd(a,b) = 1

c∣a+b

We have to prove that,
​
gcd(a,c) = 1

gcd(b,c) = 1

If gcd(a,b) = c then there exists, x,y in Z such that,

c = ax + by

We have,c∣a + b therefore, there existsn such that cn = a + b and hence,

a = cn−b

Therefore,
​
(cn−b)x + by = 1

cnx − bx + by = 1

cnx + b(y−x) = 1
​
So gcd(c,b) = 1

Similarly,
​
cn − a = b

ax + (cn−a)y = 1

ax + cny − ay = 1

a(x−y) + cny = 1
​
So,gcd(c,a) = 1.

We have proved that if gcd(a,b) = 1, and c∣a + b then,
​
​gcd(a,c) = 1

gcd(b,c) = 1

We are given,

gcd(a,b) = 1

d∣ac

d∣bc

We have to prove that d∣c

We have,

gcd(a,b) = 1, then for some x,y in Z

ax + by = 1

Therefore,

c = cax + cby…(1)

Now as d∣ac

Therefore,
​
ac = dr

c = \(\frac{d r}{a}\)

Also,
​
d∣bc

⇒ bc = dm

⇒ c = \(\frac{d m}{b}\)

Using above (1) we get,

c = \(\frac{d r}{a} a x+\frac{d m}{b} b y\)

c = drx + dmy

c = d(rx+my)

Therefore d|c

We have proved if gcd(a,b) = 1,d∣ac, and d∣bc, then d∣c.

Page 26 Problem 21 Answer

Given : d ∣ n is given. We need to prove 2^d−1∣2ⁿ−1.

We will do it by using the identity.

It is given that d∣n.

We can also write it as dm = n, here m is some integer.

So we can also write :

2ⁿ−1 = 2^dm−1

= (2^d)^m−1

Now we will use the identity :

x^k-1 = (x−1)(x^k-1+x^k-2+⋯+x+1)

Now we have ,

2ⁿ−1 = (2^d)^m−1

= (2^d-1)((2^d)^m-1+(2^d)^m-2+⋯+(2^d)+1)

Hence, 2^d−1∣2ⁿ−1.

2^d – 1|2ⁿ-1 by using the identity:

x^k-1 = (x-1)(x^k-1 + x^k-2+…+x+1).

2³⁵ – 1 is given.

We will verity that 2³⁵-1 is divisible by 31 and 127.

We will do it by using the identity.

We have :

31 = 2⁵−1 and 127=2⁷−1

And we have that 5∣35.

Now using the identity :

x^k-1 = (x−1)(x^k-1+x^k-2+⋯+x+1) we have ,

31 = 2⁵−1∣2³⁵−1

And similarly we have 7∣35.

So, again using the identity we get :

127 = 2⁷−1∣2³⁵−1

Yes, 2³⁵−1 is divided by 31 and 127.

Exercise 2.3 Burton Elementary Number Theory Problem Walkthrough

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.3 Page 26 Problem 22 Answer

Given : Let t_ndenote the nth triangular number.

We will find for what values of n does t_n divide the sum t₁+t₂+⋯+t_n.

We will do it by using the formula above.

We have:

t₁ + t₂ + …+ t_n = \(\frac{n(n+1)(n+2)}{6}\)

t_n = \(\frac{n(n+1)}{2}\).

Now, therefore:

= \(\frac{n+2}{3}\)

So, at the \(\frac{n+2}{3}\) integer tn divides t₁ + t₂ + …. + t_n.

Therefore, the form of n is n = 3k + 1 and the values of n are 1,4,7,10,……

At the \(\frac{n+2}{3}\) integer tn divides t₁ + t₂ + …. + t_n.

Therefore, the form of n is n = 3k + 1 and the values of n are 1,4,7,10,….

Page 26 Problem 23 Answer

a | b is given.

We need to show that a| gcd(a,b)gcd(a,c).

We will prove it by using the formula of gcd(a,b).

a|bc is given that means bc = ax where x∈Z (let us consider this equation one).

Now we have :

gcd(a,b) = am + bn ,where m,n∈Z and

gcd(a,c) = ar + bs , where r,s∈Z.

Now we have :

gcd(a,b)⋅gcd(a,c) = a²mr + acms + abrn + bcns

Now using equation one we get :

= a²mr + acms + abrn + axns

= a(amr+cms+brn+xns)

Hence , a ∣ gcd(a,b)⋅gcd(a,c) is proved.

Yes, a∣gcd(a,b)⋅gcd(a,c) is proved.

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers

Page 19 Problem 1 Answer

Here, we have to prove that if a and b are integers, with b > 0 then there exist unique integers q and r satisfying a = qb + r, where 2b ≤ r < 3b

Proof : By division algorithm, ∃ unique q′ and r′, such that a = q′b + r′,0 ≤ r′ < b

∴ a = q′b + r′ + 2b − 2b = (q′−2)b + r′+2b. Let q = q′− 2,r = r′ + 2b,

Therefore r and q are unique.

Since, 0 ≤ r′ < b, then 2b ≤ r′ + 2b < b + 2b ⟹ 2b ≤ r < 3b

Thus, we have proved that if a and b are integers, with b > 0,then there exist unique integers q and r satisfying a = qb + r, where 2b ≤ r < 3b

David Burton Elementary Number Theory Chapter 2 Exercise 2.2 Solutions

Page 19 Problem 2 Answer

Here, we have to show that any integer of the form 6k + 5 is also of the form 3j + 2,but not conversely

Proof : If a = 6k + 5 = 3⋅2k + 3 + 2 = 3(2k+1)+ 2 = 3j+ 2 where j = 2k + 1. To disprove that any integer of the form 3j + 2 is also of the form 6k + 5.Take 3j + 2 where j is even, i.e j = 2r ⇒ 3(2r) + 2 = 6r + 2,but r and 2 are unique, so 3j + 2 ≠ 6k + 5

Thus, we proved that any integer of the form 6k + 5 is also of the form 3j + 2, but not conversely

Page 19 Problem 3 Answer

Here, we have to use the Division Algorithm to establish, the square of any integer is either of the form 3k or 3k + 1

Proof : By division algorithm ∃a and q such that a = 3q,a = 3q + 1 or a = 3q + 2

If a = 3q: ∴ a² = 9q² = 3(3q²) = 3k where k = 3q²

If a = 3q + 1: ∴ a² = 9q² + 6q + 1 = 3(3q²+2q) + 1 = 3k + 1 where k = 3q² + 2q

If a = 3q + 2: ∴ a² = 9q² + 12q + 4 = 9q² + 12q + 3 + 1 = 3(3q²+4q+1) + 1 = 3k+1 where k = 3q² + 4q + 1

Thus, we use the Division Algorithm to establish, the square of any integer is either of the form 3k or 3k+1

Here, we have to use the Division Algorithm to establish, the cube of any integer has one of the forms: 9k, 9k+1 or 9k+8

Proof : By division algorithm ∃a and q such that a = 3q+r,r = 0,1,2

If \(a=3 q: (3 q)^3=27 q^3=9\left(3 q^3\right)=9 k \text { where } k=3 q^3\)

If \(a = 3 q+1: (3 q+1)^3=\left(\begin{array}{l}
3 \\
0
\end{array}\right)(3 q)^3+\left(\begin{array}{l}
3 \\
1
\end{array}\right)(3 q)^2+\left(\begin{array}{l}
3 \\
2
\end{array}\right) 3 q+\left(\begin{array}{l}
3 \\
3
\end{array}\right)\)

=\(27 q^3+27 q^2+9 q+1\)

=\(9\left(3 q^3+\right.\left.3 q^2+q\right)+1\)

=\(9 k+1 \text { where } k=3 q^3+3 q^2+q\)

If a = \(3 q+2: (3 q+2)^3=\left(\begin{array}{l}
3 \\
0
\end{array}\right)(3 q)^3+\left(\begin{array}{c}
3 \\
1
\end{array}\right)(3 q)^2 \cdot 2+\left(\begin{array}{l}
3 \\
2
\end{array}\right) 3 q \cdot 2^2+\left(\begin{array}{c}
3 \\
3
\end{array}\right) \cdot 2^3\)

=\(27 q^3+54 q^2+36 q+8\)

= \(9\left(3 q^3+3 q^2+4 q\right)+8=9 k+8 \text { where } k=3 q^3+3 q^2+4 q\)

Thus, we used the Division Algorithm to establish, the cube of any integer has one of the forms : 9k, 9k+1 or 9k+8

Here, we have to use the Division Algorithm to establish the fourth power of any integer is either of the form : 5k, 5k+1

Proof : By division algorithm, ∃a and q such that a = 5q + r,0 ≤ r < 5.Consider n⁴ = (5q+r)⁴,from binomial expansion, each term is a factor of 5 except last term.

⇒ \((5 q+r)^4=5\left[\left(\begin{array}{c}
4 \\
0
\end{array}\right) 5^3 q^4+\left(\begin{array}{c}
4 \\
1
\end{array}\right) 5^2 q^3 r+\left(\begin{array}{c}
4 \\
2
\end{array}\right) 5 q^2 r^2+\left(\begin{array}{c}
4 \\
1
\end{array}\right) q r^3\right]+r^4\)

⇒ \((5 q+r)^4=5 k+r^4 \text { where } k=\left(\begin{array}{c}
4 \\
0
\end{array}\right) 5^3 q^4+\left(\begin{array}{c}
4 \\
1
\end{array}\right) 5^2 q^3 r+\left(\begin{array}{c}
4 \\
2
\end{array}\right) 5 q^2 r^2+\left(\begin{array}{c}
4 \\
1
\end{array}\right) q r^3\)

If r = 0 then r⁴ = 0, and n⁴ = 5k as all other terms have 5 as a factor

If r = 1 then r⁴ = 1,then clearly n⁴ = 5k + 1

If r = 2 then r⁴ = 16 = 15 + 1 = 3⋅5 + 1, so n⁴ = 5k + 1

If r = 3 then r⁴ = 81 = 80 + 1 = 5⋅16 + 1, so n⁴ = 5k + 1

If r = 4 then r⁴ = 256 = 255 + 1 = 5⋅51 + 1, so n⁴ = 5k + 1

Thus, we use the Division Algorithm to establish the fourth power of any integer is either of the form 5k or 5k+1

Solutions To Chapter 2 Exercise 2.2 Burton Number Theory

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.2 Page 19 Problem 4 Answer

Here, we have to prove that 3a² − 1 is never a perfect square

Proof :

Suppose 3a² − 1 = n², some n by Ex3(a),

3a² − 1 = 3k + 1 or 3a^{2} − 1 = 3k

∴ 3(a²−k) = 2 or 3(a²−k) = 1,

but each are impossible, since by division algorithm, 2 = 3⋅0 + 2 and 1 = 3⋅0 + 1

Thus, we proved that 3a² − 1 is never a perfect square.

Page 19 Problem 5 Answer

Here, we have to prove that n(n+1)(2n+1)/6 is an integer.

Proof: By division algorithm, ∃n and k such that n = 6k + r, 0 ≤ r < 6. Let A = \(\frac{n(n+1)(2 n+1)}{6}\)

If r = 0 then, A = k(6k+1)(12k+1) is an integer

If r = 1 then

A = \(\frac{(6 k+1)(6 k+2)(12 k+3)}{6}\)

A = \(\frac{(6 k+1) 2(3 k+1) 3(4 k+1)}{6}\)

= (6k+1)(3k+1)(4k+1) is an integer

If r = 2 then

A = \(\frac{(6 k+2)(6 k+3)(12 k+5)}{6}\)

A = \(\frac{2(3 k+1) 3(2 k+1) (12 k+5)}{6}\)

= (6k+1)(3k+1)(4k+1) is an integer

If r = 3 then,

A = \(\frac{(6 k+3)(6 k+4)(12 k+7)}{6}\)

A = \(\frac{3(2 k+1) 2(3 k+1) (12 k+7)}{6}\)

= (2k+1)(3k+2)(12k+7) is an integer

If r = 4 then

A = \(\frac{(6 k+4)(6 k+5)(12 k+9)}{6}\)

A = \(\frac{2(3 k+2) (6 k+5) 3(4 k+3)}{6}\)

= (3k+2)(6k+5)(4k+3) is an integer

If r = 5 then,

A = \(\frac{(6 k+5)(6 k+6)(12 k+11)}{6}\)

A = \(\frac{(6 k+5) 6( k+1) (12 k+11)}{6}\)

= (6k+1)(3k+1)(4k+1) is an integer

Thus for n ≥ 1, \(\frac{n(n+1)(2 n+1)}{6}\) is an integer.

Thus, we prove that for n ≥ 1 n(n+1)(2n+1)/6 is an integer

Page 19 Problem 6 Answer

Here, we have to show that the cube of any integer is of the form 7k or 7k ± 1

Proof : By division algorithm, ∃n and q such that n = 7q + r,0 ≤ r < 7.Consider n³ = (7q+r)³,from binomial expansion, each term is a factor of 7 except last term,

(7q+r)³ = \(\left(\begin{array}{l}
3 \\
0
\end{array}\right)(7 q)^3+\left(\begin{array}{l}
3 \\
1
\end{array}\right)(7 q)^2 r+\left(\begin{array}{l}
3 \\
2
\end{array}\right)(7 q)^2 r^2+r^3\)

If r = 0 then, r³ = 0and n³ = 7k as all other terms have 7 as a factor.

If r = 1then, r³ = 1,then clearly n³ = 7k + 1

If r = 2then,

r³ = 8 = 7 + 1, so n³ = 7k + 1

If r = 3then,

r³ = 27 = 28 − 1 = 4⋅7 − 1, sо n³ = 7k − 1

If r = 4then,

r³ = 64 = 63 + 1 = 9⋅7 + 1, and n³ = 7k + 1

If r = 5then,

r³ = 125 = 126−1 = 18⋅7 − 1, so n³ = 7k − 1

If r = 6then,

r³ = 216 = 217 − 1 = 31⋅7 − 1, so n³ = 7k + 1

Thus, the cube of any integer is of the form 7k, 7k+1 or 7k−1

Divisibility Theory Exercise 2.2 Answers David Burton

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.2 Page 19 Problem 7 Answer

Obtain the following version of the Division Algorithm: For integers a and b, with b ≠ 0, there exist unique integers q and r that satisfy a = qb + r, where \(-\frac{1}{2}|b|<r \leq \frac{1}{2}|b|\).

It is required to obtain a following version of Division Algorithm: For integers a and b, with b≠0, there exists unique integers q and r that satisfy a = qb + r, where \(-\frac{1}{2}|b|<r \leq \frac{1}{2}|b|\).

The division algorithm for integers states that given any two integers a and b with b > 0, there exists unlque integers q and r such that a = qb + r, where 0 ≤ r < b.

Therefore, according to the division algorithm, there exists unique integers q′ and r′ such that a = q′b + r′, where 0 ≤ r′ < ∣b∣. Consider 0 < ∣b∣, this can be further divided into intervals, 0 < \(\frac{1}{2}|b|\) and \(\frac{1}{2}|b|\) < ∣b∣

Now, if 0 ≤ r’ ≤ \(\frac{1}{2}|b|\), let r = r’ and q = q’, and if \(\frac{1}{2}|b|\) < r’ < |b|, then \(-\frac{1}{2}|b|\) < r’ – |b| < 0, this gives,

a = q’b + r’ – |b| + |b|

If |b| ≥ 0, then |b| = b, that is,

a = q’b + r’ – |b| + b

This gives,

a = (q′+1)b + r′ − ∣b∣, therefore, let q = q′ + 1 and r = r′ − ∣b∣

If ∣b∣ < 0, then ∣b∣ = −b, that is,

a = q′b + r′ − ∣b∣ − b

This gives, a = (q′−1)b + r′ − ∣b∣, therefore, let q = q′ − 1 and r = r′ − ∣b∣

Therefore, if

\(\frac{1}{2}|b|\) < r’ < |b| = |b| – \(\frac{1}{2}|b|\) < r’ < |b| ⇒ \(-\frac{1}{2}|b|\) < r’ < 0 ⇒ \(-\frac{1}{2}|b|\) < r’ < 0 < \(\frac{1}{2}|b|\),

that is,

Hence, for integers a and b. with b ≠ 0, there exists unique integers q and r that satisfy a = qb + r, where \(-\frac{1}{2}|b|<r \leq \frac{1}{2}|b|\).

Page 19 Problem 8 Answer

Here, we have to prove that no integer in the following sequence is a perfect square: 11,111,1111,11111,…

It’s given that a typical term 111⋅⋅⋅⋅⋅111 can be written as

111⋯111 = 111⋯108 + 3 = 4k + 3

Proof: Any number in sequence can be written as

A = 11 + 100 + 1000 + ….. = 11 + \(\sum_{i=2}^n 10^i\)

Each term of \(\sum_{i=2}^n 10^i\) is divisible by 4. So,

A_i= 11 + 4r_i = 4(r+2) + 3, for certain r_i

So, A_i = rr’_i + 3 by division algorithm, r’ and 3 are unique. Suppose A_i = s² let s = 4q + r

r ≠ 0,as

s² = 16q² = 4(4q²),which is not of the form 4r_i′ + 3

r ≠ 1,as

s² = 16q² + 8q + 1 = 4(4q²+2q) + 1,which is not of the form 4r_i′ + 3

r ≠ 2,as

s² = 16q² + 16q + 4 = 4(4q² + 4q + 1),which is not of the form 4r_i′ + 3

r ≠ 3,as

s² = 16q² + 24q + 9 = 4(4q² + 2q + 2) + 1,which is not of the form 4r_i′ + 3

Therefore there is no s such that s² = 4r_i + 3. All A_i are not perfect squares

Thus, we proved that no integer in the following sequence is a perfect square, 11,111,1111,11111,…

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.2 Page 19 Problem 9 Answer

Here, we have to verify that if an integer is simultaneously a square and a cube (as is the case with 64 = 8² = 4³),then it must be either of the form 7k or 7k+1

Proof : By division algorithm, ∃s and k such that s = 7k + b,0 ≤ b < 7.Consider s³ = (7k+b)³, from binomial expansion, each term is a factor of 7 except last term,

(7k+b)³ = \(\left(\begin{array}{c}
3 \\
0
\end{array}\right)(7 k)^3+\left(\begin{array}{c}
3 \\
1
\end{array}\right)(7 k)^3 b+\left(\begin{array}{c}
3 \\
2
\end{array}\right)(7 k)^2 b^2+b^3\)

If b = 0 then, b³ = 0, and n³ = 7k as all other terms have 7 as a factor.

If b = 1 then, b³ = 1,then clearly n³ = 7k + 1

If b = 2 then,

b³ = 8 = 7 + 1,so n³ = 7k + 1

If b = 3 then,

b³ = 27 = 28 − 1 = 4⋅7 − 1, so n³ = 7k − 1

If b = 4 then,

b³ = 64 = 63 + 1 = 9⋅7 + 1, and n³ = 7k + 1

If b = 5 then,

b³ = 125 = 126 − 1 = 18⋅7 − 1, so n³ = 7k − 1

If b = 6 then,

b³ = 216 = 217 − 1 = 31⋅7−1, so n³ = 7k + 1

Now by division algorithm, ∃r and c such that r = 7c + d,0 ≤ d < 7 then,

If d = 0 then,r² = 7(7c²) = 7k

If d = 1 then,

r² = 49c² + 14c + 1 = 7(7c²+2c) + 1 = 7k + 1

If d = 2 then,

r² = 49c² + 28c + 4 = 7(7c²+4c) + 4 = 7k + 4

If d = 3 then,

r² = 49c² + 42c + 9 = 7(7c²+6c+1) + 2 = 7k + 2

If d = 4 then,

r² = 49c² + 56c + 16 = 7(7c²+8c+2) + 2 = 7k + 2

If d = 5 then,

r² = 49c² + 70c + 25 = 7(7c²+10c+3) + 4 = 7k + 4

If d = 6 then,

r² = 49c² + 84c + 36 = 7(7c²+12c+5) + 1 = 7k + 1

Thus r² is of the form : 7k, 7k+1, 7k+2 or 7k+4 and s³ is of the form :7k, 7k+1 or 7k+6. By uniqueness part of division algorithm, A must be either of form 7k or 7k+1

Thus, we verify that if an integer is simultaneously a square and a cube (as is the case with 64 = 8² = 4³),then it must be either of the form 7k or 7k+1

How To Solve Chapter 2 Exercise 2.2 Burton Number Theory

Page 19 Problem 10 Answer

Here, we have to establish that the integer n(7n²+5) is of the form 6k

By division algorithm n=6k+r, 0 ≤ r < 6

If n = 6k then,(6k)(7(36k²)+5) = 6t

If n = 6k + 1 then,

(6k+1)(7(6k+1)²+5) = (6k+1)(7(36k²+12k+1)+5) = 6(6k+ 1) (7(6k²+2k)+2) = 6t

If n = 6k + 2 then,

2(3k+1)(7(6k+2)²+5) = 2(3k+1)(7(36k²+24k+4)+5) = 6(3k+ 1) (7(12k²+8k)+11) = 6t

If n = 6k + 3 then,

3(2k+1)(7(6k+3)²+5) = 3(2k+1)(7(36k²+36k+9)+5) = 6(6k+ 1) (7(18k²+18k)+34) = 6t

If n = 6k + 4then,

2(3k+2)(7(6k+4)²+5) = 2(3k+2)(7(36k²+48k+16)+5) = 2(3k+ 2) (7(12k²+16k)+39) = 6t

If n = 6k + 5 then,

(6k+5)(7(6k+5)²+5) = (6k+5)(7(36k²+60k+25)+5) = (6k+5)(7(36k²+60k)+180) = 6(6k+5)(7(6k²+10k)+30) = 6t

Thus, in all cases we have n(7n²+5) is of the form 6k

Thus, we establish that the integer n(7n²+5) is of the form 6k

Elementary Number Theory Burton Chapter 2 Exercise 2.2 Explanations

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.2 Page 19 Problem 11 Answer

Here, we have to show that n⁴ + 4n² + 11 is of the form 16k

Since, n is odd then n = 2r + 1

n⁴ + 4n² + 11 = (n²+2)² + 7

= [(2r+1)²+2]² + 7

= (4r²+4r+1+2)² + 7

= (4r²+4r+3)² + 7

= [(4r²+4r)+3]² + 7

= (4r²+4r)² + 2⋅(4r²+4r)⋅3 + 9 + 7

= 16r⁴ + 2⋅4r²⋅4r + 16r² + 24r² + 24r + 9 + 7

= 16r⁴ + 32r³ + 16r² + 24r² + 24r + 9 + 7

= 16r⁴ + 32r³ + 40r² + 24r + 16

Now, by division algorithm, r = 2q or 2q + 1

If r = 2q: ​

​16(2q)⁴ + 32(2q)³ + 40(2q)² + 24(2q) + 16

= 16[(2q)⁴ + 2(2q)³ + 10q² + 3q + 1]

= 16k

If r = 2q + 1:​

​16(2q+1)⁴ + 32(2q+1)³ + 40(2q+1)² + 24(2q+1) + 16

= 16(2q+1)⁴ + 32(2q+1)³ + 160q² + 160q + 40 + 48q + 24 + 16

= 16[(2q+1)⁴ + 2(2q+1)³ + 10q² + 10q + 3q + 4 + 1]

= 16k

Thus, we showed that n⁴ + 4n² + 11 is of the form 16k

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers

Page 15 Problem 1 Answer

Here, we have to prove that a number is triangular if and only if it is of the form n(n+1)/2 for some n ≥ 1. It’s given that each of the numbers 1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3, 10 = 1 + 2 + 3 + 4,… represents the number of dots that can be arranged evenly in an equilateral triangle:

Proof: Remember that we proved in sec 1.1 that, 1 + 2 + 3 + …. + n = \(\frac{n(n+1)}{2}\). So, if f is triangular, then for some n, 1 + 2 + 3 + …. + n = f by definition, and so f = \(\frac{n(n+1)}{2}\) for some n, then

f = 1 + 2 + 3 + … + n

Thus, we proved that a number is triangular if and only if it is of the form n(n+1)/2 for some n ≥ 1

Here, we have to prove that the integer n is a triangular number if and only if 8n + 1 is a perfect square. it’s given that each of the numbers 1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3, 10 = 1 + 2 + 3 + 4,… represents the number of dots that can be arranged evenly in an equilateral triangle:

Proof: (⇒) if n is triangular, then there is a k ∃ n = \(\frac{k(k+1)}{2}\).

∴ 8n = 4k(k+1)

8n + 1 = 4k(k+1) + 1

= 4k² + 4k + 1

= (2k+1)²

Therefore n is triangular ⇒ 8n + 1 is a perfect square.

if 8n + 1 is a perfect square, then there is an integer k ∃ k² = 8n + 1. Note that 8n+1 must be odd. k² is odd, and so k is odd, so there is an r ∃ 2r + 1 = k

(2r+1)² = 8n + 1

4r² + 4r + 1 = 8n + 1

4r(r+1) = 8n

\(\frac{r(r+1)}{2}\) = n

Therefore, 8n + 1 is a perfect square ⇒ n is triangular.

Thus, we proved that integer n is a triangular number if and only if 8n+1 is a perfect square.

Here, we have to prove that the sum of any two consecutive triangular numbers is a perfect square. It’s given that each of the numbers, 1 = 1,3 = 1 + 2,6 = 1 + 2 + 3,10 = 1 + 2 + 3 + 4,… represents the number of dots that can be arranged evenly in an equilateral triangle:

Proof: We want to prove that if k and l are consecutive triangular numbers, then k+l is a perfect square.

Let, 1 + 2 + 3 + ⋯ + n = k, then 1 + 2 + 3 + ⋯ + n + n + 1 = l

∴ k + l = \(\frac{n(n+1)}{2}+\frac{n(n+1)}{2}+(n+1)\)

= n(n+1) = (n+1)

= (n+1)(n+1)

So, k + 1 is a perfect square.

Thus, we proved that the sum of any two consecutive triangular numbers is a perfect square.

Here, we have to prove that if n is a triangular number, then so are 9n + 1,25n + 3, and 49n + 6.

It’s given that each of the numbers, 1 = 1,3 = 1 + 2,6 = 1 + 2 + 3,10 = 1 + 2 + 3 + 4,… represents the number of dots that can be arranged evenly in an equilateral triangle:

Proof : Let 1 + 2 + 3 + ⋯ + k = n, then

9n + 1 = \(\frac{9 k(k+1)}{2}+1=\frac{\left.9 k^2+9 k+2\right)}{2}=\frac{(3 k+1)(3 k+2)}{2}=\frac{s(s+1)}{2}^{\text {for } s=3 k+1}\) 9n + 1 is a triangular.

25n + 3 = \(\frac{25 k(k+1)}{2}+3=\frac{\left.25 k^2+25 k+6\right)}{2}=\frac{(5 k+2)(5 k+3)}{2}=\frac{s(s+1)}{2}\) for s = 5k+2, thus 25n + 3 is triangular

49n + 6 = \(\frac{49 k(k+1)}{2}+6=\frac{\left.49 k^2+49 k+12\right)}{2}=\frac{(7 k+3)(7 k+4)}{2}=\frac{s(s+1)}{2}\) for s = 7k + 2, thus 49n + 6 is triangular.

Thus, proved that if n is a triangular number, then so are 9n + 1, 25n + 3, and 49n + 6.

David Burton Elementary Number Theory Chapter 2 Exercise 2.1 solutions

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.1 Page 15 Problem 3 Answer

Here, we have to derive the following formula for the sum of triangular numbers, attributed to the Hindu mathematician Aryabhata,

t₁+ t₂ + t₃ + …. + \(\frac{n(n+1)(n+2)}{6}\) n ≥ 1. It’s given that, t_k-1 + t_k = k²

Proof: Recall from ex 1 (c) in sec 1.1,

1.2 + 2.3 + …. + n.(n+1) = \(\frac{n(n+1)(n+2)}{3}\), n ≥ 1

∴ \(\frac{1 \cdot 2}{2}+\frac{2 \cdot 3}{2}+\cdots+\frac{n \cdot(n+1)}{2}=\frac{n(n+1)(n+2)}{6}\)

Note that each term k can be written as \(\frac{k(k+1)}{2}=t_k\)

∴ t₁ + t₂ + t₃ + …. + \(\frac{n(n+1)(n+2)}{6}\)

Thus, we derive the following formula for the sum of triangular numbers

t₁ + t₂ + t₃ + …. + \(\frac{n(n+1)(n+2)}{6}\) n ≥ 1.

Page 16 Problem 4 Answer

Here, we have to prove that the square of any odd multiple of 3 is the difference of two triangular numbers specifically, that 9(2n+1)² = t_9n+4 − t_3n+1

Proof : We want to prove that the square of any odd multiple of 3 is the difference of two triangular numbers.

Since,

\(t_k=\frac{k(k+1)}{2}\), then

Therefore,

= \(\frac{72 n^2+72 n+18}{2}\) = 36n² + 36n + 9

= 9(4n² + 4n + 1) = 9(2n+1)²

Thus, we proved that the square of any odd multiple of 3 is the difference of two triangular numbers specifically, that 9(2n+1)^{2} = t_9n+4 − t_3n+1

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.1 Page 16 Problem 5 Answer

Here, we have to find two triangular numbers whose sum and difference are also triangular numbers.

From the list of the first ten triangular numbers, 1,3,6,10,15,21,28,36,45,55, if we look carefully, it is not hard to see that the number we searching for are A = 15 and B = 21.Really, A + B = 36 triangular number, B − A = 6 triangular number.

So, make a list of first ten triangular numbers i.e 0,1,3,6,10,15,21,28,36,45,55

Here, we have to find three successive triangular numbers whose product is a perfect square.

Product of three successive triangular numbers is given by,

\(\frac{n(n+1)}{2} \cdot \frac{(n+1)(n+2)}{2} \cdot \frac{(n+2)(n+3)}{2}\) = \(\frac{n(n+1)^2(n+2)^2(n+3)}{8}\)

for some positive integer n. We can conclude that 2 divide n+1 or n+2,then 4 must divide (n+1)² or (n+2)².So that, if we find n such that n(n+3) divided by 2 gives the perfect square, our problem was solved. It is not hard to conclude that we need to chose n = 3

Really, for n = 3

\(\frac{3 \cdot 4 \cdot 4 \cdot 5 \cdot 5 \cdot 6}{8}\) = 3² . 5² . 4 = 30² = 900

Thus, use that the product of the three successive triangular numbers is given by

\(\frac{n(n+1)}{2} \cdot \frac{(n+1)(n+2)}{2} \cdot \frac{(n+2)(n+3)}{2}\) = \(\frac{n(n+1)^2(n+2)^2(n+3)}{8}\) , for some positive integer n

Here, we have to find the three successive triangular numbers whose sum is a perfect square.

From the list of first ten triangular numbers 1,3,6,10,15,21,28,36,45,55, if we look carefully, it is not hard to see that the number we searching for are A = 15,B = 21 and C = 28 Really, A + B + C = 64 perfect square

Thus, make a list of first ten triangular numbers i.e 0,1,3,6,10,15,21,28,36,45,55

Solutions to Chapter 2 Exercise 2.1 Burton Number Theory

Page 16 Problem 6 Answer

Here, we have to prove that t_4n(n+1) is also a square if the triangular number t_n is a perfect square.

Proof: Assume

t_n = k² = \(\frac{n(n+1)}{2}\), then 2k2 = n(n+1)

t_4n(n+1)= \(\frac{4 n(n+1)(4 n(n+1)+1)}{2}\)

= \(4 \cdot 2 k^2\left[4 n^2+4 n+1\right]\)

= 4k²(2n+1)²

= [2k(2n+1)]²

Thus, we prove that t_4n(n+1) is also a square.

Here, we have to use part (a) to find three examples of squares that are also triangular numbers.

Using part (a) t₁ = 1 is a perfect square. t4⋅1(1+1) = t₈ = 36 is a perfect square.

\(t_{4 \cdot 8(8+1)}=t_{288}=\frac{288(288+1)}{2}\) = 41616 = 204² is a perfect square.

Thus, we used part (a) to find three examples of squares that are also triangular numbers.

Page 16 Problem 7 Answer

Here, we have to show that the difference between the squares of two consecutive triangular numbers is always a cube.

Proof : We want to prove the difference between the squares of two consecutive triangular numbers is always a cube.

Since, \(t_{n+1}=\frac{(n+1)(n+2)}{2}, t_n=\frac{n(n+1)}{2}\)

∴ \(t_{n+1}^2-t_n^2=\frac{(n+1)^2(n+2)^2-(n+1)^2 n^2}{4}\)

= \(\frac{(n+1)^2\left[n^2+4 n+4=n^2\right]}{4}\) for n ≥ 1

= \(\frac{(n+1)^2(4 n+4)}{4}=(n+1)^3\)

Thus, show that the difference between the squares of two consecutive triangular numbers is always a cube.

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.1 Page 16 Problem 8 Answer

Here, we have to prove that the sum of the reciprocals of the first n triangular numbers is less than 2 that is,\(\frac{1}{1}+\frac{1}{3}+\frac{1}{6}+\frac{1}{10}+\cdots+\frac{1}{t_n}<2\). It’s given that \(\frac{2}{n(n+1)}=2\left(\frac{1}{n}-\frac{1}{n+1}\right)\)

Proof:

Note that,

∴ \(\frac{1}{1}+\frac{1}{3}+\cdots+\frac{1}{t_n}\)

= \(2\left(\frac{1}{1}-\frac{1}{2}\right)+2\left(\frac{1}{2}-\frac{1}{3}\right)+\cdots+2\left(\frac{1}{n}-\frac{1}{n+1}\right)\)

=\(2\left(\frac{1}{1}-\frac{1}{n+1}\right)=2\left(1-\frac{1}{n+1}\right)\)

Since,

that is \(\frac{1}{1}+\frac{1}{3}+\cdots+\frac{1}{t_n}<2\)

Thus, we proved that sum of the reciprocals of the first n triangular numbers is less than 2 that is 1

Divisibility Theory Exercise 2.1 answers David Burton

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.1 Page 16 Problem 9 Answer

Here, we have to establish the identity t_{x} = t_{y} + t_{z}, where \(x=\frac{n(n+3)}{2}+1 \quad y=n+1 \quad z=\frac{n(n+3)}{2}\) and n ≥ 1, thereby proving that there are infinitely many triangular numbers that are the sum of two other such numbers.

Proof:

R.H.S

= \(t_y+t_z=\frac{(n+1)(n+2)}{2}+\frac{\frac{n(n+3)}{2}\left[\frac{n(n+3)}{2}+1\right]}{2}\)

= \(\frac{2\left[\frac{(n+1)(n+2)}{2}\right]+\frac{n(n+3)}{2}\left[\frac{n(n+3)}{2}+1\right]}{2}\)

= \(\frac{2\left[\frac{n^2+3 n+2}{2}\right]+\frac{n(n+3)}{2}\left[\frac{n(n+3)}{2}+1\right]}{2}\)

= \(\frac{2\left[\frac{n(n+3)}{2}+1\right]+\frac{n(n+3)}{2}\left[\frac{n(n+3)}{2}+1\right]}{2}\)

= \(\frac{\left[\frac{n(n+3)}{2}+1\right]\left[\frac{n(n+3)}{2}+1+1\right]}{2}\)

= t_x = L.H.S

Thus, we prove that t_{x} = t_{y} + t_{z} where \(x=\frac{n(n+3)}{2}+1 \quad y=n+1 \quad z=\frac{n(n+3)}{2}\)

Here, we have to find three examples of triangular numbers that are sums of two other triangular numbers.

Using part (a):

​n = 1 : t₃ = t₂ + t₂, or 6 = 3 + 3

n = 2 : t₆ = t₃ + t₅, or 21 = 6 + 15

n = 3 : t₁₀ = t₄ + t₉, or 55 = 10 + 45

Thus, we find three examples of triangular numbers that are sums of two other triangular numbers, they are

​n = 1 : t₃ = t₂ + t₂, or 6 = 3 + 3

n = 2 : t₆ = t₃ + t₅, or 21 = 6 + 15

n = 3 : t₁₀ = t₄ + t₉, or 55 = 10 + 45

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.1 Page 16 Problem 10 Answer

Here, we have to prove that p_n = \(\frac{n(3 n-1)}{2}\), n ≥ 1. It’s given that each of the numbers 1, 5 = 1 + 4, 12 = 1 + 4 + 7, 22 = 1 + 4 + 7 + 10,… represents the number of dots that can be arranged evenly in a pentagon:

Let p_n denotes nth pentagonal number where, p₁ = 1

p_n = p_n-1 + 3n – 2, n ≥ 2

We need to prove that n th pentagonal number is given by formula p_n = \(\frac{n(3 n-1)}{2}\) equation (1) for each positive integer n for which Eq (1) holds.

For n = 1 eq (1) is true, so that 1 belongs to the set S.

We assume that Eq (1) is true for a fixed integer k, so that for this k, p_k = \(\frac{k(3 k-1)}{2}\) and we attempt to prove that validity of the formula for k + 1. Using the definition of the pentagonal numbers we obtain that, p_k+1 = p_k + 3(k+1)-2

Next, from hypothesis that Eq (1) is correct for k we have that

p_k+1 = p_k + 3(k+1)-2

= \(\frac{k(3 k-1)}{2}+\frac{6(k+1)-4}{2}\)

= \(\frac{3 k^2-k+6 k+6-4}{2}\)

= \(\frac{3 k^2+5 k+2}{2}\)

= \(\frac{3 k^2+3 k+2 k+2}{2}\)

= \(\frac{3 k(k+1)+2(k+1)}{2}\)

= \(\frac{(k+1)(3(k+1)-1)}{2}\)

But this says that Eq (1) holds when n = k + 1,putting the integer k+1 in S so, that k+1 is in S whenever k is in S.According to the induction principle, S must be the set of all positive integers.

Thus, we use the definition of the pentagonal numbers and the induction principle to prove p_n = \(\frac{n(3 n-1)}{2}\), n ≥ 1

Burton Number Theory Divisibility Exercise 2.1 solutions

David Burton Elementary Number Theory Solutions Chapter 2 Divisibility Theory In The Integers Exercise 2.1 Page 16 Problem 11 Answer

Here, we have to verify the relations between the pentagonal, square, and triangular numbers: p_n = t_n-1 + n²

Let n be fixed arbitrary integer such that n ≥ 2, then

= \(\frac{n^2+n+2 n^2}{2}\)

= \(\frac{n(3 n+1)}{2}\)

= p_n

So, that this relation is correct.

Thus, we verified the relations between the pentagonal, square, and triangular numbers ; p_n = t_n-1 + n²

Here, we have to verify the relations between the pentagonal, square, and triangular numbers: pn = 3t_n-1 + n = 2t_n-1 + t_n

Let n be fixed arbitrary integer such that n ≥ 2,then,

= \(\frac{3 n^2-3 n+2 n}{2}\)

= \(\frac{3 n^2-n}{2}\)

= \(\frac{n(3 n+1)}{2}\)

= \(p_n\)

= \(\frac{n(3 n+1)}{2}\)

= \(\frac{3 n^2-n}{2}\)

= \(\frac{2 n^2-2 n+n^2+n}{2}\)

= \(2 \frac{n(n-1)}{2}+\frac{n(n+1)}{2}\)

= 2t_n-1 + t_n

So, the these relations are correct

Thus, we verified the relations between the pentagonal, square, and triangular numbers: p_n = 3t_n-1 + n = 2t_n-1 + t_n

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries

Page 7 Problem 2 Answer

Given: a + ar + ar² + …. + arⁿ = \(\frac{a\left(r^{n+1}-1\right)}{r-1}\)

If r ≠ 1, we have to show that for any positive integer n

We want to prove that:

a + ar + ar² + …. + arⁿ = \(\frac{a\left(r^{n+1}-1\right)}{r-1}\)(1)

Let S be the set of all positive integers for which Equation (1) is true.

When r = 2, a + ar + ar² = a(r² + r + 1)

R.H.S:

\(\frac{a\left(r^3-1\right)}{r-1}=\frac{a(r-1)\left(r^2+r+1\right)}{(r-1)}\) = a(r² + r + 1)

From (1) and (2), r = 2 satisfies

Equation (1) ⇒ 2 ∈ S Let K ∈ S then

a + ar + …. + ark = \(\frac{a\left(r^{k+1}-1\right)}{r-1}\) + ark+1

Now for

r = k + 1, a + ar + … + ark + ark+1 = \(\frac{a\left(r^{k+1}-1\right)}{r-1}\)

= \(\frac{a}{r-1}\left[r^{k+1}-1+(r-1) r^{k+1}\right]=\frac{a}{r-1}\left[r^{k+2}-1\right]\)

Which is the R.H.S of Eq.(1) when r=k+1

Thus k+1 ∈ S then S is the set of all positive integers r ≥ 2,thus Eq.(1) is true for all r ≥ 2

We get, a + ar + ar² + …. + arn = \(\frac{a\left(r^{n+1}-1\right)}{r-1}\)

David Burton Elementary Number Theory Chapter 1 Exercise 1.1 Solutions

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries Exercise 1.1 Page 7 Problem 3 Answer

Given: aⁿ−1 = (a−1)(a^n-1 + a^n-2 + a^n-3 + ⋯ + a + 1)

By using the Second Principle of Finite Induction we have to establish that for all n ≥ 1

aⁿ-1 = (a-1)(a^n-1 + a^n-2 + … + a + 1)

Proof: We prove it by induction. For n = 1, the relation trivially holds. Let this hold for all numbers less or equal to k i.e.

a^k−1 = (a−1)(a^k-1 + a^k-2 + ⋯ + a + 1)

Then
​
a^k+1 − 1 = a^k+1 − a^k + a^k − 1

= a^k(a−1) + (a−1)(a^k-1 + a^k-2 + ⋯ + a + 1)

= (a−1)(a^k + a^k-1 + a^k-2 + ⋯ + a + 1)
​
This shows that the relation holds for number k implies it holds for k+1. Hence by principle of finite induction, this holds for all n ≥ 1.

So, the relation holds for number k implies it holds for k + 1.

Hence by principle of finite induction, this holds for all n ≥ 1.

Page 7 Problem 4 Answer

Given:

n³ = (1³ + 2³ + ⋯ + n³) − (1³ + 2³ + ⋯ + (n−1)³).

We have to prove that the cube of any integer can be written as the difference of two squares

we use the relation that

1³ + 2³ + … + n³ = \(\left(\frac{n(n+1)}{2}\right)^2\)

We know that

n³ = (1³ + 2³ + ⋯ + n³) − (1³ + 2³ + ⋯ + (n−1)³)

Using the above relation, we get

n³ = \(\left(\frac{n(n+1)}{2}\right)^2-\left(\frac{(n-1) n}{2}\right)^2\)

Where the terms \(\left(\frac{n(n+1)}{2}\right) \text { and }\left(\frac{(n-1) n}{2}\right)\) are integers.

We get n³ = \(\left(\frac{n(n+1)}{2}\right)^2-\left(\frac{(n-1) n}{2}\right)^2\)

Where the terms \(\left(\frac{n(n+1)}{2}\right) \text { and }\left(\frac{(n-1) n}{2}\right)\) are integers.

Solutions To Chapter 1 Exercise 1.1 Burton Elementary Number Theory

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries Exercise 1.1 Page 7 Problem 5 Answer

We need to find the values of n ≤ 7 for which n!+1 is a perfect square.

We need to find the values of n ≤ 7 for which n!+1 is a perfect square.
​
n:1 ⇒ ​n! + l = 2

n:2 ⇒​ n! + 1 = 3

n:3 ⇒ ​n! + l = 7

n:4 ⇒ ​n! + 1 = 5²

n:5 ⇒​ n! + 1 = 11²

​n = 6 ⇒ ​n!+1 = 721

n = 7 ⇒​ n!+1 = 5041 = 71²

Thus for n = 4,5,7 n!+1 is a perfect square

For n = 4,5,7,n! + 1 is a perfect square.

Given -​ For positive integers m and n,(mn)! = m!n! and (m+n)! = m!+n!.
​
We will determine whether the given statement is true or false.

We will use the known facts.

False.

Because(3.2)! = 720

3!.2! = 6.2

= 12

So (3.2)! ≠ 3!.2!

(3+2)! = 5!

= 120

3! + 2! = 6 + 2

= 8

So (3+2)! ≠ 3! + 2!

The given statement is false.

Page 7 Problem 6 Answer

We have to prove that n! > n² for every integer n ≥ 4, where as n! > n³ for every integer n ≥ 6.

We prove it via finite induction. We know 4! = 24 ≥ 16 = 4² thus it works for case n = 4. Let this true for some integer k > 4. i.e. k! > k^{2}.

Then

(k+1)! = (k+1)k! > (k+1)k² > (k+1)²

[Note* here we use k² ≥ k+1]

This shows n! > n² for all n ≥ 4 by induction.

For n = 6, we have 6! = 720 > 216 = 6³. Let this be true for some integer k i.e. k! > k³, then

(k+1)! = (k+1)k! > (k+1)k³ > (k+1)(k+1)² = (k+1)³

[There we use k³ >(k+1)² for all k ≥ 3].

This shows n! > n³ for all n ≥ 6.

We get that n! > n³ for all n ≥ 6.

Page 7 Problem 8 Answer

Given: 2.6.10.14…(4n-2) = \(\frac{(2 n) !}{n !}\)

We have to verify that for all n ≥ 1

We have to prove that:

2.6.10.14…(4n-2) = \(\frac{(2 n) !}{n !}\)

Let S be the set of all positive integers for which Equation (1) is true.

For n = 1, 2 = \(\frac{(2) !}{1 !}\) = 2 thus 1 ∈ S

Assume K ∈ S then

2.6.10.14….(4k-2) = \(\frac{(2 k) !}{k !}\)

Now for

r = k + 1, 2.6.10.14…(4k-2).(4k+2) = \(\frac{(2 k) !}{k !}\)2(2k+1) = \(\frac{(2 k+1) !(2)}{k !} \cdot \frac{(k+1)}{(k+1)}\) = \(\frac{(2 k+2) !}{(k+1) !}=\frac{[2(k+1)] !}{(k+1) !}\) which is R.H.S of Eq(1)

When n = k + 1, thus k + 1 ∈ S

So, 2.6.10.14…(4n-2) = \(\frac{(2 n) !}{n !}\) is true for all n ≥ 1.

thus, 2.6.10.14…(4n-2) = \(\frac{(2 n) !}{n !}\) is true for all n ≥ 1.

By using (a)part we have to obtain that the inequality 2n(n!)2 ≤ (2n)! for all n ≥ 1.

Proof: 2ⁿ(n!) ≤ \(\frac{(2 n) !}{n !}\)

Using part (a): 2⋅6⋅10⋅14⋯(4n−2) ≥ 2ⁿ(n!)

Let S be the set of all positve integers for which Eq.(1) is true.

For n = 1,2 ≥ 2 thus 1 ∈ S

Assume k ∈ S then 2⋅6⋅10⋅14⋯(4k−2) ≥ 2^k(k!)

Now for r = k+1,2⋅6⋅10⋅14⋯(4k−2)⋅(4k+2) ≥ 2^k(k!)(4k+2)

= 2^k(k!)2(2k+1)=2^k+1(k+1)!

Therefore, k + 1 satisfies Eq.(1), thus k+1 ∈ S

Thus, 2⋅6⋅10⋅14⋯(4n−2) ≥ 2ⁿ(n!)

We get, 2.6.10.14…(4n-2) ≥ 2ⁿ(n!) is true for all n ≥ 1.

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries Exercise 1.1 Page 7 Problem 9 Answer

We have to Establish the Bernoulli inequality: If 1 + a > 0, then(1+a)ⁿ ≥ 1 + na for all n ≥ 1.

If 1 + a > 0, we need to prove that for each integer n ≥ 1 inequality

(1+a)ⁿ ≥ 1 + na…………(1) is correct.

Let S be the set of positive integers n for which Eq.1 holds. For n = 1 (1) is true, so that 1 belongs to the set S. We assume that inequality (1) is true for a fixed integer k, so that for this k

(1+a)^k ≥ 1 + ka

and we attempt to prove the validity of the formula for k+1. Next, from hypothesis that inequality(1) is correct for k we have that
​
​(1+a)^k+1 = (1+a)^k(1+a)
​​
hypothesis

≥ (1+ka)(1+a)

= 1 + ka + a + ka²

= 1 + (k+1)a

But this says that inequality (1) holds when n = k + 1, putting the integer k+1 in S so that k+1 is in S whenever k is in S. According to the induction principle, S must be the set of all positive integers.

So, the Bernoullis’s ldentity is established.

So, the Bernoullis’s ldentity is established.

Elementary Number Theory Burton Exercise 1.1 Answers

Page 7 Problem 10 Answer

Given: \(\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} \leq 2-\frac{1}{n}\)

To find: For all n ≥ 1,prove the following by mathematical induction

For n = 1, we have

so it holds.

Let the proposition hold for any number k, i.e. \(\frac{1}{1^2}+\frac{1}{2^2}+\cdots+\frac{1}{k^2} \leq 2-\frac{1}{k}\)

Then

\(\frac{1}{1^2}+\frac{1}{2^2}+\cdots+\frac{1}{k^2}+\frac{1}{(k+1)^2} \leq 2-\frac{1}{k}+\frac{1}{(k+1)^2}\) = \(2-\frac{1}{k+1}\left(\frac{k+1}{k}-\frac{1}{k+1}\right)\)

= \(2-\frac{1}{k+1}\left(\frac{(k+1)^2-k}{k(k+1)}\right)\)

= \(2-\frac{1}{k+1}\left(\frac{k(k+1)+1}{k(k+1)}\right)\)

< \(2-\frac{1}{k+1}\)

This shows that the relation holds for any n ≥ 1.

This shows that the relation holds for any n ≥ 1.

Given: \(\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^3}+\cdots+\frac{n}{2^n}=2-\frac{n+2}{2^n}\)

To find: For all n ≥ 1, prove the following by mathematical induction:

For n = 1, we have

So the relation holds for n = 1.

Let the relation hold for some integer k, i.e.

then

\(\frac{1}{2}+\frac{2}{2^2}+\frac{3}{2^2}+\cdots+\frac{k}{2^k}+\frac{k+1}{2^{k+1}}\) = \(2-\frac{k+2}{2^k}+\frac{k+1}{2^{k+1}}\)

= \(2-\left(\frac{2(k+2)-(k+1)}{2^{k+1}}\right)\)

= \(2-\frac{k+3}{2^{k+1}}\)

This shows the relation holds for all n ≥ 1.

This shows the relation holds for all n ≥ 1.

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries Exercise 1.1 Page 7 Problem 11 Answer

We have to show that the expression (2n)!/2ⁿn! is an integer for all. n ≥ 0

From problem no 8, we have

2.6.10.14….(4n-2) = \(\frac{(2 n) !}{n !}\)

factoring 2 from each term on left side, we get

2ⁿ . 1.3.5.7…(2n-1) = \(\frac{(2 n) !}{n !}\)

This gives \(\frac{(2 n) !}{n ! 2^n}\) = 1.3.5.7…(2n-1) which is an integer.

We get \(\frac{(2 n) !}{n ! 2^n}\) = 1.3.5.7…(2n-1) which is an integer.

Page 7 Problem 12 Answer

Given: Consider the function defined by

T(n) = \(\begin{cases}\frac{3 n+1}{2} & \text { for } n \text { odd } \\ \frac{n}{2} & \text { for } n \text { ever }\end{cases}\)

The 3n+1 conjecture is the claim that starting from any integer n > 1, the sequence of iterates T(n),T(T(n)),T(T(T(n))),…, eventually reaches the integer 1 and subsequently runs through the values 1 and 2 . This has been verified for all n ≤ 10¹⁶.

Confirm the conjecture in the cases n = 21 and n = 23.

If n = 1, then we get T(1) = \(\frac{1}{2}(3 \cdot 1+1)=2\) and if n = 2, we get T(2) = 2/2 = 1.

For n = 21, we get the following result.

\(\begin{array}{l|l}
\mathrm{k} & T^k(21) \\
0 & 21 \\
1 & 32 \\
2 & 16 \\
3 & 8 \\
4 & 4 \\
5 & 2
\end{array}\) For n = 23, we get following result.

We get,

For n = 21

for n = 23

Page 8 Problem 13 Answer

Given: Suppose that the numbers an are defined inductively by

a₁= 1, a₂ = 2, a₃ = 3a₁=1, a₂ = 2, a₃ = 3, and

a_n = a_n-1 + a_n-2 + a_n-3 for all n ≥ 4.

To find: Use the Second Principle of Finite Induction to show that a_n < 2ⁿ for every positive integer n.

Given that a₁ = 1, a₂ = 2, a₃ = 3 and

a_n = a_n-1 + a_n-2 + a_n-3

for all n ≥ 4. Then a_{n} < 2^{n}.

For base case, a_{n} = 1 + 2 + 3 = 6<2^{4} = 16.

Let us assume that for all numbers r < k, the inequality be true.

i.e.

aτ < 2r

for all r ≤ k. Then ak+1

​= a_k + a_k-1 + a_k-2

< 2^k + 2^k-1 + 2^k-2

= 2^k-2(1+2+4)

< 2^k+1

Or,

a_k+1 < 2^k+1

This shows that by strong induction, a_{n} < 2^{n} for all n ≥ 4.

This shows that by strong induction, a_{n} < 2^{n} for all n ≥ 4.

Chapter 1 Exercise 1.1 Burton Number Theory Key

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries Exercise 1.1 Page 8 Problem 14 Answer

Given: If the numbers an are defined by a₁ = 11, a₂ = 21, and a_n = 3a_n-1 – 2a_n-2 for n ≥ 3

To prove: an = 5.2ⁿ + 1 n ≥ 1

Let a₁ = 11 and a₂ = 21 and an be defined by

a_n = 3a_n-1 − 2a_n-2

Then a_n = 5⋅2ⁿ+1,n ≥ 1. This is true for n = 1,2,3 since
​
​a₁ = 5⋅2 + 1 = 11

a₂ = 5⋅4 + 1 = 21

a₃ = 41 = 3⋅21 − 2⋅11
​
Let this be true for all integers r ≤ k. i.e.

a_r = 5⋅2^r + 1,r ≤ k

Then
​
a_k+1 = 3a_k − 2a_k-1

= 3(5⋅2^k+1) − 2(5⋅2^k-1+1)

= 5⋅2^k-1(6−2) + 3 − 2

= 5⋅2^k+1+1
​
which shows the result hold for k+1 as well.

Therefore by strong induction, the result holds for all n ≥ 1.

Therefore by strong induction, the result holds for all n ≥ 1.

Page 10 Problem 1 Answer

We have to Derive Newton’s identity

\(\left(\begin{array}{l}
n \\
k
\end{array}\right)\left(\begin{array}{l}
k \\
r
\end{array}\right)\) = \(\frac{n !}{(n-k) ! k !} \cdot \frac{k !}{(k-r) ! r !}\)

= \(\frac{n !}{(n-r) ! r !} \cdot \frac{(n-r) !}{(n-k) !(k-r) !}\)

= \(\left(\begin{array}{l}
n \\
r
\end{array}\right)\left(\begin{array}{l}
n-r \\
k-r
\end{array}\right)\)

We get, \(\left(\begin{array}{l}
n \\
k
\end{array}\right)\left(\begin{array}{l}
k \\
r
\end{array}\right)\) = \(\left(\begin{array}{l}
n \\
r
\end{array}\right)\left(\begin{array}{l}
n-r \\
k-r
\end{array}\right)\)

By the Use of part (a) we have to express \(\left(\begin{array}{l}
n \\
k
\end{array}\right)\) in terms of it predecessor: \(\left(\begin{array}{l}
n \\
k
\end{array}\right)\) = \(\frac{n-k+1}{k}\left(\begin{array}{c}
n \\
k-1
\end{array}\right) \quad n \geq k \geq 1\)

Put r = k – 1, this gives

This gives

\(\left(\begin{array}{l}
n \\
k
\end{array}\right)\)k = \(\left(\begin{array}{c}
n \\
k-1
\end{array}\right)(n-k+1)\) ⇒ \(\frac{(n-k+1)}{k}\left(\begin{array}{c}
n \\
k-1
\end{array}\right)\)

We get, \(\left(\begin{array}{l}
n \\
k
\end{array}\right)\)k = \(\left(\begin{array}{c}
n \\
k-1
\end{array}\right)(n-k+1)\) ⇒ \(\frac{(n-k+1)}{k}\left(\begin{array}{c}
n \\
k-1
\end{array}\right)\)

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries Exercise 1.1 Page 11 Problem 2 Answer

If 2 ≤ k ≤ n-2, show that

\(\left(\begin{array}{l}
n \\
k
\end{array}\right)=\left(\begin{array}{l}
n-2 \\
k-2
\end{array}\right)+2\left(\begin{array}{c}
n-2 \\
k-1
\end{array}\right)+\left(\begin{array}{c}
n-2 \\
k
\end{array}\right)\) n ≥ 4

Proof: let 2 ≤ k ≤ n-2 and n ≥ 4. We want to prove:

Take the right hand side:

= \(\frac{(n-2) !}{(k-2) !(n-k) !}+\frac{2(n-2) !}{(k-1) !(n-k-1) !}+\frac{(n-2) !}{k !(n-k-2) !}\)

= \(\frac{k(k-1)(n-2) !}{k !(n-k) !}+\frac{2 k(n-k)(n-2) !}{k !(n-k) !}+\frac{(n-k)(n-k-1)(n-2) !}{k !(n-k) !}\)

= \(\frac{\left.(n-2) ! k^2-k+2 k n 2-2 k^2+n^2-n k-n-k_R+k^2+k\right]}{k !(n-k) !}\)

= \(\frac{(n-2) !\left[n^2-n\right]}{k !(n-k) !}=\frac{n(n-1)(n-2) !}{k !(n-k) !}\)

= \(\frac{n !}{k !(n-k) !}=\left(\begin{array}{c}
n \\
k
\end{array}\right)\)

Therefore R.H.S = L.H.S.

We get, \(\left(\begin{array}{l}
n \\
k
\end{array}\right)=\left(\begin{array}{l}
n-2 \\
k-2
\end{array}\right)+2\left(\begin{array}{c}
n-2 \\
k-1
\end{array}\right)+\left(\begin{array}{c}
n-2 \\
k
\end{array}\right)\) n ≥ 4

Page 11 Problem 4 Answer

We have to prove the following for n ≥ 1: \(\left(\begin{array}{l}
n \\
r
\end{array}\right)<\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if 0 ≤ r < \(\frac{1}{2}(n-1)\).

Proof: for n ≥ 1,

<=> \(\frac{n !}{r !(n-r) !}<\frac{n !}{(r+1) !(n-r-1) !}\), 0 ≤ r, 0 ≤ n – r – 1

<=> \(frac{(r+1) !}{r !}<\frac{(n-r) !}{(n-r-1) !}\), 0 ≤ r ≤ n-1

<=> r + 1 < n – r, 0 ≤ r ≤ n-1

<=> 0 ≤ 2r ≤ n-1

<=> 0 ≤ r ≤ \(\frac{1}{2}(n-1)\)

We get, \(\left(\begin{array}{l}
n \\
r
\end{array}\right)<\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if 0 ≤ r < \(\frac{1}{2}(n-1)\).

We have to prove the following for n ≥ 1: \(\left(\begin{array}{l}
n \\
r
\end{array}\right)>\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if n-1 ≥ r > \(\frac{1}{2}(n-1)\).

For n ≥ 1,

<=> \(\frac{n !}{r !(n-r) !}>\frac{n !}{(r+1) !(n-r-1) !}\), r ≥ 0, n – r – 1 ≥ 0

<=> \(frac{(r+1) !}{r !}<\frac{(n-r) !}{(n-r-1) !}\), r ≥ 0, n – r – 1 ≥ 0

<=> 2r > n – 1, n – 1 ≥ r ≥ 0

<=> n – 1 ≥ r ≥ \(\frac{1}{2}(n-1)\) ≥ 0

We get, \(\left(\begin{array}{l}
n \\
r
\end{array}\right)>\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if n-1 ≥ r > \(\frac{1}{2}(n-1)\).

We have to prove the following for n ≥ 1:

\(\left(\begin{array}{l}
n \\
r
\end{array}\right)=\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if n is odd integer, and r = \(\frac{1}{2}(n-1)\).

for n ≥ 1,

<=> r + 1 = n – r, n – 1 ≥ r ≥ 0

<=> 2r = n – 1, n – 1 ≥ r ≥ 0

<=> r = \(\frac{1}{2}(n-1)\), n – 1 ≥ r ≥ 0

We get, \(\left(\begin{array}{l}
n \\
r
\end{array}\right)=\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\) if and only if n is odd integer, and r = \(\frac{1}{2}(n-1)\).

How To Solve Chapter 1 Exercise 1.1 Burton Number Theory

Page 12 Problem 5 Answer

For n ≥ 2, we have to prove that

\(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\left(\begin{array}{l}
3 \\
2
\end{array}\right)+\left(\begin{array}{l}
4 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{l}
n \\
2
\end{array}\right)\) = \(\left(\begin{array}{c}
n+1 \\
3
\end{array}\right)\)

First, recall Pascal’s identity

Proof by mathematical induction: for

for n=2, \(\left(\begin{array}{l}
2 \\
2
\end{array}\right)=1=\left(\begin{array}{c}
2+1 \\
3
\end{array}\right)=1\)

Thus its true for n=2. Now assume it’s true for n=k then prove it for n = k + 1. Let

Then

= \(\left(\begin{array}{c}
k+1 \\
3
\end{array}\right)+\left(\begin{array}{c}
k+1 \\
2
\end{array}\right)\)

= \(\left(\begin{array}{c}
k+2 \\
3
\end{array}\right)\)

(from Pascal’s identity)

Thus its true for n = k + 1, therefore by mathematical induction

We get, \(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\left(\begin{array}{l}
3 \\
2
\end{array}\right)+\left(\begin{array}{l}
4 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{l}
n \\
2
\end{array}\right)\) = \(\left(\begin{array}{c}
n+1 \\
3
\end{array}\right)\)

From part (a), and the relation m² = 2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\) + m for m ≥ 2,

We have to deduce the formula 1² + 2² + 3² +….+n² = \(\frac{n(n+1)(2 n+1)}{6}\)

First we want to prove that m² = 2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\) + m for m ≥ 2

2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\) + m <=> \(\frac{2 m !}{2 !(m-2) !}+m\) <=> m(m-1) + m = m2

Now we want to prove that:

1² + 2²+ 3² +….+n² = \(\frac{n(n+1)(2 n+1)}{6}\)

Proof:

1² + 2² + …. + n²

= \(1+2\left(\begin{array}{l}
2 \\
2
\end{array}\right)+2+2\left(\begin{array}{l}
3 \\
2
\end{array}\right)+3+\cdots+2\left(\begin{array}{l}
n \\
2
\end{array}\right)+n\)

= \((1+2+\cdots+n)+2\left[\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\left(\begin{array}{l}
3 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{l}
n \\
2
\end{array}\right)\right]\)

= \((n(n+1)] \frac{3+2 n-2}{6}\)

= \(\frac{n(n+1)}{2}+\frac{2(n+1) !}{3 !(n-2) !}\)

= \(\frac{n(n+1)}{2}+\frac{(n+1)(n)(n-1)}{3}\)

= \([n(n+1)]\left(\frac{1}{2}+\frac{n-1}{3}\right)\)

= \([n(n+1)] \frac{3+2 n-2}{6}\)

= \(\frac{n(n+1)(2 n+1)}{6}\)

We get, 1² + 2² + 3² +….+n² = \(\frac{n(n+1)(2 n+1)}{6}\)

Here, we have to prove that 1.2 + 2.3 + …. + n(n+1) = \(\frac{n(n+1)(n+2)}{3}\)

Proof: from(b)

m² = 2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\) + m ⇒ m(m-1) = 2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\), m ≥ 2

∴ 1.2 + 2.3 + …. + n.(n+1)

= \(2\left(\begin{array}{l}
2 \\
2
\end{array}\right)+2\left(\begin{array}{l}
3 \\
2
\end{array}\right)+\cdots+2\left(\begin{array}{l}
n \\
2
\end{array}\right)\)

= \(2\left[\left(\begin{array}{c}
n+2 \\
3
\end{array}\right)\right] \text { from (a) }\)

= \(2\left[\frac{(n+2) !}{3 !(n-1) !}\right]=\frac{2(n+2)(n+1)(n)}{3 \cdot 2 \cdot 1}\)

= \(\frac{n(n+1)(n+2)}{3}\)

Thus, we proved that 1.2 + 2.3 + …. + n(n+1) = \(\frac{n(n+1)(n+2)}{3}\)

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries Exercise 1.1 Page 12 Problem 6 Answer

Here, we have to derive the binomial identity,

\(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\left(\begin{array}{l}
4 \\
2
\end{array}\right)+\left(\begin{array}{l}
6 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{c}
2 n \\
2
\end{array}\right)=\frac{n(n+1)(4 n-1)}{6} \quad n \geq 2\).

It’s given that m ≥ 2, \(\left(\begin{array}{c}
2 m \\
2
\end{array}\right)=2\left(\begin{array}{c}
m \\
2
\end{array}\right)+m^2\)

We can write as,

∴ \(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\left(\begin{array}{l}
4 \\
2
\end{array}\right)+\left(\begin{array}{l}
6 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{c}
2 n \\
2
\end{array}\right)\)

= \(1+\left[2^2+2\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\cdots+n^2+2\left(\begin{array}{l}
n \\
2
\end{array}\right)\right]\)

= \(\left(1^2+2^2+\cdots+n^2\right)+2\left[\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\cdots+\left(\begin{array}{l}
n \\
2
\end{array}\right)\right]\)

= \(\frac{n(n+1)(2 n+1)}{6}+2\left(\begin{array}{c}
n+1 \\
3
\end{array}\right)\)

= \(\frac{n(n+1)(2 n+1)}{6}+\frac{2(n+1) !}{3 \cdot 3(n-2) !}\)

= \(\frac{n(n+1)(2 n+1)}{6}+\frac{6(n+1)(n)(n-1)}{6}\)

= \(\frac{n(n+1)[2 n+1+2 n-2]}{6}\)

= \(\frac{n(n+1)(4 n-1)}{6}\)

Thus, we derive the binomial identity,

Page 12 Problem 7 Answer

Here, we have to verify that

1² + 3² + 5² + …. + (2n-1)² = \(\left(\begin{array}{c}
2 n+1 \\
3
\end{array}\right)\)

We solve this by mathematical induction on n.

For the case n = 1, 1² = \(\left(\begin{array}{c}
3 \\
3
\end{array}\right)\) = 1

Assume that the identity is true for some k > 1.

For some k > 1,

1² + 3² + 5² + … + (2k−1)² = \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\)

Add (2k+1)² to both sides

L.H.S 1² + 3² + 5² + … + (2k-1)² + (2k+1)²

R.H.S = \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\) + (2k+1)²

= \(\frac{(2 k+1)(2 k)(2 k-1)}{6}+(2 k+1)^2\)

= \((2 k+1)\left(\frac{(2 k)(2 k-1)}{6}+2 k+1\right)\)

= \((2 k+1)\left(\frac{4 k^2+10 k+6}{6}\right)\)

= \(\frac{(2 k+1)(2 k+2)(2 k+3)}{6}\)

= \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\)

Hence, the identity is true for k+1 too. This completes the induction. Hence, the identity is true for all integers greater than or equal to 1

1² + 3² + 5² + …. + (2k+1)² = \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\)

Thus, we verified that

1² + 3² + 5² + …. + (2n-1)² = \(\left(\begin{array}{c}
2 n+1 \\
3
\end{array}\right)\)

Burton Number Theory Exercise 1.1 Step-By-Step Solutions

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries Exercise 1.1 Page 12 Problem 8 Answer

Here, we have to show that for n ≥ 1,

Expand the L.H.S according to definition,

In the second step, cancel each (2n−2k) from the numerator by an(n−k) from the denominator. You get n 2′s in the numerator. Then multiply each term of the denominator by a 2 and multiply 2n to balance it out,

L.H.S = \(\left(\begin{array}{c}
2 n \\
n
\end{array}\right)=\frac{(2 n) !}{n ! n !}\)

= \frac{(2 n)(2 n-1) \cdots 2 \cdot 1}{n(n-1) \cdots 1 \cdot n(n-1) \cdots 1}

= \frac{(2 n-1)(2 n-3) \cdots \cdots 3 \cdot 1}{n(n-1) \cdots 1} 2^n

= \frac{(2 n-1)(2 n-3) \cdots \cdot 3 \cdot 1}{2 n(2 n-2) \cdots 2} 2^{2 n}

= \frac{1 \cdot 3 \cdot 5 \cdots(2 n-1)}{2 \cdot 4 \cdot 6 \cdots \cdots 2 n} 2^{2 n}

= R.H.S

Thus, we proved that for n ≥ 1,

Page 12 Problem 9 Answer

Here, we have to show that x > y > z, hence x² > xy > xz and establish the inequality \(2^n<\left(\begin{array}{c}
2 n \\
n
\end{array}\right)<2^{2 n}\), for n > 1. It’s given that x = 2.4.6…(2n), y = 1.3.5….(2n-1), and z = 1.2.3….n

Proof : We want to prove by induction that

n! < 1⋅3⋅5⋅⋅⋅⋅⋅(2n−1) for n > 1,for n = 2,2!<1⋅3, thus it’s true for n = 2. Now assume it’s true for n = k, let k! < 1⋅3⋅5⋅⋅⋅⋅(kn−1),then

(k+1)! = k!(k+1) < 1⋅3⋅5⋅⋅⋅⋅(kn−1)(k+1) < 1⋅3⋅5⋅⋅⋅⋅⋅(2k−1)(2k+1)

Note that: 2^kk! = 2.4.6….2n-1

So,

2^kk! < 1.3.5….(2k-1)2k

⇒ \(1<\frac{1 \cdot 3 \cdot 5 \cdots(2 k-1)}{2^k k !}\)

= \(\frac{1 \cdot 3 \cdot 5 \cdots(2 k-1)}{2 \cdot 4 \cdots 2 k !}\)

∴ \(2^k<\frac{1 \cdot 3 \cdot 5 \cdots(2 k-1)}{2 \cdot 4 \cdot 6 \cdots 2 k} 2^{2 k}=\left(\begin{array}{c}
2 k \\
k
\end{array}\right)\)

Now, since 2m−1 < 2m for m ≥ 1 for m ≥ 1,then 1⋅3⋅5⋯(2k−1)<2⋅4⋅6⋯2k

So, \(\frac{1 \cdot 3 \cdot 5 \cdots(2 k-1)}{2 \cdot 4 \cdot 6 \cdots 2 k}\), for k ≥ 1

Therefore, by ex (8),

Thus, we establish the equality \(2^n<\left(\begin{array}{c}
2 n \\
n
\end{array}\right)<2^{2 n}\), for n > 1

Page 12 Problem 10 Answer

Here, we have to prove that C_n can be given inductively by C_n = \(\frac{2(2 n-1)}{n+1} C_{n-1}\). It’s given that Catalan numbers, defined by

\(C_n=\frac{1}{n+1}\left(\begin{array}{c}
2 n \\
n
\end{array}\right)=\frac{(2 n) !}{n !(n+1) !} \quad n=0,1,2, \ldots\) from the sequence 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862,…

Multiply by 2n in the numerator and the denominator,

= \(\frac{2(2 n-1) !}{(n+1) !(n-1) !}\)

= \(\frac{2(2 n)(2 n-1) !}{2(n+1) ! n(n-1) !}\)

= \(\frac{(2 n) !}{(n+1) ! n !}\)

= C_n

Thus, we proved that C_n can be inductively by C_n = \(\frac{2(2 n-1)}{n+1} C_{n-1}\)