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

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

Page 49 Problem 1 Answer

Given ; p ≤ √701

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

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

we have p ≤ √701

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

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

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

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

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

 

Page 49 Problem 3 Answer

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

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

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

assume n = p1p2⋯pk,k ≥ 3

The first three primes factors are p1,p2,p3 then

p1 ∣ n,p2 ∣ n,p3 ∣ n

⟹ p1p2p3 ∣ n ⟹ p ≥ p1p2p3

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

p1 > \(\sqrt[3]{n}\),p2 > \(\sqrt[3]{n}\),p3 > \(\sqrt[3]{n}\)

Thus p1p2p3 > n contradiction, thus n > 1 is either a prime or the product of two prime

Hence we conclude that if p1p2p3 > n contradiction, thus n > 1 is either a prime or the product of two primes.

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

Page 49 Problem 4 Answer

Given ; √p is irrational for any prime p

To find ; Establish the following facts:

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

Let p is fixed prime number.

Assume that √p is rational,

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

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

From the last equality, we have that l2 and m2.

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

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

Hence, the proof!

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

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

To find; Establish the following facts:

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

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

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

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

also lna = kn.

Therefore, ln divides kn!

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

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

Hence we conclude that lna = kn. Therefore, ln divides kn! So that, must be l = 1 because gcd(k,l) = 1.

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

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

To find : we have to Establish the following facts:

Here we will use the fact 2n > n

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

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

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

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

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

Therefore, ln divides kn!

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

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

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

Then using result from part b it must be integer

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

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

So that, must be n ≥ 2n.

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

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

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

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

 

Page 49 Problem 6 Answer

Given : Proof of the infinitude of primes.

To find : missing details in given proof.

We will find it.

Here,

Assume only finite numbers p1,…,pn

Let A be the product of any r these primes.

So,

A = pa1⋅…⋅par,ai ∈ {1,2,…,n}

Consider

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

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

= pb1……..pbs

Where ai ≠ bj

So that,

{ai∣i=1,…,r}∩{bj∣j=1,…,s}=∅

and

{ai∣i=1,…,r}∪{bj∣j=1,…,s}={pi∣i=1,…,n}

Hence, A and B have no common factors.

Then each pk of p1,p2,…,pn divides either A or B, but not both. Since, A > 1,B > 1, then A + B > 1

Therefore, A + B has a prime divisor different from any of the pi, which is a contradiction.

Therefore, We completed the given proof..

 

Page 49 Problem 7 Answer

Given : Euclid’s proof

To do : Modify the given proof.

Here,

The modify proof is :

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

Now,

q = pi for some i.

Then q∣pi ⟹ q∣1 ⟹ q ≤ 1 which is contradiction.

Hence, there are infinitely many primes.

Therefore,

Modified proof is stated above.

 

Page 49 Problem 8 Answer

Given : Proof of the infinitude of primes.

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

Here,

The another proof of the infinitude of primes:

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

But p1,p2,⋯,pn are all prime numbers, thus q = pi for some i

If q = pi then q ∣ N and q ∣ pi

Then pi = q ∣ p2p3⋯pi-1pi+1⋯pn thus

pi ∣ pk,​2 ≤ k ≤ n is a contradiction.

Hence,

The set of prime numbers is infinite.

Therefore,

Another proof of the infinitude of primes is given above.

 

Page 50 Problem 9 Answer

Given : n>2

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

We will prove it.

Here,

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

Now,

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

From the facts

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

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

Now,

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

Hence,

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

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

Therefore,

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

Given : n > 1,

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

We will show it.

Here,

Let n be an integer such that n > 1

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

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

Therefore,

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

 

Page 50 Problem 10 Answer

Let qn be the smallest prime that is strictly greater than Pn = p1p2⋯pn+1

It has been conjectured that the difference qn−(p1p2⋯pn) always a prime.

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

Here,

We have , qn be the smallest prime that is strictly greater than Pn = p1p2⋯pn + 1

It has been conjectured that the difference qn − p1p2⋯pn is always a prime.

Now,

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

p1 = 2

p2 = 3

p3 = 5

p7,p5 = 11

So,

P1 = 2 + 1 ⇒ 3 ⟹ q1 ⇒ 5,

⇒ q1 − p1 = 5 − 2 ⇒ 3 is prime.

P2 = 2⋅3 + 1 ⇒ 7 ⟹ q2 ⇒ 11,

⇒ q2 − p1p2 = 11 − 6 ⇒ 5 is prime.

P3 = 2⋅3⋅5 + 1 ⇒ 31 ⟹ q3 ⇒ 37,

⇒ q3 − p1p2p3 = 37 − 30 ⇒ 7 is prime.

P4 = 2⋅3⋅5⋅7 + 1 ⇒ 211 ⟹ q4 ⇒ 223,

⇒ q4 − p1p2p3p4 = 223 − 210 ⇒ 13 is prime.

P5 = 2⋅3⋅5⋅7⋅11 + 1 ⇒ 2311 ⟹ q5 ⇒ 2333,

q5 − p1p2p3p4p5 = 2333 − 2310 ⇒ 23 is prime.

Therefore,

The difference qn – (p1p2….pn) always a prime.

 

Page 50 Problem 12 Answer

Given : pn is the nth prime number,

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

Here,

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

Now,

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

Now,

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

Hence,

We get that

pk+1 ≥ pk + 2 > 2k−1 + 2 = 2(k+1)−1

Therefore,

pn > 2n−1 for n ≥ 5

Given : pn is the nth prime number,

We have to show that none of the integers

Pn = p1p2⋯pn + 1 is a perfect square.

We will show it by a contradiction.

Here,

Integer p2…pn is odd, so that exist an positive integer k such that p2…pn = 2k + 1,

Then we get that Pn is given of the form ​

Pn = 2(2k+1) + 1

= 4k + 3

Now,

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

such that Pn = m2.

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

= (2l+1)2

= 4l2 + 4l + 1

i.e. 4k + 2 = 4l2 + 4l

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

Therefore,

None of the integers Pn = p1p2⋯pn+1 is a perfect square.

Given : pn is the nth prime number

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

We will show it by a contradiction.

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

Now,

Consider that A is an integer,

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

Also

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

Hence, pn ∣ p1p2…pn-1, then we have contradiction.

Therefore,

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

 

Page 50 Problem 13 Answer

Given : n∣m

We have to show that Rn∣Rm

We will use above information.

Here,

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

So, repunit Rm is given of the form :​

Rm = Rkn

= 11…1

= 10(k-1)nRn + 10(k-2)nRn+…+10nRn + Rn

Hence,

It is not hard to see that Rn ∣ Rm

Therefore,

If n ∣ m, then Rn ∣ Rm

Given : d ∣ Rn and d ∣ Rm

We have to show that d ∣ Rn+m

We will use above information.

Here,

We have, d ∣ Rn and d ∣ Rm, we need to show that d ∣ Rn+m.

Now,

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

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

= 10mRn + Rm

Hence,

It is not hard to see that d ∣ Rm+n.

Therefore,

If d ∣ Rn and d ∣ Rm, then d ∣ Rn+m

Given : gcd(n,m) = 1

We have to show that gcd(Rn,Rm) = 1

We will use above information.

Here,

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

Now,

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

Repunit Rm−n is given of the form :

Rm-n = Rm−10m-nRn

Hence,

It is not hard to conclude that gcd(Rm,Rn) = gcd(Rm-n,Rn).

If we repeat this procedure k times, we get that ​

gcd(Rm,Rn) = gcd(Rm-n,Rn)

= …

= gcd(Rm-kn,Rm)

= gcd(Rr,Rm)

Now, using Theorem 2.1. we get that n = k1r + r1 for some integers 0 < k−1 and 0 ≤ r1 < r.

