Exercise (3.1).15

Show that $2^m \not \equiv 0 \pmod {10}$ where $m$ is a natural number.

What does this mean in relation to digits of $2^m$?

Hint: Write $m = 4q + r$ where $0 ≤ r < 4$.

We start with the Division Algorithm to write $m = 4q + r$ where $0 \le r < 4$. 

And so

$$ \begin{align} 2^m & = 2^{4q+r} \\ \\ & = (2^4)^q \times 2^r  \\ \\ & \equiv 6^q \times 2^r \pmod {10} \\ \\ & \equiv 6 \times 2^r \pmod {10} \end{align} $$

The last line uses the previously proven result that $6^q \equiv 6 \pmod{10}$.

We have four cases for $r$. Let's consider each in turn:

$r=0$ means $6 \times 2^r \equiv 6 \times 1 \equiv 6 \pmod{10}$.

$r=1$ means $6 \times 2^r \equiv 6 \times 2 \equiv 2 \pmod{10}$.

$r=2$ means $6 \times 2^r \equiv 6 \times 4 \equiv 4 \pmod{10}$.

$r=3$ means $6 \times 2^r \equiv 6 \times 8 \equiv 8 \pmod{10}$.

In all cases $2^m \not \equiv 0 \pmod{10}$. The means that the last digit of $2^m$ is never 0.

Exercise (3.1).14

Let $n$ be a natural number. Prove that $6^n ≡ 6 \pmod {10}$. 

What conclusion can you draw about the last digit of powers of 6?

We'll prove this by induction.

Let the statement $P(n)$ mean that $6^n \equiv 6 \pmod {10}$.

We need to prove the base case $P(1)$, and the inductive step $P(n) \implies P(n+1)$.

Base Case

The base case $P(1)$ is that $6^1 \equiv 6 \pmod {10}$. This is trivially true.

Induction Step

We assume $P(n)$ and aim to show $P(n+1)$.

$P(n+1)$ is

$$ \begin{align} 6^{n+1} & \equiv 6^n \times 6 \pmod{10} \\ \\ & \equiv 6 \times 6 \pmod {10} \tag{*} \\ \\ & \equiv 36 \pmod {10} \\ \\ & \equiv 6 \pmod {10}  \end{align}$$

Line (*) uses the induction hypothesis that $6^n \equiv 6 \pmod {10}$.

We have shown that $P(n) \implies P(n+1)$.

We have shown, by induction, that $6^n \equiv 6 \pmod {10}$. We conclude that the last digit of powers of 6 is always 6.

Exercise (3.1).13

Let $p$ be prime of the form $p ≡ 3 \pmod 4$. Show that $p$ cannot be written as the sum of two squares.

[Hint: Use the result of question 12 (b).]

We have shown that a square can only be 0 or 1 modulo 4.

So the sum of two squares can only be 0, 1 or 2 modulo 4, by Proposition (3.6).

And so any number congruent to 3 modulo 4 cannot be the sum of two squares.

Note $p$ doesn't need to be a prime, the result holds for any number congruent to 3 modulo 4.

Exercise (3.1).12

(a) Show that a square number $a^2$ divided by 3 gives only remainders 0 or 1.

(b) Show that a square number $a^2$ divided by 4 gives only remainders 0 or 1.

(a) We start by noting that a number $a$ is congruent to 0, 1 or 2 modulo 3.

Using Proposition (3.8) we have, for each of these cases

$$ a \equiv 0 \pmod 3 \implies a^2 \equiv 0^2 \equiv 0 \pmod 3 $$

$$ a \equiv 1 \pmod 3 \implies a^2 \equiv 1^2 \equiv 1 \pmod 3 $$

$$ a \equiv 2 \pmod 3 \implies a^2 \equiv 2^2 \equiv 1 \pmod 3 $$

And so $a^2$ divided by 3 only gives remainders 0 or 1.

(b) We start by noting that a number $a$ is congruent to 0, 1, 2 or 3 modulo 4.

Using Proposition (3.8) we have, for each of these cases

$$ a \equiv 0 \pmod 4 \implies a^2 \equiv 0^2 \equiv 0 \pmod 4 $$

$$ a \equiv 1 \pmod 4 \implies a^2 \equiv 1^2 \equiv 1 \pmod 4 $$

$$ a \equiv 2 \pmod 4 \implies a^2 \equiv 2^2 \equiv 0 \pmod 4 $$

$$ a \equiv 3 \pmod 4 \implies a^2 \equiv 3^2 \equiv 1 \pmod 4 $$

And so $a^2$ divided by 4 only gives remainders 0 or 1.

Exercise (3.1).11

(a) Show that if $a$ is an even number and $n$ is a natural number then $a^n$ is also even.

(b) Show that if $a$ is an odd number and $n$ is a natural number then $a^n$ is also odd.

We'll be using Proposition (3.8) that

$$a \equiv b \pmod m \implies a^k \equiv b^k \pmod m$$

