Exercise (1.3).2

Find a particular integer solution to the linear equations:

(a) $156x + 18y= \gcd (156, 18)$

(b) $129x + 1011y= \gcd (129, 1011)$

(c) 703x + 111y= \gcd (703, 111)$

(d) $181x + 232y= \gcd (181, 232)$

We first notice the coefficients of these equations are the values from the previous exercise. We can therefore re-use the working there to develop solutions here.

(a) Applying the Division Algorithm to 156 and 18 gives

$ 156 = 8 (18) + 12 $

$ 18 =  1(12) + 6  = 1(12) + \gcd(156,18)$

Re-arranging,

$ 18 - 1(12) = \gcd(156,18) $

$ 18 - (156-8(18)) = \gcd(156,18) $

$ (9)(18) + (-1)156 = \gcd(156,18)$

So, a particular solution is $x=-1, y=9$.

(b) Applying the Division Algorithm to 1011 and 129 gives

$ 1011 = 7(129) + 108 $

$ 129 = 1(108) + 21 $

$ 108 = 5(21) + 3 = 5(21) + \gcd(1011,129) $

Re-arranging,

$  108 - 5(21) = \gcd(1011,129)  $

$  108 - 5(129-1(108)) = \gcd(1011,129)  $

$  (6)108 - 5(129) = \gcd(1011,129)  $

$  (6)(1011-7(129)) - 5(129) = \gcd(1011,129)  $

$  (6)(1011) - 47(129) = \gcd(1011,129)  $

So, a particular solution is $x=-47, y=6$.

(c) We apply the Division Algorithm to 703 and 111.

$ 703 =  6(111) + 37 = 6(11) + \gcd(703,111)$

Re-arranging,

$ 703 - 6(111) - \gcd(703,111) $ 

So, a particular solution is $x=1, y=-6$.

(d) We apply the Division Algorithm to 232 and 181.

$ 232 = 1(181) + 51 $

$ 181 = 3(51) + 28 $

$ 51 = 1(28) + 23 $

$ 28 = 1(23) + 5 $

$ 23 = 4(5) + 3 $

$ 5 = 1(3) + 2 $

$ 3 = 1(2) + 1 = 1(2) + \gcd(232,181)$

Re-arranging

$ \gcd(232,181) =  3 - 1(2) $

$ \gcd(232,181) =  3 - (5-3) $

$ \gcd(232,181) =  2(3) - (5)  $

$ \gcd(232,181) =  2(23-4(5)) - (5)  = 2(23) - 9(5) $

$ \gcd(232,181) =  2(23) - 9(28-23) = 11(23) - 9(28) $

$ \gcd(232,181) =  11(51-28) - 9(28)  = 11(51) - 20(28)$

$ \gcd(232,181) =  11(51) - 20(181-3(51)) = 71(51) -20(181)$

$ \gcd(232,181) =  71(232-181) -20(181) = 71(232) -91(181) $

So, a particular solution is $x=-91, y=71$.

Exercise (1.3).1

By using the Euclidean Algorithm determine:

(a) $\gcd (156, 18)$

(b) $\gcd (129, 1011)$

(c) $\gcd (703, 111)$

(d) $\gcd (181, 232)$

(a) Applying the Division Algorithm to 156 and 18 gives

$$ 156 = 8 (18) + 12 $$

We apply the Division Algorithm to 18 and the non-zero remainder 12.

$$ 18 =  1(12) + 6 $$

We apply the Division Algorithm to 12 and the non-zero remainder 6.

$$ 12 =  2(6) + 0 $$

The algorithm terminates. The last non-zero remainder is 6, so $\gcd(156,18)=6$.

(b) Applying the Division Algorithm to 1011 and 129 gives

$$ 1011 = 7(129) + 108 $$

We apply the Division Algorithm to 129 and 108.

$$ 129 = 1(108) + 21 $$

We apply the Division Algorithm to 108 and 21.

$$ 108 = 5(21) + 3 $$

We apply the Division Algorithm to 21 and 3.

$$ 21 = 7(3) + 0 $$

The last non-zero remainder is 3, so $\gcd(1011,129) = 3$

(c) We apply the Division Algorithm to 703 and 111.

$$ 703 =  6(111) + 37$$

$$ 111 = 3(37) + 0 $$

So $\gcd(703,111) = 37$

(d) We apply the Division Algorithm to 232 and 181.

$$ 232 = 1(181) + 51 $$

$$ 181 = 3(51) + 28 $$

$$ 51 = 1(28) + 23 $$

$$ 28 = 1(23) + 5 $$

$$ 23 = 4(5) + 3 $$

$$ 5 = 1(3) + 2 $$

$$ 3 = 1(2) + 1 $$

$$ 2 = 1(2) + 0 $$

So $\gcd(232,181) = 1$. They are coprime.

Exercise (1.2).7

Prove Corollary (1.8).

Corollary (1.8). Given any integers $a$ and $b$ with $b ≠ 0$, there exist unique integers $q$ and $r$ such that