Then using preceding procedure we get that ​gcd(Rm,Rn) = gcd(Rr,Rm)

= gcd(Rr,Rr1)

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

gcd(Rm,Rn) = Rgcd(m,n)

= R1

= 1

Now,

If gcd(Rm,Rn) = 1,

then gcd(m,n) = 1.

If d = gcd(m,n),

then using result from part b) we have that Rd ∣ Rm and Rd ∣ Rn.

So, ​Rd ∣ gcd(Rm,Rn) = 1

⇒ d = 1

Therefore,

If gcd(n,m) = 1,

then gcd(Rn,Rm) = 1

 

Page 50 Problem 14 Answer

We have to obtain the prime factors of the repunit R10

We will use result : If n ∣ m, then Rn ∣ Rm

Here,

We have,  R2, R5 ∣ R10.

So, we repunit R10 is given of the form

R10 = R2⋅R5⋅k for some positive integer k.

Now,

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

= 9091

Integers 9091 and R2 = 11 are prime numbers,

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

Prime factors of this number are 271 and 41.

Hence,

R10 = 11⋅41⋅271⋅9091

Therefore,

R10 = 11⋅41⋅271⋅9091

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

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

Page 43 Problem 1 Answer

Given ;There are infinitely many primes of the form n{2}−2

To find : Exhibit five such primes.

There are infinitely many primes of the form n2 − 2,

2 = 22 − 2

7 = 32 − 2

23 = 52 − 2

47 = 72 − 2

79 = 92 − 2

Hence the list of the prime number are of the given form n{2}−2. 2,7,23,47,79.

 

Page 43 Problem 2 Answer

Given ; Every positive integer can be written in the form p + a2, where p is either a prime or 1, and a ≥ 0.

To find : Give an example to show that the following conjecture is not true:

Here We will give an example to show that the following conjecture is not true:

Every positive integer can be written in the form p+a2, where p is either a prime or 1.

Take x = 25, hence 25

​= 0 + 25

= 21 + 4

= 9 + 16

= 16 + 9

But none of 0,4,9 and 16 is prime or 1

Hence we have shown that Every positive integer can be written in the form p + a{2} conjecture is not true: when x = 25

 

Page 43 Problem 3 Answer

Given ; Any prime of the form 3n+1 is also of the form 6m+1

To find : Prove each of the assertions below:

here we know that If a = 3n + 1 ⟹ 3 ∤ a,a ≠ 2,

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

so a is an odd prime not divisible by 3 .

By Division Algorithm, a = 6m + r,0 ≤ r < 6.

-​r ≠ 0,since if r = 0

⟹ a = 6m⟹3∣a

−r≠2, since if​ r = 2 ⟹ a

= 6m + 2 = 2(3m+1)

⟹ 2 ∣ a

– r≠3, since if ​r = 3 ⟹ a.

= 6m + 3

= 3(2m+1)

⟹ 3 ∣ a

– r ≠ 4, since if ​r = 4 ⟹ a

= 6m + 4

= 2(3m+2)

⟹ 2 ∣ a

– r ≠ 5, since if ​r = 5.

a = 6m + 5

= 3(2m+1) + 2

⟹ 2 ∣ a

So, r must be 1 .

Hence we have proved that if r = 1 Any prime of the 3n+1 form is also of the form 6m+1

Given ; Each integer of the form 3n+2 has a prime factor of this form.

To find : Prove each of the assertions below:

let a be the integer of the form 3n + 2,a = 3n + 2.

Let p be the prime factor of a, then p = 3r + 1 or 3r+2.

Assume that every prime factor of a has the form 3r+1,

then a also has the form 3r+1, since the product of two or more numbers of the form 3r+1 is also of the form 3r+1,

i.e (3m+1)(3n+1) = 9nm + 3m + 3n + 1 = 3(3nm+m+n) + 1

So, a must have at least one prime factor of the form 3n+2, if not, a can not be of the form 3n+2.

Hence we conclude that if, a must have at least one prime factor of the form 3n+2, if not, a can not be of the form 3n+2.

Given ; The only prime of the form n3−1 is 7

To prove the given of the assertions

We have n = 2

Therefore,​ 7 = 23 − 1

= 8 − 1

= 7

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

Now for n > 2,n3 − 1 = (n−1)(n2+n+1)

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

Thus, n3−1 can not be a prime.

We conclude that n3−1 can not be a prime.

Given ; The only prime P for which 3p+1 is a perfect square is p = 5.

To find ; Prove each of the assertions below:

3.5 + 1 = 16 is a perfect square.

Now assume for prime p, 3p + 1 = a2, a ∈ z.

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

9k2 – 3p = 3(3k2-p)

So, 3|1 a contradiction.

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

Now 3p + 1 = a2

3p = a2 – 1

⇒ p = (a-1)(a+1)

If a = 3k+1

p = \(\frac{(a-1)(a+1)}{3}\)

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

p = k(3k+2) a contradiction, since p is prime.

If a = 3k+2

p = \(\frac{(a-1)(a+1)}{3}\)

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

p = (k+1)(3k+1). a contradiction, since p is prime. Thus 3p+1 cannot be a perfect square.

Hence we conclude that p=(k+1)(3k+1). a contradiction, since p is prime. Thus 3p+1 can not be a perfect square

Given ; The only prime of the form n2−4 is 5

To find ; Prove each of the assertions below:

5 = 32 – 5 = 5

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

For n > 5, n2-4 > 0.

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

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

So n2 – 4 can not be prime.

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

 

Page 43 Problem 4 Answer

Given : If p ≥ 5 is a prime number,

To find ; show that p{2}+2 is composite.

But p on the form p = 3k + 1 or p = 3k + 2.

– If ​p = 3k + 1.

⟹ p−1 = 3k

⟹ 3∣(p−1)

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

So, 3∣(p2+2) ⟹ p2+2 is composite.

– If ​p = 3k + 2

⟹ p + 1

= 3(k+1)

⟹ 3∣(p+1)

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

So, 3∣(p2+2) ⟹ p2+2 is composite.

Hence we have proved that 3∣(p2+2) ⟹ p2+2 is composite.

 

Page 43 Problem 8 Answer

Given ; If p ≥ q ≥ 5 and p and q are both primes

To find ; prove that 24 ∣ p2−q2

Here we know p, q are odd primes. then they take one of these forms 3k+1 or 3k+2.

– If p = 3k+1 and q = 3m+1.

So ​p − q = 3(k−m).

⟹ 3∣(p−q)

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

– If p = 3k+2 and q = 3m+2.

So ​p−q = 3(k−m).

⟹ 3∣(p−q)

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

– If p = 3k+1 and q = 3m+2.

So​ p+q = 3(k+m)+3.

⟹ 3∣(p+q)

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

Thus in all cases 3∣(p−q)(p+q) ⟹ 3∣p2−q2

Now since p, q are primes, they take one of these forms 4r+1 or 4s+3.

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

So p2−q2,

= 16r2 + 8r + 1 − 16r2 − 8s − 1 = 8(2r2+r−2s2−s)

so  8∣p2−q2

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

So p2 − q2 = 16r2 + 24r + 9 − 16r2 − 24s − 9 = 8(2r2+3r−2s2−3s),

so 8∣p2−q2

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

So ​p2 − q2 = 16r2 + 8r + 1 − 16r2 − 24s − 9

8(2r2+r−2s2−3s−1)

so 8∣p2−q2

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

From and since gcd(8,3) = 1 ⟹ 24∣p2−q2

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

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

⟹ 24∣p2−q2

 

Page 43 Problem 9 Answer

Given ; An unanswered question is whether there are infinitely many primes that are 1 more than a power of 2 , such as 5 = 2{2}+1

To find ; Find two more of these primes.

We have 5 = 2{2}+1

