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.

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:

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