Elementary Number Theory Problems 4.2 Solution (David M. Burton's 7th Edition)

Background

These are my solutions while I was studying number theory using this book. I will use the theorems and definitions mentioned in the book.

If you don't have the book or are unsure which theorem or definition I am using here, you can check out this article, where I listed all theorems, corollaries, and definitions by following the book's order.

Theorems and Corollaries in Elementary Number Theory

All theorems and corollaries mentioned in David M. Burton’s Elementary Number Theory are listed by following the book’s order. (7th Edition) (Currently Ch 1 - 4)

RanblogRan

If you haven't heard of this book and are interested in learning number theory, I strongly recommend it since it is quite friendly for beginners. You can check out the book by this link:

Elementary Number Theory (Paperback)

Get it now:

I will only use theorems or facts that are proved before this chapter. So, you will not see that I quote theorems or facts from the later chapters.

All Problems in 4.2 (p. 67 - p. 68)

Q1

Prove each of the following assertions:
(a) If $a \equiv b \pmod n$ and $m \mid n$, then $a \equiv b \pmod m$.
(b) If $a \equiv b \pmod n$ and $c > 0$, then $ca \equiv cb \pmod {cn}$.
(c) If $a \equiv b \pmod n$ and the integers $a$, $b$, $n$ are all divisible by $d > 0$, then $a/d \equiv b/d \pmod {n/d}$.

Solution

Q2

(a) If $1$ is added to a product of twin primes, prove that a perfect square is always obtained.
(b) Show that the sum of twin primes $p$ and $p + 2$ is divisible by $12$, provided that $p > 3$.

Solution

Q3

If $a \equiv b \pmod n$, prove that $gcd(a, n) = gcd(b, n)$.

Solution

Q4

(a) Find the remainders when $2^{50}$ and $41^{65}$ are divided by $7$.
(b) What is the remainder when the following sum is divided by $4$? $$1^5 + 2^5 + 3^5 + \cdots + 99^5 + 100^5$$

Solution

Q5

Prove that the integer $53^{103} + 103^{53}$ is divisible by $39$, and that $111^{333}$ + $333^{111}$ is divisible by $7$.

Solution

Q6

For $n \geq 1$, use congruence theory to establish each of the following divisibility statements:
(a) $7 \mid 5^{2n} + 3 \cdot 2^{5n-2}$.
(b) $13 \mid 3^{n+2} + 4^{2n+1} $.
(c) $27 \mid 2^{5n+1} + 5^{n+2}$.
(d) $43 \mid 6^{n+2} + 7^{2n+1}$.

Solution

Q7

For $n \geq 1$, show that $$(-13)^{n + 1} \equiv (-13)^{n} + (-13) ^{n - 1} \pmod {181}$$
[Hint: Notice that $(-13)^{2} \equiv -13 + 1 \pmod {181}$; use induction on $n$.]

Solution

Q8

Prove the assertions below:
(a) If $a$ is an odd integer, then $a^{2} \equiv 1 \pmod 8$.
(b) For any integer $a$, $a^{3} \equiv 0, 1,$ or $6 \pmod 7$.
(c) For any integer $a$, $a^{4} \equiv 0$ or $1 \pmod 5$.
(d) If the integer $a$ is not divisible by $2$ or $3$, then $a^{2} \equiv 1 \pmod {24}$.

Solution

Q9

If $p$ is a prime satisfying $n < p < 2n$, show that $${2n \choose n} \equiv 0 \pmod p$$

Solution

Q10

If $a_{1}, a_{2}, ..., a_{n}$ is a complete set of residues modulo $n$ and $gcd(a, n) = 1$, prove that $aa_{1}, aa_{2}, ... , aa_{n}$ is also a complete set of residues modulo $n$.
[Hint: It suffices to show that the numbers in question are incongruent modulo $n$.]

Solution

Q11

Verify that $0, 1, 2, 2^{2}, 2^{3}, ..., 2^{9}$ form a complete set of residues modulo $11$, but that $0, 1^{2} , 2^{2} , 3^{2} , ... , 10^{2}$ do not.

Solution

Q12

Prove the following statements:
(a) If $gcd(a, n) = 1$, then the integers $$c, c + a, c + 2a, c + 3a, ... , c + (n - 1)a$$ form a complete set of residues modulo $n$ for any $c$.
(b) Any $n$ consecutive integers form a complete set of residues modulo $n$.
[Hint: Use part (a).]
(c) The product of any set of $n$ consecutive integers is divisible by $n$.

Solution

Q13

Verify that if $a \equiv b \pmod {n_{1}}$ and $a \equiv b \pmod {n_{2}}$, then $a \equiv b \pmod {n}$, where the integer $n = lcm(n_{1}, n_{2})$. Hence, whenever $n_{1}$ and $n_{2}$ are relatively prime, $a \equiv b \pmod{n_{1}n_{2}}$.

Solution

Q14

Give an example to show that $a^{k} \equiv b^{k} \pmod {n}$ and $k \equiv j \pmod {n}$ need not imply that $a^{j} \equiv b^{j} \pmod {n}$.

Solution

Q15

Establish that if $a$ is an odd integer, then for any $n \geq 1$$$a^{2^{n}} \equiv 1 \pmod {2^{n + 2}}$$
[Hint: Proceed by induction on $n$.]

Solution

Q16

Use the theory of congruences to verify that $$89 \mid 2^{44} - 1 \qquad \text{and} \qquad 97 \mid 2 ^{48} - 1$$

Solution

Q17

Prove that whenever $ab \equiv cd \pmod {n}$ and $b \equiv d \pmod {n}$, with $gcd(b, n) = 1$, then $a \equiv c \pmod {n}$.

Solution

Q18

If $a \equiv b \pmod {n_{1}}$ and $a \equiv c \pmod {n_{2}}$, prove that $b \equiv c \pmod {n}$, where the integer $n = gcd(n_{1}, n_{2})$.

Solution