​17 = 24 + 1

and 257 = 28 + 1.

Hence we have found 2 more prime that are 17,257.

Given : A more general conjecture is that there exist infinitely many primes of the form n2 + 1; for example, 257 = 162 + 1

To find : Exhibit five more primes of this type.

Here put the value of n = 1, 2, 4, 6, 8 to find the prime number in the given form

we have ​n2+1;

257 = 162 + 1

​12 + 1 = 2

22 + 1 = 5

42 + 1 = 17

62 + 1 = 37

102 + 1 = 101

Hence we have found 5 more prime in the form of n{2}+1 that s are 2,5,17,37,101

 

Page 43 Problem 10 Answer

Given ; . If p ≠ 5 is an odd prime

To find : prove that either p2−1 or p2+1 is divisible by 10.

here we will put the value of r and try to find that the given integers are divisible by 10

we know that p is odd prime, then by Division Algorithm ​p = 10q + r,

r = 1,3,7,9

– If ​r = 1,.

p = 10q + 1

⟹ p2−1 = 100q2 + 20q

= 10(10q2+2q)

⟹ 10∣(p2−1)

– If ​r = 3,

p = 10q + 3

⟹ p2+1

= 100q2 + 60q + 10

​10(10q2+6q+1)

⟹ 10∣(p+−1)

– If ​r = 7,

p = 10q + 7

⟹ p2+1

= 100q2 + 140q + 50

​10(10q2+14q+5)

⟹ 10∣(p2+1).

– If ​r = 9,

p = 10q + 9

p2−1 = 100q2 + 180q + 80

= 10(10q2+18q+8)

⟹ 10∣(p2−1)

In all cases either 10∣(p2−1) or 10∣(p2+1)

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

 

Page 43 Problem 12 Answer

Given; 1234, 10140 and 36000

To find the prime factorization of the given integers

The given integers are 1234, 10140, and 36000.

1234 = 2.617

10140 = 22.5.3.132

36000 = 25.53.32

The prime factorization of the given integer is:

1234 = 2⋅617

10140 = 22⋅5⋅3⋅132

36000 = 25⋅53⋅32

 

Page 43 Problem 13 Answer

Given : If n > 1 is an integer not of the form 6k+3

To find ; prove that n{2}+2{n} is composite.

here we will try to find in all the cases that the number is composite or not

By division we have ​n = 2k

n = 2k+1

– If n is even, n = 2k so, ​(2k)2 + 22k = 4k2 + 4k

⟹ 2∣n2 + 2n

Thus n2 + 2n is composite.

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

– If n = 6k + 1

n ≡ 1​(3)

n2 ≡ 1​(3)

and 2 ≡ −1​(3)

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

So, n2 + 2n ≡ 0​(3)

Thus n2 + 2n is composite.

– If n = 6k + 5

n ≡ 2​(3)

n2 ≡ 4 ≡ 1​(3)

and 2 ≡ −1​(3)

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

So, n2 + 2n ≡ 0​(3)

Thus n2+2n is composite.

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

Hence we conclude that n2+2n is composite.

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

 

Page 44 Problem 14 Answer

Given ; 6 = 29 − 23 = 137 − 131 = 599 − 593 = 1019 − 1013 = ⋯

To find : Express the integer 10 as the difference of two consecutive primes in 15 ways.

Here we will subtract 10 from all the given stes to find two consecutive numbers

We have 6 = 29 − 23 = 137 − 131 = 599 − 593 = 1019 − 1013 = ⋯

​10 = 23 − 13 = 149 − 139 = 191 − 181

= 41 − 31 = 251 − 241 = 293 − 283

= 47 − 37 = 347 − 337 = 419 − 409

= 71 − 61 = 431 − 421 = 557 − 547

= 83 − 73 = 701 − 691 = 113 − 103

Hence we have Express the integer 10 as the difference of two consecutive primes in 15 ways. is given by

10 = 23 − 13 = 149 − 139 = 191 − 181

= 41 − 31 = 251 − 241 = 293 − 283

= 47 − 37 = 347 − 337 = 419 − 409

= 71 − 61 = 431 − 421 = 557 − 547

= 83 − 73 = 701 − 691 = 113 − 103

 

Page 44 Problem 15 Answer

Given ; A square if and only if in the canonical form of a all the exponents of the primes are even integers

To find ; Prove that a positive integer a > 1 is square

pi is prime. So, a = k2 = (p1r1p2r2….psrs)2

= (p12r1p22r2….ps2rs)

So, all the exponents are even.

i.e a = (p12m1 p22m2….. ps2ms)

a = (p1m1 p2m2…..psms)2

So, a is a square

Hence we conclude that a = (p1m1p2m2⋯psms)2 So, a is a square.

 

Page 44 Problem 16 Answer

Given ; An integer is said to be square-free if it is not divisible by the square of any integer greater than 1

To prove:

An integer n > 1 is square-free if and only if n can be factored into a product of distinct primes.

Assume n is square-free then for any a ∈ Z,a2∤n

Assume ​pr ∈ Z ∋ n = prp1p2⋯pn

r > 1 ⟹ r = 2 + s,s ≥ 0

Then \(\frac{n}{p^2}=\frac{p^{2+s} p_1 p_2 \cdots p_n}{p^2}\)

\(\frac{p^2 p^s p_1 p_2 \cdots p_n}{p^2}\)

which is a contradiction.

Thus r must equal 1.

Assume n is a product of distinct primes

n = p1p2⋯pn

Assume ∃ a ∈ Z ∋ a2 ∣ n since a2 is square then a2 = q12r1q22r2⋯qs2rs contradiction

Hence we conclude that if n is a product of distinct primes n = p1p2⋯pn assume ∃ a ∈ Z ∋ a2 ∣ n since a2 is square then a2 = q12r1q22r2⋯qs2rs contradiction

Given ; An integer is said to be square-free if it is not divisible by the square of any integer greater than 1

To find ; Every integer n > 1 is the product of a square-free integer and a perfect square.

Here we have ​n = q12r1q22r2⋯qs2rs

,ri = 2pi + ri,

r = 0,1

​n = q12p1+r1q22p2+r2⋯qs2ps+rs

= (q1r1q2r2⋯qsrs)(q1p1q2p2⋯qsps)2

​Thus every integer is a product of a square free and a perfect square.

Hence we conclude that every integer is a product of a square free and a perfect square

 

Page 44 Problem 17 Answer

Given ; k ≥ 0 and m is an odd integer.

To find ; Verify that any integer n can be expressed as n = 2{k}m

here we will find whether m is odd or even if its odd then n = \(\prod_{i=1}^r p_i^{\alpha_i}=2^0 \prod_{i=1}^r p_i^{\alpha_i}=2^0 m\)

We know that by Fundamental theorem of Arithmetics

n = p1α​1p2α​s⋯psα​s, either n is even or n is odd.

– If n is even then 2∣n or ∃ pj = 2 ∋ 1 ≤ i ≤ r

⇒ n = 2αj \(\prod_{i=1, i \neq j}^r p_i^{\alpha_i}\)

Thus, n = 2αjm (where m = \(\prod_{i=1, i \neq j}^r p_i^{\alpha_i}\) is odd.)

-If n is odd, then n = \(\prod_{i=1}^r p_i^{\alpha_i}\)

= [/latex]2^0 \prod_{i=1}^r p_i^{\alpha_i}[/latex]

= 20m

(where m = \(\prod_{i=1}^r p_i^{\alpha_i}\) is odd)

Hence we conclude that If n is odd, then

n = \(\prod_{i=1}^r p_i^{\alpha_i}=2^0 \prod_{i=1}^r p_i^{\alpha_i}=2^0 m\)

(where m = \(\prod_{i=1}^r p_i^{\alpha_i}\) is odd)

 

