## Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.28

28.  Show that the union of two countable sets is countable.

Solution: We assume that A and B are two countable sets.
We will consider following cases.
Case 1:
If bothA and B are finite, then $A\cup B$ is finite and hence countable.
Case 2:
We assume that one of A and B is finite and the other is countable infinite. We assume without loss of generality that A is finite.
Since B is countably infinite, there exists a function
$f:B \rightarrow \mathbb{Z^+}$
This is a one-to-one correspondence, that is,
$f(b_i)=i$
For $b_i \epsilon B$ and $i \epsilon \mathbb{Z^+}$
Let us consider
C=A-B
Thus,
$A \cup B = B\cup C$
If $C=$Ø
Then $A \cup B = B$
This is countably infinite.
Therefore, we assume that $C\neq$Ø
Also we suppose that
$C=\left \{ c_1,c_2,...,c_n \right \}$
We consider the function
$g:B \cup C \rightarrow \mathbb{Z^+}$
Where $g(c_j)=j$
And $g(b_i)=n+i$
Clearly, g is one-to-one and onto.
Thus,$B \cup C$ is countable.
But $B \cup C = A \cup B$
So, $A \cup B$ is countable.
Case 3:
We suppose that both A and B are infinite and $A\cap B=$Ø
Since A and B are both countable, there exist functions
$p:\mathbb{Z^+} \rightarrow A$
$q:\mathbb{Z^+} \rightarrow B$
These are one-to-one correspondences.
We also consider the function
$r:\mathbb{Z^+} \rightarrow A \cup B$
Where $r(n)=p\left ( \frac{n}{2} \right )$
If n is even
And $r(n)=q\left ( \frac{n+1}{2} \right )$
If n is odd
Since p,q are one-to-one, so r is also one-to-one.
Similarly, since p,q are onto, so r is also onto.
Therefore, r is a one-to-one correspondence, and hence,r is countable.
Case 4:
We suppose that both A and B are infinite and $A \cap B=$Ø
We assume that C=B-A
Then,
$A \cup B= A \cup C$
And
$A \cap C=$Ø
If C is countably infinite, then
$A \cup B= A \cup C$
Is countable by the previous case
If C is finite, then
$A \cup B= A \cup C$
Is countable by case 2
Therefore, $A \cup B$ is countable.

## Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.27

27. Show that the set of all numbers of the form $a+b\sqrt{2}$ where a and b are integers, is countable.

Solution: We shall first prove a proposition.
We assume that A is a non-empty set. Then the following are equivalent.
(a) A is countable
(b) there exists a surjection $f: \mathbb{Z^+} \rightarrow A$
(c) there exists an injection $g: A \rightarrow \mathbb{Z^+}$