(a) If a number is congruent to 0 modulo 2 then it is even.

Using Proposition (3.8),

$$ a \equiv 0 \pmod{2} \implies a^n \equiv 0^n  \equiv 0 \pmod{n}$$

That is, $a^n$ is even. 

Note that $n$ must be greater than 0.

(b) If a number is congruent to 1 modulo 2 then it is odd.

Using Proposition (3.8),

$$ a \equiv 1 \pmod{2} \implies a^n \equiv 1^n  \equiv 1 \pmod{n}$$

That is, $a^n$ is odd. 

Exercise (3.1).10

Find the last two digits of $2014^{2014}$.

(This number has 6655 digits.)

The last two digits are the least non-negative residue modulo 100.

We have $2014 \equiv 14 \pmod{100}$, and $14^2 = 196 \equiv -4 \pmod{100}$.

By Proposition (3.8) we have

$$ \begin{align} 2014^{2014} & \equiv (14)^{2014} \pmod{100} \\ \\ & \equiv (14)^{2 \times 19 \times 53} \pmod{100} \\ \\  & \equiv  (14^2)^{19 \times 53} \pmod{100} \\ \\ & \equiv (-4)^{19 \times 53} \pmod{100}  \end{align} $$

Now, $19 \times 53$ can't be decomposed further, so we'll resort to the division algorithm.

$$ 19 \times 53 = 1007 =  (10 \times 100) + 7$$

And so, 

$$ \begin{align} 2014^{2014} & \equiv (-4)^{(10 \times 100) + 7} \pmod{100}  \\ \\  & \equiv (-4)^{10 \times 100} \times (-4)^7 \pmod{100} \\ \\ & \equiv ((-4)^{10})^{100} \times (-4)^7 \pmod{100} \end{align} $$

It is now feasible to calculate

$$ (-4)^{10} \equiv -1048576  \equiv 24 \pmod {100} $$

$$ (-4)^7  \equiv -16384  \equiv 16 \pmod {100} $$

And so,

$$ \begin{align} 2014^{2014} & \equiv (24)^{100} \times 16 \pmod{100} \end{align} $$

We can repeat this process using $24^{100} =  (24^{10})^{10}  = (6^{10} \times 4^{10})^{10}  \equiv (76 \times  76)^{10} \equiv 76^{10} \pmod{100}$

$$ \begin{align} 2014^{2014} & \equiv (24^{10})^{10} \times 16 \pmod{100} \\ \\  & \equiv (76)^{10} \times 16 \pmod{100}  \end{align} $$

Similarly $76^{10} = 4^{10} \times 19^{10} \equiv 76 \times 1 \pmod {100}$, and so

$$ \begin{align} 2014^{2014} & \equiv76 \times 1 \times 16 \pmod{100} \\ \\  & \equiv 1216 \pmod{100}  \\ \\ & \equiv 16 \pmod{100} \end{align} $$

And so the last two digits of $2014^{2014}$ are 16.

Exercise (3.1).9

Determine the last digit of the following numbers:

(a) $3^{100}$ (b) $9^{100}$

(c) $2^{100}$ (d) $4^{100}$

The last digit of a number is congruent to the number modulo 10. 

We also use Proposition (3.8). 

If $a ≡ b \pmod {n}$ then $a^k ≡ b^k \pmod{n}$ where $k$ is a natural number.

(a) We have $3^2 = 9 \equiv -1 \pmod{10}$.

And so

 $$ \begin{align} 3^{100} & = (3^2)^{50} = (9)^{50} \\ \\ & \equiv (-1)^{50} \pmod{10} \\ \\ & \equiv 1 \pmod{10} \end{align} $$

So the last digit is 1.

(b) We have $9^2 = 81 \equiv 1 \pmod{10}$.

And so

 $$ \begin{align} 9^{100} & = (9^2)^{50} = (81)^{50} \\ \\ & \equiv (1)^{50} \pmod{10} \\ \\ & \equiv 1 \pmod{10} \end{align} $$

So the last digit is 1.

(c) We have $2^5 = 32 \equiv 2 \pmod{10}$.

And so

 $$ \begin{align} 2^{100} & = (2^5)^{20} = (32)^{20} \\ \\ & \equiv (2)^{20} \pmod{10} \\ \\ & \equiv (2^5)^4 \pmod{10} \\ \\ & \equiv (2)^4 \pmod{10} \\ \\ & \equiv 16 \pmod{10} \\ \\ & \equiv 6 \pmod{10} \end{align} $$

So the last digit is 6.

(d) We already have $2^{100} \equiv 6 \pmod{10}$.

And so

 $$ \begin{align} 4^{100} & = (2^2)^{100} \\ \\ & = (2^{100})^2 \\ \\ & \equiv 6^2 \pmod{10} \\ \\ & \equiv 36 \pmod {10} \\ \\ & \equiv 6 \pmod{10} \end{align} $$

So the last digit is 6.