Page 44 Problem 18 Answer

Given ; Numerical evidence makes it plausible that there are infinitely many primes p such that is also prime. p + 50

To find ; List 15 of these primes.

we will start with 3 as a prime number and add 50 to get desired solution

we have prime p such that p + 50 is also a prime

​(3,53)       (47,97)       (107,157)    (11,61)       (47,97)

(17,67)     (17,67)       (23,73)       (29,79)       (53,103)

(59,109)   (83,133)    (101,151)   (107,157)   (113,163)

Hence all the 15 prime number in the form p such that p + 50

(3,53)       (47,97)       (107,157)    (11,61)       (47,97)

(17,67)     (17,67)       (23,73)       (29,79)       (53,103)

(59,109)   (83,133)    (101,151)   (107,157)   (113,163)

 

Page 44 Problem 19 Answer

Given ; A positive integer n is called square-full, or powerful, if p2 ∣ n or every prime factor p of n , if n is square full

To find ; show that it can be written in the form n = a2b3, with a and b positive integers.

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

let n = p1k1⋯ prkr since n is square full, ki ≥ 2.

\(p_1^{k_1} \cdots p_r^{k_r}=q_{m_1}^{k_{m 1}} \cdots q_{m_s}^{k_{m s}} q_{n_1}^{k_{n 1}} \cdots q_{n_t}^{k_{t t}}\)

Where kmi are odd (so kmi ≥ 3). and kni are even,

so kni = 2vi

​n = \(q_{m_1}^{k_{m 1}} \cdots q_{m_s}^{k_{m s}}\left(q_{n_1}^{v_1} \cdots q_{n_t}^{v_t}\right)\)
​​

​= \(q_{m_1}^{k_{m 1}} \cdots q_{m_s}^{k_{m s}}\left(q_{n_1}^{v_1} \cdots q_{n_t}^{v_t}\right)^2\)

= \(q_{m_1}^{k_{m 1}} \cdots q_{m_s}^{k_{m s}}(g)^2, where g = (\left(q_{n_1}^{v_1} \cdots q_{n_t}^{v_t}\right))\)

since kmi is odd and ≥ 3, so kmi−3 is even.

n = \(q_{m_1}^3 \cdots q_{m_s}^3\left(q_{m_1}^{m-3} \cdots q_{m_s}^{m-3}\right)\left(g^2\right)\)

Let ​mi−3 = 2wi,

qm1⋯qms = b

∴ n = \(b^3\left(q_{m_1}^{2 w_1} \cdots q_m^{2 w_s}\right)\left(g^2\right)\)

Let f = \(q_{m_1}^{w_1} \cdots q_{m_s}^{w_s}\)

then n = b3f2g2

Let a = fg, then, n = a2b3

Hence we conclude that if kmi is odd and ≥ 3,so kmi − 3 is even.

n = \(q_{m_1}^3 \cdots q_{m_s}^3\left(q_{m_1}^{m-3} \cdots q_{m_s}^{m-3}\right)\left(g^2\right)\)

​mi − 3 = 2wi,

qm1⋯qms = b

∴ n = \(b^3\left(q_{m_1}^{2 w_1} \cdots q_m^{2 w_s}\right)\left(g^2\right)\)

f = \(q_{m_1}^{w_1} \cdots q_{m_s}^{w_s}\)

then n = b3f2g2

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

Hence proved

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

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

 

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 a2∣ bc

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

∴ (ax)(ay) = bc = a2xy ⟹ a2 ∣ bc

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

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

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 = a2xy ⟹ 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

 

Page 24 Problem 4 Answer

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

For n = 1:52n + 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 ∣ 52k + 7 ∴ ∃ x ∋ 8x = 52k + 7

Now, for n = k + 1

​52(k+1) + 7 = 52⋅52k + 7

= 52(52k+7) − 52⋅7 + 7

= 52(8x) − 52 − 7(52−1)

= 52(8x) − 7(24)

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

= 8(25x−21)

∴ 8 ∣ 5k+1

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

Thus, we have to use mathematical induction to establish the divisibility statements 8 ∣ 52n + 7

Here, we have to use mathematical induction to establish the divisibility statements, 15 ∣ 24n − 1

For, n = 1 : 24 − 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 ∣ (24k−1) ∴ ∃ x ∋ 15x = 24k − 1

Now, for n = k + 1

24(k+1) − 1 = 24⋅24k − 1 + 24 − 24

= 24(24k−1) + (24−1)

= 24(15x) + 15

= 15(x24+1)

∴ 15 ∣ 24(k+1) − 1

Thus, by mathematical induction for n ≥ 1,15 ∣ 24n − 1

Thus, we use mathematical induction to establish the divisibility statements, 15 ∣ 24n − 1

Here, we have to use mathematical induction to establish the divisibility statements, 5 ∣ 33n+1 + 2n+1

For n = 1 : 33+1 + 22 = 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 ∣(33k+1 + 2k+1) ∴ ∃ x ∋ 5x = 33k+1 + 2k+1

Now for n = k + 1

33(k+1)+1 − 2k+2 = 33k+4 − 2k+2

= 33⋅33k+1 + 2⋅2k+1 + 3⋅2k+1 − 33⋅2k+1

= 33(33k+1 + 2k+1) − 2k+1(33−2)

= 33(5x) − 2k+1(25)

= 5(x33 − 5⋅2k+1)

∴ 5 ∣ (33n+1 + 2n+1)

Thus, by mathematical induction for n ≥ 1, 5 ∣ 24n − 1

Thus, we use mathematical induction to establish the divisibility statements, 5 ∣ 24n−1

Here, we have to use mathematical induction to establish the divisibility statements, 21 ∣ 4n+1 + 52n-1

For ,n = 1: 42 + 51 = 21 and 21 ∣ 21.Suppose, it’s true for n = k then we want to prove it for n = k + 1.

Let 21 ∣ (4k+1+52k-1) ∴ ∃ x ∋ 21x = 4k+1 + 52k-1

Now, for n = k + 1

​43(k+2) − 52(k+1)−1 = 4k+2 − 52k+1

= 4⋅4k+1 + 52⋅52k-1 + 4⋅52k-1− 4⋅52k-1

= 4(4k+1 + 52k-1) + 21(52k-1)

= 4(21x) + 21(52k-1)

= 21(4x+52k-1)

∴ 21 ∣ (4(k+1)+1 + 52(k+1)-1)

Thus, by mathematical induction for n ≥ 1, 21∣(4k+1 + 52k+1)

Thus, we use mathematical induction to establish the divisibility statements, 21 ∣ 4n+1 + 52n-1

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

Now we want to prove by mathematical induction that 24 ∣ 4⋅7k + 20 for s = 1: 4⋅71 + 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⋅7s + 20 ∴ ∃ x ∋ 24x = 4⋅7s + 20

Now, for n = k + 1

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

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

= 7(24y) − 24⋅5

∴ ∃ q ∋ 24q = 4⋅7k + 20