$$a = bq + r \quad \text{where} \quad  0 \le r <  \lvert b \rvert $$

The Division Algorithm (1.7). Given any integers $a$ and $b$ where $b ≥ 1$, then there exist unique integers $q$ called the quotient and $r$ called the remainder such that

$$a = bq + r \quad \text{where} \quad 0 ≤ r < b$$

To prove Corollary 1.8, we will show it follows from the Division Algorithm 1.7.

Given $b \ne 0$, there are two cases to consider, $b>0$ and $b<0$.

Case $b>0$

The Division Algorithm requires $b \ge 1$, which is equivalent to $b>0$.

The Division Algorithm then asserts there exist unique integers $q$ and $r$ such that 

$$a = bq + r \quad \text{where} \quad 0 ≤ r < b$$

This is equivalent to the Corollary because $b = \lvert b \rvert$.

So for the case $b>0$, the Corollary is equivalent to the Division Algorithm.

Case $b<0$

We'll apply the Division Algorithm to $a$ and $\lvert b \rvert$. It then says that given any integers $a$ and $ \lvert b \rvert$ where $\lvert b \rvert ≥ 1$, then there exist unique integers $q$ and $r$ such that

$$a = \lvert b \rvert q + r \quad \text{where} \quad 0 ≤ r < \lvert b \rvert$$

Since $b<0$, 

$$ \lvert b \rvert q = (-b)q = b(-q)$$

So we have

$$a =b (-q) + r \quad \text{where} \quad 0 ≤ r < \lvert b \rvert$$

This is Corollary 1.8 but with the unique integer $(-q)$ as quotient.

We have shown Corollary 1.8 follows from Division Algorithm 1.7 by showing it for both cases $b>0$ and $b<0$.

Exercise (1.2).6

Prove that for any integer $a$ we have $11 \mid (a^{11}− a)$.

We first recognise that $(a^{11}-a) = a(a^{10}-1)$.

Well consider two cases, $\gcd(a,11)=1$ and $\gcd(a,11) \ne 1$. 

Case $\gcd(a,11)=1$ for $(a^{10}-1)$

Well use the Division Algorithm: for integers $a$ and $b \ge 1$ there exist integers $q$ and $r$ such that $a = bq + r$ where $0 ≤ r < b$.

Choosing $b=11$, then $0 \le r < 11$, and

$$\begin{gather*} a^{10}-1 =  11 q (2357947691 q^9 + 2143588810 q^8 r + \\ 876922695 q^7 r^2 + 212587320 q^6 r^3 + 33820710 q^5 r^4 + 3689532 q^4 r^5 + \\ 279510 q^3 r^6 + 14520 q^2 r^7 + 495 q r^8 + 10 r^9) + r^{10} - 1\end{gather*}$$

The first part is divisible by 11, so we focus on $r^10 -1$.

Since $\gcd(a,11)=1$ we have $r \ne 0$. This means $r$ can be 1,2,3,4,5,6,7,8,9,10,

$r=1$ means $r^10-1=0$, which is divisible by 11.

$r=2$ means $r^10-1=1023$, which is divisible by 1.

$r=3$ means $r^10-1=59048$, which is divisible by 11.

$r=4$ means $r^10 -1 = 1048575$, which is divisible by 11.

$r=5$ means $r^10-1 = 9765624$, which is divisible by 11.

$r=6$ means $r^10-1 = 60466175$, which is divisible by 11.

$r=7$ means $r^10-1 = 282475248$, which is divisible by 11.

$r=8$ means $r^10-1 = 1073741823$, which is divisible by 11.

$r=9$ means $r^10-1 = 3486784400$, which is divisible by 11.

$r=10$ means $r^10-1 = 9999999999$, which is divisible by 11.

So, for $\gcd(a,11)=1$ we have $11 \mid (a^{10}-1)$.

Case $\gcd(a,11)\ne 1$ for $a$

Because 11 only has two factors, 1 and 11, and 1 is excluded in this case, we're left with only $\gcd(a,11)=11$. This tells us $11\mid a$.

The two cases combined tell us that for any integer $a$ we have $11 \mid (a^{11}− a)$.

Exercise (1.2).5

(i) Prove that $7 \mid (a^6 − 1)$ for any integer $a$ such that $\gcd (a, 7) = 1$.

(ii) Prove that for any integer $a$ we have $7 \mid (a^7− a)$.

(i) We'll use the Division Algorithm:

For integers $a$ and $b \ge 1$ there exist integers $q$ and $r$ such that $a = bq + r$ where $0 ≤ r < b$.

Choosing $b=7$, then $0 \le r < 7$, and

$$\begin{align} a^6 -1 &= (7q + r)^6 -1 = 117649 q^6 + 100842 q^5 r + 36015 q^4 r^2 + 6860 q^3 r^3 + 735 q^2 r^4 + 42 q r^5 + r^6 - 1 \\ \\ & = 7 q (16807 q^5 + 14406 q^4 r + 5145 q^3 r^2 + 980 q^2 r^3 + 105 q r^4 + 6 r^5) + r^6 -1 \end{align}$$