Proof
$(a) \Rightarrow (b)$
If A is countably infinite, then there exists a bijection
$f: \mathbb{Z^+} \rightarrow A$
And then (b) follows
If A is finite, then there is a bijection
$h:\left \{ 1,...,n \right \} \rightarrow A$
For some n
Then the function $f: \mathbb{Z^+} \rightarrow A$ defined by
$f\left (i \right )=\left\{\begin{matrix} h\left (i \right ) & 1\leq i \leq n\\ h\left (n \right ) & i> n \end{matrix}\right.$
Is a surjection
$(b) \Rightarrow (c)$
We assume that $f: \mathbb{Z^+} \rightarrow A$ is a surjection. We claim that there is an injection $g: A \rightarrow \mathbb{Z^+}$
To define g we note that if
$a\epsilon A$
Then
$f^{-1}(\left \{a \right \})\neq \phi$
Hence, we set
$g(a)=min f^{-1}(\left \{a \right \})$
Now we note that if
$a \neq a'$
Then
$f^{-1}(\left \{ a \right \})\bigcap f^{-1}(\left \{ a' \right \})=\phi$
Implies
$min f^{-1}(\left \{ a \right \})\neq min f^{-1}(\left \{ a' \right \})$
Hence
$g(a)\neq g(a')$
And $g: A \rightarrow \mathbb{Z^+}$ is an injection
$(c) \Rightarrow (a)$
We assume that $g: A \rightarrow \mathbb{Z^+}$ is an injection. We want to show that A is countable.
Since
$g:A \rightarrow g(A)$
Is a bijection and
$g(A)\subset \mathbb{Z^+}$
That is, the subset of a countable set is countable.
So, A is countable.
This ends the proposition.
We now show that the set of all numbers of the form $a+b\sqrt{2}$ where a,b are integers, is countable.
By the above proposition it suffices to construct an injective function
$f:\mathbb{Z^+}\times \mathbb{Z^+} \rightarrow \mathbb{Z^+}$
We define it as
$f(a,b)=2^a3^b$
We assume that
$2^a3^b=2^c3^d$
If
a<c
Then
$3^b=2^{c-a}3^d$
The left side of this equality is an odd number where as the right side is an even number implying
a=c
And
$3^b=3^d$
Then also
b=d
Hence, f is injective and so set of all numbers of the form $a+b\sqrt{2}$ where a,b are integers, is countable.

## Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.26

26. Show that the set of all rational numbers of the form n/5, where n is an integer, is countable.

Solution:

We have to show that the set of all rational numbers of the form n/5 where n is an integer, is countable.
We shall first prove a proposition.
We assume that A is a non-empty set. Then the following are equivalent.
(a) A is countable
(b) there exists a surjection $f: \mathbb{Z^+} \rightarrow A$
(c) there exists an injection $g: A \rightarrow \mathbb{Z^+}$

Proof
$(a) \Rightarrow (b)$
If A is countably infinite, then there exists a bijection
$f: \mathbb{Z^+} \rightarrow A$
And then (b) follows
If A is finite, then there is a bijection
$h:\left \{ 1,...,n \right \} \rightarrow A$
For some n
Then the function $f: \mathbb{Z^+} \rightarrow A$ defined by
$f\left (i \right )=\left\{\begin{matrix} h\left (i \right ) & 1\leq i \leq n\\ h\left (n \right ) & i> n \end{matrix}\right.$
Is a surjection
$(b) \Rightarrow (c)$
We assume that $f: \mathbb{Z^+} \rightarrow A$ is a surjection. We claim that there is an injection $g: A \rightarrow \mathbb{Z^+}$
To define g we note that if
$a\epsilon A$
Then
$f^{-1}(\left \{a \right \})\neq \phi$
Hence, we set
$g(a)=min f^{-1}(\left \{a \right \})$
Now we note that if
$a \neq a'$
Then
$f^{-1}(\left \{ a \right \})\bigcap f^{-1}(\left \{ a' \right \})=\phi$
Implies
$min f^{-1}(\left \{ a \right \})\neq min f^{-1}(\left \{ a' \right \})$
Hence
$g(a)\neq g(a')$
And $g: A \rightarrow \mathbb{Z^+}$ is an injection
$(c) \Rightarrow (a)$
We assume that $g: A \rightarrow \mathbb{Z^+}$ is an injection. We want to show that A is countable.
Since
$g:A \rightarrow g(A)$
Is a bijection and
$g(A)\subset \mathbb{Z^+}$
That is, the subset of a countable set is countable.
So, A is countable.
This ends the proposition.
We define the function
$f:\mathbb{Z} \times \mathbb{Z^+}\rightarrow \mathbb{Q}$
As
f(n,5)=n/5
Since each rational number is of the form n/5 for some $n \epsilon \mathbb{Z}$, it follows that f is surjective.
Since $\mathbb{Z} \times \mathbb{Z^+}$ is countably infinite, that is, the Cartesian product of countable sets is countable, it follows from part (b) of the above proposition and replacing $\mathbb{Z^+}$ by an arbitrary countably infinite set (using composition of functions), that rational numbers of the form n/5 is countable.

## Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.25

25. Show that the set of all integers greater than -100 is countable.

Solution: In order to prove that the set of all integers greater than -100 is countable, it suffices to prove that the set of integers $\mathbb{Z}$ is countable. This follows from the fact that the subset of a countable set is countable.

We can the list the integers in a sequence
0,1,-1,2,-2,3,-3,…
We define a function
$f:\mathbb{N} \rightarrow \mathbb{Z}$

This is defined as
$f(n)=\left\{\begin{matrix} \frac{n}{2}&\text{n is even} \\ \frac{-(n-1)}{2}& \text{n is odd}\end{matrix}\right.$

We now show that $f$ is a bijection.
First we show that it is injective by case analysis on the parity of $\mathbb{N}$
Case 1
If $m,n$ are two even natural numbers
Then
$f(m)=\frac{m}{2}$
$f(n)=\frac{n}{2}$
It follows that
$f(m)=f(n)$
Implies that
$m=n$
Case 2
If $m,n$ are two odd natural numbers
Then
$f(m)=-\frac{m-1}{2}$
$f(n)=-\frac{n-1}{2}$
It follows that
$f(m)=f(n)$
Implies that
$m=n$
Therefore $f$ is injective.
We now show that $f$ is surjective by case analysis on the sign of some integer $t$ in $\mathbb{Z}$
Case 1
If $t$ is positive, then $t$ will appear in an even position in the sequence.
Thus,
$f(2k)=\frac{2k}{2}$
$=t$
With
$t=k$
This implies that for every positive value $t$ in $\mathbb{Z}$ there is a natural number $2k$
Case 2
If $t$ is negative, then $t$ will appear in an odd position in the sequence.
Thus,
$f(2k-1)=-\frac{(2k-1)-1}{2}$
$=t$
With
$t=-k$
This implies that for every negative value $t$ in $\mathbb{Z}$ there is a natural number $2k-1$
Therefore, $f$ is surjective
Hence, $\mathbb{Z}$ is countable set.
Now we define the sequence
$a_n=n-100$
$>-100$
For $n \in \mathbb{N}$
This is clearly a subset of $\mathbb{Z}$ and so is countable.

## Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.24

24. Find three different formulas or rules for the terms of a sequence $a_n$ if the first three terms of this sequence are 2, 3, 6.

Solution: We consider the first three terms of a sequence 2,3,6.
The simplest form of this sequence is
$a_n=2^{n}-(n-1)$
For $n=1,2,3,...$
We can even use recursive formula for this sequence, that is,
$a_1=2$
$a_2=3$
$a_n=a_{n-1}.a_{n-2}$
For $n \geq 3$
We can also formulate the nth term of this sequence by inserting factorials and doing inspection.
$2=\frac{(1+1)!}{2^0}$
$3=\frac{(2+1)!}{2^1}$
$6=\frac{(3+1)!}{2^2}$
Therefore, we have for $n=1,2,3,...$
$a_n=\frac{(n+1)!}{2^{n-1}}$

## Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.23

23. Find three different formulas or rules for the terms of a sequence ${a_n}$  if the first three terms of this sequence are  1,2,4.

Solution: We consider the first three terms of a sequence as 1,2,4

The simplest form of this sequence is

$a_n=2^{n-1}$
For $n=1,2,3,...$
We can even use recursive formula for this sequence, that is,
$a_1=1$
$a_2=2$
$a_n=a_{n-1}+2a_{n-2}$
For $n \geq 3$
We can also formulate the $nth$ term of this sequence by inspection.
$1=\frac{1^2-1+2}{2}$
$2=\frac{2^2-2+2}{2}$
$4=\frac{3^2-3+2}{2}$
Therefore, we have for $n=1,2,3,...$
$a_n=\frac{n^2-n+2}{2}$

## Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.22

22. Conjecture a formula for the nth term of ${a_n}$  if the first ten terms of this sequence are as follows.

a) 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366
b) 1, 1, 0, 1, 1, 0, 1, 1, 0, 1
c) 1, 2, 3, 5, 7, 10, 13, 17, 21, 26
d) 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365

Solution:

(a) 2, 6, 18, 54,162,486,1458,4374,13122,39366

We can see that this sequence is neither in arithmetic progression nor in geometric Progression. We use the method of inspection to find the $nth$ term of this sequence.

$2=2(3^0)$
$6=2(3^1)$
$18=2(3^2)$
$54=2(3^3)$
$162=2(3^4)$
$486=2(3^5)$
$1458=2(3^6)$
$4374=2(3^7)$
$13122=2(3^8)$
$39366=2(3^9)$

Therefore we have for $n=1,2,...,10$

$a_n=2(3^{n-1})$

(b) 1,1,0,1,1,0,1,1,0,1

This sequence contains 0’s and 1’s only. We notice that 0 occurs in third multiple term of the sequence.
Therefore, we have for $n=1,2,...,10$

$a_n = \left\{\begin{matrix}0; n=3m&for& m=1,2,3 & \\1; otherwise & \end{matrix}\right.$

(c) 1, 2, 3,5,7,10,13,17,21,26

We can see that this sequence is neither in arithmetic progression nor in geometric Progression. We split the sequence into odd and even terms and use the method of inspection to find the $nth$ term of this sequence. Now, for 1,3,7,13,21 we have

$1=1^2-0$
$3=2^2-1$
$7=3^2-2$
$13=4^2-3$
$21=5^2-4$

So the odd termed sequence is of the form

$a_{2n-1} = n^2-(n-1)$
Where $n=1,2,3,4,5$
Similarly, for 2,5,10,17,26 we have

$2=1^2+1$
$5=2^2+1$
$10=3^2+1$
$17=4^2+1$
$26=5^2+1$

So the even termed sequence is of the form

$a_{2n}=n^2+1$
where n=1,2,3,4,5
Therefore, we have for n=1,2,…,10

$a_n = \left\{\begin{matrix} a_{2m-1} = m^2-(m-1),m=1,2,3,4,5 & \\ a_{2m} = m^2 + 1,m=1,2,3,4,5 & \end{matrix}\right.$

(d) 3, 5,11,21,43,85,171,341,683,1365

We can see that this sequence is neither in arithmetic progression nor in geometric Progression. We use the method of inspection to find the $nth$ term of this sequence.

$5=2.3-(-1)^2$
$11=2.5-(-1)^3$
$21=2.11-(-1)^4$
$43=2.21-(-1)^5$
$85=2.43-(-1)^6$
$171=2.85-(-1)^7$
$341=2.171-(-1)^8$
$683=2.341-(-1)^9$
$1365=2.683-(-1)^10$

Therefore we have for n=1,2,….,10

$a_1=3,a_n=2a_{n-1}-(-1)^n, n \geq 2$

## Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.21

21. Conjecture a formula for the nth term of ${a_n}$ if the first ten terms of this sequence are as follows.
a) 3, 11,19,27,35,43,51,59,67,75
b) 5, 7, 11, 19, 35,67, 131,259,515, 1027
c) 1,0,0, 1,0,0,0,0,1,0
d) 1, 3,4,7,11,18,29,47,76,123

Solution:

(a) 3,11,19,27,35,43,51,59,67,75

We can see that this sequence is neither in arithmetic progression nor in geometric Progression. We use the method of inspection to find the nth term of this sequence.

$3=8(1)-5$
$11=8(2)-5$
$19=8(3)-5$
$27=8(4)-5$
$35=8(5)-5$
$43=8(6)-5$
$51=8(7)-5$
$59=8(8)-5$
$67=8(9)-5$
$75=8(10)-5$

Therefore we have for $n=1,2,3,...,10$
$a_n=8n-5$

(b) 5, 7,11,19,35,67,131,259,515,1027

We can see that this sequence is neither in arithmetic progression nor in geometric Progression. We use the method of inspection to find the nth term of this sequence.

$5=2+3$
$7=2^2+3$
$11=2^3+3$
$19=2^4+3$
$35=2^5+3$
$67=2^6+3$
$131=2^7+3$
$259=2^8+3$
$515=2^9+3$
$1027=2^{10}+3$

Therefore we have for $n=1,2,3,...,10$
$a_n=2^n+3$

(c) 1,0,0,1,0,0,0,0,1,0
We can see that this sequence is neither in arithmetic progression nor in geometric Progression. It might strike to use greatest integer function here. We observe that For perfect squares the value turns out to be 1 otherwise it is 0. So, we use the method of inspection to find the nth term of this sequence.
$1=[[\sqrt{1}]/\sqrt{1}$
$0=[[\sqrt{2}]/\sqrt{2}$
$=[1/\sqrt{2}]$

$0=[[\sqrt{3}]/\sqrt{3}]$
$=[1/\sqrt{3}]$
$1=[[\sqrt{4}]/\sqrt{4}]$
$=[2/2]$

$0=[[\sqrt{5}]/\sqrt{5}]$
$=[2/\sqrt{5}]$
$0=[[\sqrt{6}]/\sqrt{6}]$
$=[2/\sqrt{6}]$

$0=[[\sqrt{7}]/\sqrt{7}]$
$=[2/\sqrt{7}]$

$0=[[\sqrt{8}]/\sqrt{8}]$
$=[2/2 \sqrt{2}]$
$=[1/\sqrt{2}]$

$1=[[\sqrt{9}]/\sqrt{9}]$
$=[3/3]$

$0=[[\sqrt{10}]/\sqrt{10}]$
$=[3/\sqrt{10}]$

Therefore we have for $n=1,2,...10$

$a_n=[[\sqrt{n}]/\sqrt{n}]$

(d) 1, 3,4,7,11,18,29,47,76,123

We define Lucas numbers recursively by

$L_n = L_{n-1} + L_{n-2}$
For $n \geq 3$ with
$L_1 =1$
$L_2 =3$
Now, we use the recursive formula to find the successive numbers.
That is,

$L_3 = L_2 + L_1$
$= 3 + 1$
$= 4$

$L_4 = L_3 + L_2$
$= 4 + 3$
$= 7$

$L_5 = L_4 + L_3$
$= 7 + 4$
$= 11$

$L_6 = L_5 + L_4$
$= 11 + 7$
$= 18$

$L_7 = L_6 + L_5$
$= 18 + 11$
$= 29$

$L_8 = L_7 + L_6$
$= 29 + 18$
$= 47$

$L_9 = L_8 + L_7$
$= 47 + 29$
$= 76$

$L_10 = L_9 + L_8$
$= 76 + 47$
$= 123$

Replacing $L_n$ with $a_n$ we have
$a_n = a_{n-1} + a_{n-2}$

For $n \geq 3$ with
$a_1 = 1$
$a_2 = 3$

## Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.20

20. Show that if m is a positive integer,then $[mx] = [x] + [x + (1/m) ] + [x + ( 2/m) ] +$ · · ·$+ [x + (m - 1) /m]$ whenever $x$ is a real number.
Solution:

We have to show that m if is a positive integer, then
$[mx]=[x]+[x+(1/m)]+[x+(2/m)]+...+[x+(m-1)/m]$….(1)
Whenever $x$ is a real number
We consider
$x=[x]+{x}$
Where $[x]$ is the greatest integer part of $x$ and ${x}$ is the fractional part of $x$
We also know that
$[integer+(...)]=integer+[(...)]$
We now, consider the right hand side of (1)
$RHS=[[x]+{x}]+[[x]+{x}+1/m]+[[x]+{x}+2/m]+...$
$+[[x]+{x}+(m-1)/m]$
$=m[x]+[{x}]+[{x}+1/m]+[{x}+2/m]+...+[{x}+(m-1)/m]$
$=m[x]+[{x}]+[{x}+1/m]+[{x}+2/m]+...+[{x}+p/m]+...$
$+[{x}+(m-1)/m]$
Where $p$ is the minimum value such that
$[{x}+p/m]=1$
Proceeding further, we get,
$RHS=m[x]+0+0+0+...p$ times$+[{x}+p/m]+...$
$+[{x}+(m-1)/m]$
$=m[x]+1+1+1+...(m-p)$ times
$=m[x]+m-p$
Now, since,
$[{x}+p/m]=1$
Implies that
$[{x}+(p/m)-1]=0$
$[{x}-((m-p)/m)]0$
Which in turn implies that
${x}=(m-p)/m+(<1/m)$ for $p$ to be minimum
$m{x}=m-p+(<1)$
$[m{x}]=m-p$ …. (2)

Therefore, by (2) we get

$RHS=m[x]+[m{x}]$
$=[m[x]]+[m{x}]$
$=[m[x]+m{x}]$
$=[mx]$
Hence, we have prove (1)

## Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.19

19. Show that $[\sqrt{[x]}]=[\sqrt{x}]$ whenever $x$ is a nonnegative real number.
Solution:  We have to prove the equation
$[\sqrt{[x]}]=[\sqrt{x}]$
Whenever $x$ is a non-negative real number
We assume that
$x=k+\epsilon$
Where $k$ is an integer and
$0<=\epsilon<1$
Further, we assume that
$k=a^2+b$
Where a is the largest integer such that
$a^2<=k$
Now,
$a^2<=k$
$=a^2+b$
$<=x$
$=a^2+b+\epsilon$
$a^2<(a+1)^2$
This implies that
$[\sqrt{x}] = a$
And
$[\sqrt{[x]}]=[\sqrt{k}]$
$=a$
Hence we have achieved the equality in the equation
$[\sqrt{[x]}]=[\sqrt{x}]$