∴ eq (1) = 5(24x) + 24q

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

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

 

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(2a2+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(2a2+7)

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

​⟹ 2a2 + 7 = 2(9q2+6q+1) + 7

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

thus 3∣∣2a2 + 7 ⟹ 3∣∣a(2a2+7)

Case 3: If a = 3q + 2 then, a2 = 9q2 + 12q + 4, ​

​⟹ 2a2 + 7 = 2(9q2+12q+4) + 7

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

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

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

Here, we have to verify that if a is odd ,then 32 ∣ (a2+3)(a2+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 a2 = 16q2 + 8q + 1

⟹ a2 + 3 = 16q2 + 8q + 4 = 4(4q2+2q+1)​⋯(1)

a2 + 7 = 16q2 + 8q + 8 = 8(2q2+q+1)​⋯(2)

From (1) and (2)

(a2+3)(a2+7) = [4(4q2+2q+1)][8(2q2+q+1)]

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

Thus 32 ∣ (a2+3)(a2+7)

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

a2 = 16q2 + 24q + 9

​⟹ a2 + 3 = 16q2 + 24q + 12 = 4(4q2+6q+3)​⋯(1)

a2 + 7 = 16q2 + 24q + 16 = 8(2q2+3q+2)​⋯(2)

from (1) and (2)

(a2+3)(a2+7) = [4(4q2+6q+3)][8(2q2+3q+2)]

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

Thus 32 ∣ (a2+3)(a2+7)

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

 

Page 25 Problem 7 Answer

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

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

Now,

a4 + b4 – 2 = (2r+1)4 + (2s+1)4 – 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(r4+s4) + 32(r3+s3) + 24r2 + 8r + 24s2 + 8s

to prove that 16 ∣ a4 + b4 − 2 we just need 16 ∣ 24r2 + 8r

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

​24(2k+1)2 + 8(2k+1)

= 96k2 + 96k + 24 + 16k + 8

= 96k2 + 96k + 16k + 32

= 16(8k2+8k+k+2)

If r is even then r = 2k,thus

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

Thus, 16 ∣ 24r2 + 8r, similarly 16 ∣ 24s2 + 8s

∴ 16 ∣ a4 + b4 − 2

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

 

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,

a2 + b2 = (2r+1)2 + (2s+1)2 = 4r2 + 4r + 1 + 4s2 + 4s + 1 = 4(r2+s2+r+s) + 2 = 4k + 2

where, k = r2 + s2 + r + s

Suppose a2 + b2 is a perfect square, then a2 + b2 = c2 = 4k + 2 = 2(2k+1)

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

Thus, a2 + b2 = c2 ⟹ 4k + 2 = 4l,this contradict the uniqueness of division algorithm, ∴ a2 + b2 ≠ c2 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) = (k2+3k)(k2+3k+2)

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

= (k2+3k+1)2 − 12

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

Hence (k2+3k+1)2 = p2

Therefore we have,

k(k+3)(k+1)(k+2) = p2 − 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)3 − a3

Solving (a+1)3 − a3 we get,

(a+1)3 − a3 = a3 + 3a2 + 3a + 1 − a3

= 3a2 + 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)3 − a3.

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

 

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

 

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

 

Page 25 Problem 17 Answer

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

For n = 1, we have,

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

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+1)) !}{(3 !)^{k+1}}=\frac{(3 k+3) !}{(3 !)^k(3 !)}\)

= \(\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!)n is an integer for all n ≥ 0.

We have proved that the expression(3n)!/(3!)​n 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.

 

Page 25 Problem 19 Answer

We are given,