The first part of this expression is divisible by 7, so we focus on the remaining $r^6 -1$.

The integer $r$ can take values 0,1,2,3,4,5,6. However, we are given $\gcd(a,7)=1$ which means $r=0$ is ruled out. To see this more clearly, $\gcd (a = 7q+0,7) = 7$.

• $r=1$ means $r^6-1=0$, which is divisible by 7.
• $r=2$ means $r^6-1=63$, which is divisible by 7.
• $r=3$ means $r^6-1=728$, which is divisible by 7.
• $r=4$ means $r^6-1=4095$, which is divisible by 7.
• $r=5$ means $r^6-1=15624$, which is divisible by 7.
• $r=6$ means $r^6-1=46655$, which is divisible by 7.

And so $7 \mid (a^6 − 1)$ for any integer $a$ such that $\gcd (a, 7) = 1$

(ii) Let's consider $(a^7-a)$

$$ (a^7 -a) = a(a^6-1) $$

We have already shown that $7 \mid (a^6 - 1)$ for $\gcd(a,7)=1$, so for $\gcd(a,7)=1$

$$7 \mid (a^7 -a)$$

We now need to consider the case when $\gcd(a,7) \neq 1$. The only other option for $\gcd(a,7)$ is 7, which means $a$ is a multiple of 7. That is $7 \mid a$. So in this case too, $7 \mid (a^6 - 1)$.

For both cases $\gcd(a,7)=1$ and $\gcd(a,7) \neq 7$, we have shown 7 divides $(a^7-a)$.

Exercise (1.2).4

Prove that for any integer $a$ we have $6 \mid (a^3 + 5a)$.

We'll use the Division Algorithm which guarantees that given integers $a$ and (divisor) $b \geq 1$, there exists unique integers quotient $q$ and remainder $r$ such that $a$ can be written as

$$a = qb + r  \quad \text{where} \quad 0 \le r < b$$

If we choose $b=6$, then $0 \le r < 6$, and we have

$$ a^3 + 5a = 216 q^3 + 108 q^2 r + 18 q r^2 + 30 q + r^3 + 5 r$$

The integer $r$ can only be 0,1,2,3,4,5. Let's consider each case:

• $r=0$ means $ a^3 + 5a = 216 q^3  + 30 q = 6(36 q^3 + 5q)$, divisible by 6.
• $r=1$ means $ a^3 + 5a = 216 q^3 + 108 q^2 + 18 q + 30 q + 6 = 6(36 q^3 + 18q^2 + 8q + 1)$, divisible by 6.
• $r=2$ means $ a^3 + 5a = 216 q^3 + 216 q^2  + 102 q  + 18 = 6(36q^3 + 36q^2 + 17q+3)$, divisible by 6.
• $r=3$ means $a^3 + 5a = 6 (36 q^3 + 54 q^2 + 32 q + 7)$, divisible by 6.
• $r = 4$ means $a^3 + 5a = 6 (36 q^3 + 72 q^2 + 53 q + 14)$, divisible by 6.
• $r = 5$ means $a^3 + 5a = 6 (36 q^3 + 90 q^2 + 80 q + 25)$, divisible by 6.

So, for any integer $a$ we have $6 \mid (a^3 + 5a)$.

Exercise (1.2).3

Prove by using the Division Algorithm that the fourth power of any integer is of the form $8k$ or $8k + 1$.

We'll use the Division Algorithm which guarantees that given integers $a$ and (divisor) $b \geq 1$, there exists unique integers quotient $q$ and remainder $r$ such that $a$ can be written as

$$a = qb + r  \quad \text{where} \quad 0 \le r < b$$

If we choose $b=8$, then $0 \le r < 8$, and we have

$$\begin{align} a^4 &= 4096 q^4 + 2048 q^3 r + 384 q^2 r^2 + 32 q r^3 + r^4 \\ \\ &= 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + r^4 \end{align}$$

The integer $r$ can only be $0, 1, 2, 3, 4, 5, 6, 7$. Let's consider each case:

• $r=0$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3)$, of the form $8k$.
• $r=1$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 1$, of the form $8k + 1$.
• $r=2$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 16 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 2) $, of the form $8k$.
• $r=3$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 81 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 10) + 1$, of the form $8k + 1$.
• $r=4$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 256 =  8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 32)$, of the form $8k$.
• $r=5$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 625 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 78) +1 $, of the form $8k+1$.
• $r=6$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 1296 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 162)$, of the form $8k$.
• $r=7$ means $a^4 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3) + 2401 = 8 (512 q^4 + 256 q^3 r + 48 q^2 r^2 + 4 q r^3 + 300) + 1$, of the form $8k+1$.

So the fourth power of any integer is of the form $8k$ or $4k+1$ for some integer $k$.