If a is an arbitrary integer, then 6 ∣ a(a2+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(a2+11).

If r = 1,


​⟹ a = 6q + 1

⟹ (a2+11) = 36q2 + 12q + 12

= 6(6q2+2q+2)

So, 6∣(a2+11)

⟹ 6∣a(a2+11)

If r = 2

​⟹ a = 6q + 2

= 2(3q+1)

So,

2∣a and (a2+11)

(a2+11) = 36q2 + 24q + 15

= 3(12q2+8q+5)

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

⟹ 6a(a2+11)

If r = 3

​⟹ a = 6q + 3

= 3(2q+1)

So, 3∣a

(a2+11) = 36q2 + 36q + 20

(a2+11) = 2(18q2+18q+10)

So,

2∣(a2+11) ⟹ 6∣a(a2+11)

If r = 4

​​⟹ a = 6q + 4

= 2(3q+2)

So,

2∣a and (a2+11)

(a2+11) = 36q2 + 24q + 27

= 3(12q2+8q+9)

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

⟹ 6a(a2+11)

If r = 5,

​⇒ a = 6q + 5

⇒ (a2+11) = 36q2 + 60q + 36

= 6(6q2+10q+6)

So, 6∣(a2+11)

⇒ 6 ∣ a(a2+11)

Therefore in all cases 6 ∣ a(a2+11)

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

We are given,

If a is an order integer, then 24 ∣ a(a2−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

⟹ a2 = 16k2 + 8k + 1

= 8(2k2+k) + 1

so, a2= 8m + 1 where

m = 2k2 + k.

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

= 32km+8m

= 8(4km+m).

So 8∣a(a2−1)​⋯(1)

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

If r = 0

​⇒ 3∣a

⇒ 3∣a(a2−1).

If r = 1

​⇒ a = 3q + 1

⇒ a2 − 1 = 9q2 + 6q

= 3(3q2+2q).

So,​3∣(a2−1)

⟹ 3a(a2−1)

If r = 2

​⟹ a = 3q + 2

⟹ a2−1 = 9q2 + 12q + 3

= 3(3q2+4q+1).

So,​ 3∣(a2−1)

⟹ 3a(a2−1)

Since,

gcd(8,3) = 1

24 ∣ a(a2−1)

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

We are given that a and b are odd integers.

We have to prove that 8∣(a2−b2)

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

If ​a = 4k+1

b = 4m+1

then,

a2−b2 = (16k2+8k+1)−(16m2+8m+1)

= 16(k2−m2)+8(k−m)

= 8(2(k2−m2)+(k−m)).

Hence 8∣a2−b2

If​ a = 4k−1

b = 4m−1

then,

a2−b2 = (16k2−8k+1)−(16m2−8m+1)

= 16(k2−m2)−8(k−m)

= 8(2(k2−m2)−(k−m))

Hence 8∣a2−b2

If​ a = 4k−1

b = 4m + 1

then,

a2 − b2 = (16k2−8k+1) − (16m2+8m+1)

= 16(k2−m2) + 8(k+m)

= 8(2(k2−m2) + (k+m)).

Hence 8∣a2−b2

Therefore we conclude that 8∣a2−b2

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

We are given an assertion,

If a is an integer not divisible by 2 or 3, then 24∣(a2+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,

(a2+23) = (16k2+8k+24)

(a2+23) = 8(2k2+k+3)

Thus 8∣(a2+23)…(1)

Also,

(a2+23) = 9q2 + 6q + 24

(a2+23) = 3(3q3+2q+8)

Thus 3∣(a2+23)…(2)

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

Case 2

If​ a = 4k−1

= 3q + 2

So,

(a2+23) = (16k2−8k+24)

= 8(2k2−k+3).

Thus 8∣(a2+23)…(1)

Also,

(a2+23) = 9q2 + 12q + 27

(a2+23) = 3(3q3+4q+9)

Thus 3∣(a2+23)…(2)

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

Case 3

If a = 4k + 1

= 3q + 2

So,

(a2+23) = (16k2+8k+24)

(a2+23) = 8(2k2+k+3)

Thus 8∣(a2+23)…(1)

Also,

(a2+23) = 9q2 + 12q + 27

(a2+23) = 3(3q3+4q+9)

Thus 3∣(a2+23)…(2)

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

24∣(a2+23)

Case 4

If ​a = 4k − 1

= 3q + 1

So,

(a2+23) = (16k2−8k+24)

= 8(2k2−k+3).

Thus 8∣(a2+23)…(1)

Also,

(a2+23) = 9q2 + 6q + 24

(a2+23) = 3(3q2+2q+8)

Thus 3∣(a2+23)…(2)

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

24∣(a2+23)

Therefore we conclude that 24∣(a2+23)

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

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

We have,

a2(a2−1)(a2−4) = a2(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∣a2(a2−1)(a2−4)

⇒ 360∣a2(a2−1)(a2−4)

We have proved that if a is an arbitrary integer, then 360∣a2(a2−1)(a2−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)

= a2xf + abyf + acxt + bcyt

= a(axf+byf+cxt) + bcyt

= ak1+ bck2

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 2d−1∣2n−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 :

2n−1 = 2dm−1

= (2d)m−1

Now we will use the identity :

xk-1 = (x−1)(xk-1+xk-2+⋯+x+1)

Now we have ,

2n−1 = (2d)m−1

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

Hence, 2d−1∣2n−1.

2d – 1|2n-1 by using the identity:

xk-1 = (x-1)(xk-1 + xk-2+…+x+1).

235 – 1 is given.

We will verity that 235-1 is divisible by 31 and 127.

We will do it by using the identity.

We have :

31 = 25−1 and 127=27−1

And we have that 5∣35.

Now using the identity :

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

31 = 25−1∣235−1

And similarly we have 7∣35.

So, again using the identity we get :

127 = 27−1∣235−1

Yes, 235−1 is divided by 31 and 127.

 

Page 26 Problem 22 Answer

Given : Let tndenote the nth triangular number.

We will find for what values of n does tn divide the sum t1+t2+⋯+tn.

We will do it by using the formula above.

We have:

t1 + t2 + …+ tn = \(\frac{n(n+1)(n+2)}{6}\)

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

Now, therefore:

\(\frac{t_1+t_2+\cdots+t_n}{t_n}=\frac{\frac{n(n+1)(n+2)}{6}}{\frac{n(n+1)}{2}}\)

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

So, at the \(\frac{n+2}{3}\) integer tn divides t1 + t2 + …. + tn.

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 t1 + t2 + …. + tn.

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) = a2mr + acms + abrn + bcns

Now using equation one we get :

= a2mr + 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 Exercise 2.2

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

 

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: ∴ a2 = 9q2 = 3(3q2) = 3k where k = 3q2

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

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

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

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 n4 = (5q+r)4,from binomial expansion, each term is a factor of 5 except last term.

\((5 q+r)^4=\left(\begin{array}{c}
4 \\
0
\end{array}\right)(5 q)^4+\left(\begin{array}{c}
4 \\
1
\end{array}\right)(5 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)(5 q) r^3+r^4\)

⇒ \((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 r4 = 0, and n4 = 5k as all other terms have 5 as a factor

If r = 1 then r4 = 1,then clearly n4 = 5k + 1

If r = 2 then r4 = 16 = 15 + 1 = 3⋅5 + 1, so n4 = 5k + 1

If r = 3 then r4 = 81 = 80 + 1 = 5⋅16 + 1, so n4 = 5k + 1

If r = 4 then r4 = 256 = 255 + 1 = 5⋅51 + 1, so n4 = 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

 

Page 19 Problem 4 Answer

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

Proof :

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

3a2 − 1 = 3k + 1 or 3a{2} − 1 = 3k

∴ 3(a2−k) = 2 or 3(a2−k) = 1,

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

Thus, we proved that 3a2 − 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 n3 = (7q+r)3,from binomial expansion, each term is a factor of 7 except last term,

(7q+r)3 = \(\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, r3 = 0and n3 = 7k as all other terms have 7 as a factor.

If r = 1then, r3 = 1,then clearly n3 = 7k + 1

If r = 2then,

r3 = 8 = 7 + 1, so n3 = 7k + 1

If r = 3then,

r3 = 27 = 28 − 1 = 4⋅7 − 1, sо n3 = 7k − 1

If r = 4then,

r3 = 64 = 63 + 1 = 9⋅7 + 1, and n3 = 7k + 1

If r = 5then,

r3 = 125 = 126−1 = 18⋅7 − 1, so n3 = 7k − 1

If r = 6then,

r3 = 216 = 217 − 1 = 31⋅7 − 1, so n3 = 7k + 1

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

 

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,

\(-\frac{1}{2}|b|<r^*<\frac{1}{2}|b|, \text { letr }=r^{\prime}-|b| a n d q=q^{\prime}+\frac{|b|}{b}\)

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,

Ai= 11 + 4ri = 4(r+2) + 3, for certain ri

So, Ai = rr’i + 3 by division algorithm, r’ and 3 are unique. Suppose Ai = s2 let s = 4q + r

r ≠ 0,as

s2 = 16q2 = 4(4q2),which is not of the form 4ri′ + 3

r ≠ 1,as

s2 = 16q2 + 8q + 1 = 4(4q2+2q) + 1,which is not of the form 4ri′ + 3

r ≠ 2,as

s2 = 16q2 + 16q + 4 = 4(4q2 + 4q + 1),which is not of the form 4ri′ + 3

r ≠ 3,as

s2 = 16q2 + 24q + 9 = 4(4q2 + 2q + 2) + 1,which is not of the form 4ri′ + 3

Therefore there is no s such that s2 = 4ri + 3. All Ai are not perfect squares

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

 

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 = 82 = 43),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 s3 = (7k+b)3, from binomial expansion, each term is a factor of 7 except last term,

(7k+b)3 = \(\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, b3 = 0, and n3 = 7k as all other terms have 7 as a factor.

If b = 1 then, b3 = 1,then clearly n3 = 7k + 1

If b = 2 then,

b3 = 8 = 7 + 1,so n3 = 7k + 1

If b = 3 then,

b3 = 27 = 28 − 1 = 4⋅7 − 1, so n3 = 7k − 1

If b = 4 then,

b3 = 64 = 63 + 1 = 9⋅7 + 1, and n3 = 7k + 1

If b = 5 then,

b3 = 125 = 126 − 1 = 18⋅7 − 1, so n3 = 7k − 1

If b = 6 then,

b3 = 216 = 217 − 1 = 31⋅7−1, so n3 = 7k + 1

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

If d = 0 then,r2 = 7(7c2) = 7k

If d = 1 then,

r2 = 49c2 + 14c + 1 = 7(7c2+2c) + 1 = 7k + 1

If d = 2 then,

r2 = 49c2 + 28c + 4 = 7(7c2+4c) + 4 = 7k + 4

If d = 3 then,

r2 = 49c2 + 42c + 9 = 7(7c2+6c+1) + 2 = 7k + 2

If d = 4 then,

r2 = 49c2 + 56c + 16 = 7(7c2+8c+2) + 2 = 7k + 2

If d = 5 then,

r2 = 49c2 + 70c + 25 = 7(7c2+10c+3) + 4 = 7k + 4

If d = 6 then,

r2 = 49c2 + 84c + 36 = 7(7c2+12c+5) + 1 = 7k + 1

Thus r2 is of the form : 7k, 7k+1, 7k+2 or 7k+4 and s3 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 = 82 = 43),then it must be either of the form 7k or 7k+1

 

Page 19 Problem 10 Answer

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

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

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

If n = 6k + 1 then,

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

If n = 6k + 2 then,

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

If n = 6k + 3 then,

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

If n = 6k + 4then,

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

If n = 6k + 5 then,

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

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

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

 

Page 19 Problem 11 Answer

Here, we have to show that n4 + 4n2 + 11 is of the form 16k

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

n4 + 4n2 + 11 = (n2+2)2 + 7

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

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

= (4r2+4r+3)2 + 7

= [(4r2+4r)+3]2 + 7

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

= 16r4 + 2⋅4r2⋅4r + 16r2 + 24r2 + 24r + 9 + 7

= 16r4 + 32r3 + 16r2 + 24r2 + 24r + 9 + 7

= 16r4 + 32r3 + 40r2 + 24r + 16

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

If r = 2q: ​

​16(2q)4 + 32(2q)3 + 40(2q)2 + 24(2q) + 16

= 16[(2q)4 + 2(2q)3 + 10q2 + 3q + 1]

= 16k

If r = 2q + 1:​

​16(2q+1)4 + 32(2q+1)3 + 40(2q+1)2 + 24(2q+1) + 16

= 16(2q+1)4 + 32(2q+1)3 + 160q2 + 160q + 40 + 48q + 24 + 16

= 16[(2q+1)4 + 2(2q+1)3 + 10q2 + 10q + 3q + 4 + 1]

= 16k

Thus, we showed that n4 + 4n2 + 11 is of the form 16k

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

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:

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

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:

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

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

= 4k2 + 4k + 1

= (2k+1)2

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

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

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

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

4r2 + 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:

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

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:

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

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.

 

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,

t1+ t2 + t3 + …. + \(\frac{n(n+1)(n+2)}{6}\) n ≥ 1. It’s given that, tk-1 + tk = k2

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\)

∴ t1 + t2 + t3 + …. + \(\frac{n(n+1)(n+2)}{6}\)

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

t1 + t2 + t3 + …. + \(\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)2 = t9n+4 − t3n+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

\(t_{9 n+4}=\frac{(9 n+4)(9 n+5)}{2}, t_{3 n+1}=\frac{(3 n+1)(3 n+2)}{2}\)

Therefore,

\(t_{9 n+4}-t_{3 n+1}=\frac{\left(81 n^2+81 n+20\right)-\left(9 n^2+9 n+2\right)}{2}\)

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

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

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} = t9n+4 − t3n+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)2 or (n+2)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}\) = 32 . 52 . 4 = 302 = 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

 

Page 16 Problem 6 Answer

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

Proof: Assume

tn = k2 = \(\frac{n(n+1)}{2}\), then 2k2 = n(n+1)

t4n(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]\)

= 4k2(2n+1)2

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

Thus, we prove that t4n(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) t1 = 1 is a perfect square. t4⋅1(1+1) = t8 = 36 is a perfect square.

\(t_{4 \cdot 8(8+1)}=t_{288}=\frac{288(288+1)}{2}\) = 41616 = 2042 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.

 

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}{t_k}=\frac{1}{\frac{k(k+1)}{2}}=\frac{2}{k(k+1)}=2\left(\frac{1}{k}-\frac{1}{k+1}\right)\)

∴ \(\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,

\(n>0 \Rightarrow n+1>0 \Longrightarrow \frac{1}{n+1}>0 \Longrightarrow-\frac{1}{n+1}<0\) \(\Longrightarrow 1-\frac{1}{n+1}<1 \Longrightarrow 2\left(1-\frac{1}{n+1}\right)<2\)

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

\(\frac{1}{1}+\frac{1}{3}+\frac{1}{6}+\frac{1}{10}+\cdots+\frac{1}{t_n}<2\)

 

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}\)

= tx = 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 : t3 = t2 + t2, or 6 = 3 + 3

n = 2 : t6 = t3 + t5, or 21 = 6 + 15

n = 3 : t10 = t4 + t9, or 55 = 10 + 45

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

​n = 1 : t3 = t2 + t2, or 6 = 3 + 3

n = 2 : t6 = t3 + t5, or 21 = 6 + 15

n = 3 : t10 = t4 + t9, or 55 = 10 + 45

 

Page 16 Problem 10 Answer

Here, we have to prove that pn = \(\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:

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

Let pn denotes nth pentagonal number where, p1 = 1

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

We need to prove that n th pentagonal number is given by formula pn = \(\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, pk = \(\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, pk+1 = pk + 3(k+1)-2

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

pk+1 = pk + 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 pn = \(\frac{n(3 n-1)}{2}\), n ≥ 1

 

Page 16 Problem 11 Answer

Here, we have to verify the relations between the pentagonal, square, and triangular numbers: pn = tn-1 + n2

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

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

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

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

= pn

So, that this relation is correct.

Thus, we verified the relations between the pentagonal, square, and triangular numbers ; pn = tn-1 + n2

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

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

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

= \(\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}\)

= 2tn-1 + tn

So, the these relations are correct

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

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries Exercise 1.1

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries

Page 7 Problem 2 Answer

Given: a + ar + ar2 + …. + arn = \(\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 + ar2 + …. + arn = \(\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 + ar2 = a(r2 + 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(r2 + 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 + ar2 + …. + arn = \(\frac{a\left(r^{n+1}-1\right)}{r-1}\)

 

Page 7 Problem 3 Answer

Given: an−1 = (a−1)(an-1 + an-2 + an-3 + ⋯ + a + 1)

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

an-1 = (a-1)(an-1 + an-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.

ak−1 = (a−1)(ak-1 + ak-2 + ⋯ + a + 1)

Then

ak+1 − 1 = ak+1 − ak + ak − 1

= ak(a−1) + (a−1)(ak-1 + ak-2 + ⋯ + a + 1)

= (a−1)(ak + ak-1 + ak-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.

David Burton Elementary Number Theory Solutions Chapter 1 Preliminaries Exercise 1.1

Page 7 Problem 4 Answer

Given:

n3 = (13 + 23 + ⋯ + n3) − (13 + 23 + ⋯ + (n−1)3).

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

we use the relation that

13 + 23 + … + n3 = \(\left(\frac{n(n+1)}{2}\right)^2\)

We know that

n3 = (13 + 23 + ⋯ + n3) − (13 + 23 + ⋯ + (n−1)3)

Using the above relation, we get

n3 = \(\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 n3 = \(\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.

 

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 = 52

n:5 ⇒​ n! + 1 = 112

​n = 6 ⇒ ​n!+1 = 721

n = 7 ⇒​ n!+1 = 5041 = 712

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! > n2 for every integer n ≥ 4, where as n! > n3 for every integer n ≥ 6.

We prove it via finite induction. We know 4! = 24 ≥ 16 = 42 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)k2 > (k+1)2

[Note* here we use k2 ≥ k+1]

This shows n! > n2 for all n ≥ 4 by induction.

For n = 6, we have 6! = 720 > 216 = 63. Let this be true for some integer k i.e. k! > k3, then

(k+1)! = (k+1)k! > (k+1)k3 > (k+1)(k+1)2 = (k+1)3

[There we use k3 >(k+1)2 for all k ≥ 3].

This shows n! > n3 for all n ≥ 6.

We get that n! > n3 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: 2n(n!) ≤ \(\frac{(2 n) !}{n !}\)

Using part (a): 2⋅6⋅10⋅14⋯(4n−2) ≥ 2n(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) ≥ 2k(k!)

Now for r = k+1,2⋅6⋅10⋅14⋯(4k−2)⋅(4k+2) ≥ 2k(k!)(4k+2)

= 2k(k!)2(2k+1)=2k+1(k+1)!

Therefore, k + 1 satisfies Eq.(1), thus k+1 ∈ S

Thus, 2⋅6⋅10⋅14⋯(4n−2) ≥ 2n(n!)

We get, 2.6.10.14…(4n-2) ≥ 2n(n!) is true for all n ≥ 1.

 

Page 7 Problem 9 Answer

We have to Establish the Bernoulli inequality: If 1 + a > 0, then(1+a)n ≥ 1 + na for all n ≥ 1.

If 1 + a > 0, we need to prove that for each integer n ≥ 1 inequality

(1+a)n ≥ 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 + ka2

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

 

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

\(\frac{1}{1^2}+\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{n^2} \leq 2-\frac{1}{n}\)

For n = 1, we have

\(\frac{1}{1^2} \leq 2-\frac{1}{1}=n\)

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:

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

For n = 1, we have

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

So the relation holds for n = 1.

Let the relation hold for some integer k, i.e.

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

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.

 

Page 7 Problem 11 Answer

We have to show that the expression (2n)!/2nn! 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

2n . 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 ≤ 1016.

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.

\(\begin{array}{l|l}
\mathrm{k} & T^k( \\
0 & 23 \\
1 & 35 \\
2 & 53 \\
3 & 80 \\
4 & 40 \\
5 & 20 \\
6 & 10 \\
7 & 5 \\
8 & 8 \\
9 & 4 \\
10 & 2
\end{array}\)

We get,

For n = 21

\(\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

\(\begin{array}{l|l}
\mathrm{k} & T^k( \\
0 & 23 \\
1 & 35 \\
2 & 53 \\
3 & 80 \\
4 & 40 \\
5 & 20 \\
6 & 10 \\
7 & 5 \\
8 & 8 \\
9 & 4 \\
10 & 2
\end{array}\)

 

Page 8 Problem 13 Answer

Given: Suppose that the numbers an are defined inductively by

a1= 1, a2 = 2, a3 = 3a1=1, a2 = 2, a3 = 3, and

an = an-1 + an-2 + an-3 for all n ≥ 4.

To find: Use the Second Principle of Finite Induction to show that an < 2n for every positive integer n.

Given that a1 = 1, a2 = 2, a3 = 3 and

an = an-1 + an-2 + an-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

​= ak + ak-1 + ak-2

< 2k + 2k-1 + 2k-2

= 2k-2(1+2+4)

< 2k+1

Or,

ak+1 < 2k+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.

 

Page 8 Problem 14 Answer

Given: If the numbers an are defined by a1 = 11, a2 = 21, and an = 3an-1 – 2an-2 for n ≥ 3

To prove: an = 5.2n + 1 n ≥ 1

Let a1 = 11 and a2 = 21 and an be defined by

an = 3an-1 − 2an-2

Then an = 5⋅2n+1,n ≥ 1. This is true for n = 1,2,3 since

​a1 = 5⋅2 + 1 = 11

a2 = 5⋅4 + 1 = 21

a3 = 41 = 3⋅21 − 2⋅11

Let this be true for all integers r ≤ k. i.e.

ar = 5⋅2r + 1,r ≤ k

Then

ak+1 = 3ak − 2ak-1

= 3(5⋅2k+1) − 2(5⋅2k-1+1)

= 5⋅2k-1(6−2) + 3 − 2

= 5⋅2k+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}{c}
n \\
k
\end{array}\right)\left(\begin{array}{c}
k \\
r
\end{array}\right)=\left(\begin{array}{c}
n \\
r
\end{array}\right)\left(\begin{array}{c}
n-r \\
k-r
\end{array}\right) \quad n \geq k \geq r \geq 0\)

\(\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

\(\left(\begin{array}{c}
n \\
k
\end{array}\right)\left(\begin{array}{c}
k \\
k-1
\end{array}\right)=\left(\begin{array}{c}
n \\
k-1
\end{array}\right)\left(\begin{array}{c}
n-k+1 \\
1
\end{array}\right)\)

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)\)

 

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:

\(\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)\)

Take the right hand side:

\(\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)\)

= \(\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,

\(\left(\begin{array}{l}
n \\
r
\end{array}\right)<\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\)

<=> \(\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,

\(\left(\begin{array}{l}
n \\
r
\end{array}\right)>\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\)

<=> \(\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,

\(\left(\begin{array}{l}
n \\
r
\end{array}\right)=\left(\begin{array}{c}
n \\
r+1
\end{array}\right)\)

<=> 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)\).

 

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

\(\left(\begin{array}{c}
r \\
s
\end{array}\right)+\left(\begin{array}{c}
r \\
s-1
\end{array}\right)=\left(\begin{array}{c}
r+1 \\
s
\end{array}\right), 1 \leq s \leq r\)

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

\(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\cdots\left(\begin{array}{l}
k \\
2
\end{array}\right)=\left(\begin{array}{c}
k+1 \\
3
\end{array}\right)\)

Then

\(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\cdots\left(\begin{array}{l}
k \\
2
\end{array}\right)+\left(\begin{array}{c}
k+1 \\
3
\end{array}\right)\)

= \(\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

\(\left(\begin{array}{l}
2 \\
2
\end{array}\right)+\cdots\left(\begin{array}{l}
n \\
2
\end{array}\right)=\left(\begin{array}{c}
n+1 \\
3
\end{array}\right) . \text { for } n \geq 2\)

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 m2 = 2\(\left(\begin{array}{l}
m \\
2
\end{array}\right)\) + m for m ≥ 2,

We have to deduce the formula 12 + 22 + 32 +….+n2 = \(\frac{n(n+1)(2 n+1)}{6}\)

First we want to prove that m2 = 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:

12 + 22+ 32 +….+n2 = \(\frac{n(n+1)(2 n+1)}{6}\)

Proof:

12 + 22 + …. + n2

= \(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, 12 + 22 + 32 +….+n2 = \(\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)

m2 = 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}\)

 

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}{c}
2 m \\
2
\end{array}\right)=\frac{(2 m) !}{2 !(2 m-2) !}=\frac{(2 m)(2 m-1)}{2}=2 m^2-m=m^2+m^2-m=m^2+2\left(\begin{array}{c}
m \\
2
\end{array}\right) \mathrm{m} \geq 2 \text { from ex } 5 \text { (c) }\)

∴ \(\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,

\(\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\)

 

Page 12 Problem 7 Answer

Here, we have to verify that

12 + 32 + 52 + …. + (2n-1)2 = \(\left(\begin{array}{c}
2 n+1 \\
3
\end{array}\right)\)

We solve this by mathematical induction on n.

For the case n = 1, 12 = \(\left(\begin{array}{c}
3 \\
3
\end{array}\right)\) = 1

Assume that the identity is true for some k > 1.

For some k > 1,

12 + 32 + 52 + … + (2k−1)2 = \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\)

Add (2k+1)2 to both sides

L.H.S 12 + 32 + 52 + … + (2k-1)2 + (2k+1)2

R.H.S = \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\) + (2k+1)2

= \(\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

12 + 32 + 52 + …. + (2k+1)2 = \(\left(\begin{array}{c}
2 k+1 \\
3
\end{array}\right)\)

Thus, we verified that

12 + 32 + 52 + …. + (2n-1)2 = \(\left(\begin{array}{c}
2 n+1 \\
3
\end{array}\right)\)

 

 

Page 12 Problem 8 Answer

Here, we have to show that for n ≥ 1,

\(\left(\begin{array}{c}
2 n \\
n
\end{array}\right)=\frac{1 \cdot 3 \cdot 5 \cdots(2 n-1)}{2 \cdot 4 \cdot 6 \cdots 2 n} 2^{2 n}\)

Expand the L.H.S according to definition,

\(\left(\begin{array}{c}
2 n \\
n
\end{array}\right)=\frac{1 \cdot 3 \cdot 5 \cdots(2 n-1)}{2 \cdot 4 \cdot 6 \cdots 2 n} 2^{2 n}\)

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,

\(\left(\begin{array}{c}
2 n \\
n
\end{array}\right)=\frac{1 \cdot 3 \cdot 5 \cdots(2 n-1)}{2 \cdot 4 \cdot 6 \cdots 2 n} 2^{2 n}\)

 

Page 12 Problem 9 Answer

Here, we have to show that x > y > z, hence x2 > 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: 2kk! = 2.4.6….2n-1

So,

2kk! < 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),

\(\left(\begin{array}{c}
2 k \\
k
\end{array}\right)=\frac{1 \cdot 3 \cdot 5 \cdots(2 k-1)}{2 \cdot 4 \cdot 6 \cdots 2 k} 2^{2 k}<2^{2 k}, n \geq 1\)

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 Cn can be given inductively by Cn = \(\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} C_{n-1}=\frac{2(2 n-1)}{n+1} \frac{(2 n-2) !}{(n-1) !(n) !}\)

= \(\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 !}\)

= Cn

Thus, we proved that Cn can be inductively by Cn = \(\frac{2(2 n-1)}{n+1} C_{n-1}\)