Exercise (2.2).14

(i) Show that for real $x ≥ 0$ the following is false: $√⌊x⌋ = ⌊√x⌋$.

(ii) Prove that for real $x ≥ 0$ we have $⌊√⌊x⌋⌋ = ⌊√x⌋$.

(i) We show this with a counter-example.

We choose $x=2$,

$\sqrt{\lfloor 2 \rfloor} = \sqrt{2} = 1.4142 \ldots$

$\lfloor \sqrt{2} \rfloor = \lfloor 1.4142 \ldots \rfloor = 1$

So $x=2$ shows that $\sqrt{\lfloor x \rfloor} = \lfloor \sqrt{x} \rfloor$ is not always true.

(ii) If $d$ is an integer such that 

$$ d \le \sqrt{x} < d + 1 $$

then $d = \lfloor \sqrt{x} \rfloor$, by definition of the floor function.

Since squaring positive real numbers is monotonically increasing, we can square over this inequality

$$ d^2 \le x < (d + 1)^2 $$

Since $d^2$ is an integer, we can say

$$d^2 \le \lfloor x \rfloor \tag{i}$$

Also, since $\lfloor x \rfloor \le x$ and $x < (d + 1)^2$ we have 

$$ \lfloor x \rfloor <  (d+1)^2 \tag{ii}$$

Combining (i) and (ii)

$$d^2 \le \lfloor x \rfloor <  (d+1)^2 $$

We can take the square root since it is a monotonically increasing function

$$d \le \sqrt{\lfloor x \rfloor} <  d+1 $$

This is means $d = \lfloor \sqrt{\lfloor x \rfloor} \rfloor$.

So $d = \lfloor \sqrt{x} \rfloor$, and $d = \lfloor \sqrt{\lfloor x \rfloor} \rfloor$, which means we have shown

$$ \lfloor \sqrt{\lfloor x \rfloor} \rfloor =  \lfloor \sqrt{x} \rfloor$$

Exercise (2.2).13

(a) Given that $N ≥ 1$ is a natural number, prove that $⌊\log_{10} (N)⌋ + 1$ gives the number of digits of $N$.

(b) Determine the number of digits of Googol= $10^{100}$.

(c) The googolplex is the number given by $10^{(10^{100})}$. Find the number of digits of this googolplex.

(d) (i) Find the number of digits of $2^{74 207 211}$. 

[Hint: Change of the base for logs is given by the formula $log_b (a)  = \frac{log_c (a)}{\log_c (b)}$ .]

(ii) What is the number of digits of $2^{74 207 211}$ if we work with number base 2?

(a) As the natural number $N$ increases, the number of digits $d$ increments as $N$ grows from 9 to 10, then 99 to 100,  then 999 to 1000.

So, for a number $N$ to have $d$ digits, the following must hold

$$ 10^{d-1} < N < 10^d  $$

For example, 5 has 1 digits 

$ 10^{1-1} = 1 < 5 < 10 = 10^1 $

Another example, 999 has 3 digits

$ 10^{3-1} = 100 < 999 < 1000 = 10^3$

The inequality gives us

$$ (d-1) < \log_{10} N < d $$

So $d-1$ is the largest integer less than $\log_{10} N$, which is the definition of the floor function,

$$ d -1  = \lfloor \log_{10} N \rfloor  $$

That is, the number of digits $d$ of $N$ is

$$ d = \lfloor \log_{10} N \rfloor + 1 $$

(b) We apply the formula

$$  \lfloor \log_{10} (10^{100}) \rfloor + 1 = 100 + 1 = 101 $$

So googol has 101 digits. That is, 1 followed by 100 zeroes.

(c) We apply the formula

$$  \lfloor \log_{10} (10^{10^{100}}) \rfloor + 1 = 10^{100} + 1$$

So googolplex has $10^{100}+1$ digits. That's 1 then 99 zeroes then 1.

(d) (i) We apply the formula 

$$ \begin{align} d & = \lfloor \log_{10} 2^{74 207 211} \rfloor + 1 \\ \\ & = \lfloor \frac{\log_2 2^{74 207 211}}{\log_2 10} \rfloor + 1 \\ \\ & = \lfloor \frac{74 207 211}{\log_2 10} \rfloor + 1  \\ \\ & = 22338597 \end{align}$$

The number of digits of $2^{74 207 211}$ is 22338597.

(ii) The equivalent formula for the number of digits, derived by the same rationale as above, is

$$ d = \lfloor \log_{2} N \rfloor + 1 $$

We apply the formula

$$ \begin{align} d & = \lfloor \log_{2} 2^{74 207 211} \rfloor + 1 \\ \\ & = \lfloor 74 207 211 \rfloor + 1 \\ \\  &= 74 207 212  \end{align}$$

The number of digits of $2^{74 207 211]$ in binary form (base 2) is 74 207 212.

Exercise (2.2).12

Without using a calculator or computer system, determine the following (you will need to know some properties of logs to answer this question):

(a) $⌈\log_{10} (101)⌉$

(b) $⌊\log_2 (63)⌋$

(c) $⌊\log_n (n^x)⌋$ where $n$ is a natural number and $n− 1 < x < n$.

(a) We first recognise

$$ 100 = 10^2 < 10^3 = 1000 $$

$$ \log_{10} 100 = 2 < 3 = \log_{10} 1000 $$

We used the fact that a logarithm is monotonically increasing. This also means

$$ \log_{10} 100 = 2 < \textcolor{red}{ \log_{10} 101} < 3 = \log_{10} 1000 $$

And so

$$ \lceil  \log_{10} 101 \rceil = 3  $$

because 3 is the smallest integer larger than $ \log_{10} 101$.

(b) We first recognise

$$ 32 = 2^5 < 2^6 = 64$$

$$ \log_2 32 = 5 < 6 = \log_2 64$$

Again, we used the fact that a logarithm is monodically increasing.  This also means

$$ \log_2 32 = 5 <  \textcolor{red}{ \log_2 63} < 6  = \log_2 64$$

And so

$$ \lfloor \log_2 63 \rfloor = 5 $$

because 5 is the largest integer smaller than $\log_2 63$.

(c) We are given $n− 1 < x < n$, where $n$ is a natural number, and so

$$ n^{n-1} < n^x < n^n $$

Since logarithms are monotonically increasing,

$$ \log_n n^{n-1} < \log_n n^x < \log_n n^n $$

Simplifying

$$ n-1 < \log_n n^x < n $$

And so

$$ \lfloor \log_n n^x \rfloor = n-1 $$

because $n-1$ is the largest integer smaller than $\log_n n^x$.

Exercise (2.2).11

Prove that $2^{3^n}+ 1$ is composite for all natural numbers $n$.

[Hint: $x^m + 1 = (x + 1) (x^{m−1}− x^{m−2} + x^{m−3} − ⋯ + x^2− x + 1)$ , provided $m$ is odd.]

We can take $m=3^n$ as odd because $m$ only has prime factors 3, and not 2, so is not even.

This means we can use the given factorisation as

$$ 2^{3^n} + 1 = (2+1)( 2^{3^n-1}  - 2^{3^n-2} + 2^{3^n-3} - \ldots + 2^2 -2 + 1) $$

The RHS is a product of two integers, and so $2^{3^n}+ 1$ is composite for all natural numbers $n$.

Update: the textbook author's solution requires us to check that $2^{3^n}+ 1$ is greater than one. This is because the book defines a composite as greater than 1. We can see this is the case because $3^n \ge 1$ for natural numbers $n$ (including $n=0$), and so $2^{3^n} + 1 \ge 2^1+1= 3$. 

Exercise (2.2).10

Show that $(2 × 3 × 5 × 7 × 11 × 13) + 1$ is composite.

 $(2 × 3 × 5 × 7 × 11 × 13) + 1 = 30031$. We only need to test for prime factors less than or equal to $\lfloor \sqrt{30031} \rfloor = 173$. 

The form  $(2 × 3 × 5 × 7 × 11 × 13) + 1$ means it has no prime factors 2,3,5,7,11,13, so these don't need to be tested.

This gives us

$ 30031 = 59 \times 509 $

Exercise (2.2).9

Test the following numbers for compositeness. If they are composite, give their prime decomposition:

(a) $(2 × 3 × 5 × 7) − 1$

(b) $(2 × 3 × 5 × 7) + 1$

(a) $(2 × 3 × 5 × 7) − 1 = 209$. We only need to test prime factors less than or equal to $\lfloor \sqrt{209} \rfloor = 14$.  However, the form $(2 × 3 × 5 × 7) − 1$ tells us that 2,3,5 and 7 are not prime factors. So we only need to test 11 and 13.

This gives us

$ 209 = 11 \times 19 $

(b) $(2 × 3 × 5 × 7) + 1 = 211$. We only need to test prime factors less than or equal to $\lfloor \sqrt{211} \rfloor = 14$.  However, the form $(2 × 3 × 5 × 7) + 1$ tells us that 2,3,5 and 7 are not prime factors. So we only need to test 11 and 13.

211 does not have any such factors, and so is prime.

Exercise (2.2).8

Test the following numbers for compositeness. If they are composite, write down their prime decomposition:

(a) 161

(b) 203

(c) 1003

(d) 1009

We use Corollary (2.10). 

If $n > 1$ is composite then it has a prime divisor $p$ such that $p ≤ ⌊√n⌋$.

(a) $\lfloor \sqrt(161) \rfloor = 12$, so we only need to test prime factors less than or equal to 12, that is $2,3,5,7,11$. This gives us

$ 161 = 7 \times 23$

(b) $\lfloor \sqrt(203) \rfloor = 14$, so we only need to test prime factors less than or equal to 14. This gives us

$ 203 = 7 \times 29 $

(c) $\lfloor \sqrt(1003) \rfloor = 31$, so we only need to test prime factors less than or equal to 31. This gives us

$ 1003 = 17 \times 59 $

(c) $\lfloor \sqrt(1009) \rfloor = 31$, so we only need to test prime factors less than or equal to 31.

There are no factors, and so 1009 is prime.

Exercise (2.2).7

Show that if $x− 1 < n < x$ where $n$ is a natural number then

(a) $⌊x⌋ = n$

(b) $⌈x⌉ = n + 1$

(a) $\lfloor x \rfloor$ is the largest integer smaller than or equal to $x$.

We are given $n < x$ where $n$ is a natural number (and so an integer). 

We need to show there is no other integer greater than $n$ but less than or equal to $x$.

For the purpose of contradiction, let's assume there is an integer $m = n+1$ such that 

$$n \; < \; m \; \le  \; x$$

$$n \; < \; n+1 \; \le  \; x$$

Subtracting 1 gives us

$$  n \le \; x -1$$

This contradicts the given $x-1 < n$, and so there is no integer larger than $n$ that is smaller than or equal to $x$. And so

$$ \lfloor x \rfloor = n $$

(b) $\lceil x \rceil$ is the smallest integer greater than or equal to $x$.

We are given

$$x -1 \; < \; n$$

Adding 1 gives us

$$x  \; < \; n+1$$

We need to show there is no other integer smaller than $n+1$ that is greater than to equal to $x$.

For the purpose of contradiction, let's assume there is an integer $m = (n+1) -1 = n$ such that

$$ x \; \le \; m < \; n + 1  $$

This gives us

$$ x \; \le \; n $$

This contradicts the given $n < x$, and so there is no integer smaller than $n+1$ that is greater than or equal to $x$. And so

$$ \lceil x \rceil = n + 1 $$

Exercise (2.2).6

Show that if $n− 1 < x < n$ where $n$ is a natural number then

(a) $⌈x⌉ = n$

(b) $⌊x⌋ = n− 1$

(a) The value of $\lceil x \rceil$ is the smallest integer larger than or equal to $x$. 

We are given that $x < n$. We need to establish that there is no other integer between $x$ and $n$. The integer below $n$ is $n-1$, and we are given that $n-1 < x$, so there is no other integer between $x$ and $n$. So $n$ is the smallest integer larger than or equal to $x$.

$$\lceil x \rceil = n $$

(b) The value of $\lfloor x \rfloor$ is the largest integer less than or equal to $x$.

We are given that $n-1 < x$. We need to establish that there is no integer between $n-1$ and $x$. The integer above $n-1$ is $n$, and we are given $x < n$, so there is no integer between $n-1$ and $x$. So $n-1$ is the largest integer less than or equal to $x$.

$$ \lfloor x \rfloor = n $$

Exercise (2.2).5

Show that the following statements are false (that is they are not equal):

(a) $⌊2 × x⌋ = 2 × ⌊x⌋$

(b) $⌈2 × x⌉ = 2 × ⌈x⌉$

(c) $⌈x⌉ = ⌊x⌋ + 1$

We will show the statements are false by providing a counter-example.

(a) Choosing $x=0.5$

$\lfloor 2 \times 0.5 \rfloor = \lfloor 1 \rfloor = 1$

$2 \times \lfloor 0.5 \rfloor = 2 \times 0 = 0$

(b) Choosing $x=0.5$

$\lceil 2 \times 0.5 \rceil = \lceil 1 \rceil = 1$

$2 \times \lceil 0.5 \rceil = 2 \times 1 = 2$

(c) Choosing $x=1$

$\lceil 1 \rceil = 1$

$\lfloor 1 \rfloor + 1 = 1 + 1 = 2$

Exercise (2.2).4

Plot the following graphs:

(a) $⌊x⌋ + 1$ 

(b) $⌊x⌋ − 1$

(c) $⌈x⌉ + 1$ 

(d) $⌈x⌉ − 1$

(a) The following graph of $\lfloor x \rfloor +1$ is on desmos (link):

(b) The following graph of $\lfloor x \rfloor -1$ is on desmos (link):

(c) The following graph of $\lceil x \rceil +1$ is on desmos (link):

(d) The following graph of $\lceil x \rceil -1$ is on desmos (link):

Exercise (2.2).3

Give an example of a real number $x$ such that $⌊x⌋ = ⌈x⌉$.

Any integer will work, eg 0 or 7.

$$ \lfloor 0 \rfloor = 0 = \lceil 0 \rceil $$

Exercise (2.2).2

Evaluate the following:

(a) $⌊6.3⌋ + ⌈−6.3⌉$

(b) $⌊6.3⌋ + ⌊−6.3⌋$

(c) $⌊−6.3⌋ + ⌈−6.3⌉$

(d) $⌊−6.3⌋ + ⌊−6.3⌋$

(a) $\lfloor 6.3 \rfloor + \lceil -6.3 \rceil = 6 + (-6) = 0$

(b) $\lfloor 6.3 \rfloor + \lfloor 6.3 \rfloor = 6 + (-7) = -1$

(c) $\lfloor -6.3 \rfloor + \lceil -6.3 \rceil = -7 + (-6) = -13$

(d) $\lfloor -6.3 \rfloor + \lfloor -6.3 \rfloor = -7 + (-7) = -14$

Exercise (2.2).1

Determine the following:

(a) $⌊5⌋$

(b) $⌊5.999⌋$

(c) $⌊𝜋^e⌋$

(d) $⌊e^𝜋 ⌋$

(e) $⌈7⌉$

(f) $⌈7.0000000001⌉$

(g) $⌈𝜋^e⌉$

(h) $⌈e^𝜋 ⌉$

(a) $\lfloor 5 \rfloor = 5$

(b) $\lfloor 5.999 \rfloor = 5$

(c) $\lfloor \pi ^ e \rfloor = \lfloor 22.459 \ldots  \rfloor = 22$

(d) $\lfloor  e^{\pi} \rfloor = \lfloor 23.14 \ldots  \rfloor = 23$

(e) $\lceil 7 \rceil = 7$

(f) $\lceil 7.0000000001 \rceil = 8$

(g) $\lceil \pi ^ e \rceil = \lceil 22.459 \ldots \rceil = 23$

(g) $\lceil e ^ {\pi} \rceil = \lceil 23.14 \ldots \rceil = 24$

Exercise (2.1).13

The tau function $𝜏 (n)$ was defined in Chapter 1 as the number of positive factors of n. For example,

$𝜏 (12) = 6$ because 12 has factors 1, 2, 3, 4, 6, 12.

Show that for a prime number, $p$, we have $𝜏 (p) = 2$.

A prime $p$ has only 2 positive factors, 1 and $p$, and so the number is 2.

$$ \tau(p) = 2 $$

Exercise (2.1).12

 The sigma function $𝜎 (n)$ in number theory is defined as the sum of positive factors of $n$.

For example,

$$𝜎 (12) = 1 + 2 + 3 + 4 + 6 + 12 = 28$$

Show that for a prime number, $p$, we have $𝜎 (p) = p + 1$.

A prime number $p$ has only two positive factors, 1 and $p$. Therefore the sum is $p+1$.

$$ \sigma(p) = p + 1 $$

Exercise (2.1).11

Disprove the following statements:

(a) If $p$ is prime then $p + 2$ is prime.

(b) The integer $n^2 + 1$ is prime for $n = 2m$.

(c) The integer $n^2 − 1$ is composite.

(d) The quadratic $4n^2 − 2n + 1$ where $n$ is a natural number produces primes.

(e) The Euclid number $N$ given by $N = (2 × 3 × 5 × 7 × ⋯ × P) + 1$ is prime where $P$ is a prime number.

We disprove the statements using counter-examples.

(a) $p=7$ is prime, but $p + 2 = 7+2 = 9$ is not prime.

(b) $m=4$ gives $n=2m=8$. Here $n^2+1 = 8^2 +1 = 65$ which is not prime.

(c) $n=2$ gives $n^2-1 = 2^2 - 1 = 3$ which is prime, not composite.

(d) $n=4$ gives $4n^2 -2n +1 = 64-8+1 = 57 = 19*3$, so is not prime.

(e) Consider $P=13$. Then $N = (2 \times 3 \times 5 \times 7 \times 11 \times 13) + 1 = 30031 = 59 \times 509$, so is not prime.

Exercise (2.1).10

Let $p$ be prime. Show that one of $p$, $p + 2$, or $p + 4$ is divisible by 3.

This is an interesting exercise.

Consider an integer $n$. It can be written in one the following three forms

• $n = 3k$
• $n = 3k+1$
• $n = 3k+2$

for some integer $k$. Let's consider each case in turn.

For the first case $n=3k$. This is clearly divisible by 3.

For the second case $n=3k+1$, we have $n+2 = 3k + 3 = 3(k+1)$ is divisible by 3.

For the third case $n = 3k+2$, we have $n +4 = 3k + 6 = 3(k+2)$ is divisible by 3.

So for any integer $n$, not just a prime $p$, one of $n$, $n+2$, $n+4$ is divisible by 3.

Exercise (2.1).9

Show that the integers $p, p + 2$ where $p$ is an odd prime has no common factor greater than 1.

(Show $p$ and $p + 2$ are relatively prime.)

Let $g = \gcd(p, p+2)$. That means $g \mid p$ and $g \mid p+2$. That means there exists some integer $j,k$ such that

$$ p = jg $$

$$ p + 2 = kg $$

Combining, we have

$$ j + \frac{2}{g} = k $$

For $j,k$ to be integers, $g$ must be 1 or 2.

Because $p$ is a prime greater than 2, $g \mid p$ means $g=1$ or $g=p>2$.

So the only possible value for $g=\gcd(p,p+2)$ is 1. 

That is, $p$ and $p+2$ has no common factor greater than 1.

Exercise (2.1).8

Find the error in the following statements and give reasons for your answers.

(a) $3 \mid (−3 × (−5)) \implies 3 = −3$

(b) $6 \not \mid (2 × 5 × 7) \implies \gcd (6, 2) = \gcd (6, 5) = \gcd (6, 7) = 1$

(a) $3 \mid (−3 × (−5))$ simply means that 3 divides 15. It doesn't mean 3 equals any of the given factors of 15.

For example, $4 \mid 2^3$ does not mean $4=2$.

If $x \mid yz$ and $y,z$ are prime, then $x=y$ or $x=z$, by Corollary (2.4).

(b) Aside from the false $\gcd(6,2)=1$, the deeper issue is that $a \not \mid pqr$ does mean $a$ is coprime to all $p,q,r$.

To see this, consider $bc \not \mid bqr$, where $b>1$. Here $\gcd(bc,b) \ne 1$.

On the other hand, if $a \not \mid p_2 p_3 p_4$, where $p_i$ are prime, then we can say $a$ is coprime to all $p_2, p_3, p_4$.

Exercise (2.1).7

Evaluate the following products:

(a) $ \Pi _{j=1}^{6}\left (2j \right ) $

(b) $ \Pi _{j=1}^{6} \left ( \frac{j}{2} \right ) $

(b) $ \Pi _{j=1}^{3} \Pi_{i=1}^{5}\left ( \frac{i}{j} \right ) $

(a) We have

$$ \begin{align} \Pi _{j=1}^{6}\left (2j \right ) & = (2 \times 1) \times (2 \times 2) \times (2 \times 3) \times (2 \times 4) \times (2 \times 5) \times (2 \times 6) \\ \\ & = 2^6 \times 6! \\ \\ & = 46080 \end{align}$$

(b) We have

$$ \begin{align} \Pi _{j=1}^{6}\left ( \frac{j}{2} \right ) & = \frac{1}{2} \times \frac{2}{2} \times \frac{3}{2}  \times \frac{4}{2}  \times \frac{5}{2}  \times \frac{6}{2}\\ \\ & = \frac{6!}{2^6} \\ \\ & = \frac{45}{4} \end{align}$$

(c) We have

$$ \begin{align} \Pi _{j=1}^{3} \Pi_{i=1}^{5}\left ( \frac{i}{j} \right ) & = \left ( \frac{1}{1} \times \frac{2}{1} \times \frac{3}{1} \times \frac{4}{1} \times \frac{5}{1} \right) \times \left ( \frac{1}{2} \times \frac{2}{2} \times \frac{3}{2} \times \frac{4}{2} \times \frac{5}{2}  \right) \times \left ( \frac{1}{3} \times \frac{2}{3} \times \frac{3}{3} \times \frac{4}{3} \times \frac{5}{3}  \right) \\ \\ & = \frac{1728000}{7776} \\ \\  & = \frac{2000}{9} \end{align}$$

Exercise (2.1).6

(a) Prove that consecutive integers have no prime factors in common.

(b) Prove that $\gcd (n, n + 1) = 1$.

(a) We've already shown in Exercise (1.1).18 a stronger result that consecutive integers have no common factors, prime or composite, except 1.

For practice, let's do it again.

If $g$ is a common factor of consecutive integers $n$ and $n+1$, then there exist integers $j,k$ such that

$$ n = jg $$

$$ n + 1 = kg $$

This means

$$ j + \frac{1}{g} = k $$

The only way $j,k$ are integers is if $g=1$. 

That is, consecutive integers only have 1 as a common factor, and so have no prime factors in common.

(b) We showed in part (a) above that consecutive integers $n, n+1$ only have 1 as a common factor. 

The gcd is the greatest common factor, which here is 1.

So $\gcd(n,n+1)=1$.

Exercise (2.1).5

(i) Prove that if $p$ and $q$ are distinct primes then $\gcd (p^n, q^n)=1$ for any natural number $n$.

(ii) Prove that if $p$ and $q$ are distinct primes then $\gcd (p^n, q^m) = 1$ for any natural numbers $m$ and $n$.

(i) Let $g = \gcd(p^n, q^n)$. 

Since $p$ is prime, the only factors of $p^n$ are $$1, p, p^2, \ldots, p^n$$

Since $q$ is prime, the only factors of $q^n$ are $$1, q, q^2, \ldots, q^n$$

And so $g$ must be one of these factors from each list. That is, $g=p^j = q^k$ where $j,k$ is between 0 and $n$ inclusive. 

If we assume $g>1$ for the purpose of contradiction, then $j,k$ is between 1 and $n$ inclusive. That is, we exclude $j=k=0$.

In this case, $g=p^j = q^k$ gives us $p \mid g$ and $g \mid q^k$. This gives us $p \mid q^k$. By Corollary 2.4, this means $p=q$. This is a contradiction since $p$ and $q$ are distinct.

Therefore $g>1$ was a false assumption, and so $\gcd (p^n, q^n)=1$.

(ii) Let $g = \gcd(p^n, q^m)$. 

Since $p$ is prime, the only factors of $p^n$ are $$1, p, p^2, \ldots, p^n$$

Since $q$ is prime, the only factors of $q^n$ are $$1, q, q^2, \ldots, q^m$$

And so $g$ must be one of these factors from each list. That is, $g=p^j = q^k$ where $0 \le j \le n$ and $0 \le j \le m$.

If we assume $g>1$ for the purpose of contradiction, then $1 \le j \le n$ and $1 \le j \le m$.

Again, $g=p^j = q^k$ gives us $p \mid g$ and $g \mid q^k$. This gives us $p \mid q^k$. By Corollary 2.4, this means $p=q$. This is a contradiction since $p$ and $q$ are distinct.

Therefore $g>1$ was a false assumption, and so $\gcd (p^n, q^n)=1$.

Exercise (2.1).4

Show that the smallest factor greater than 1 of $p^n$ is the prime $p$.

Since $p$ is prime, its only factors are 1 and $p$.

The factors of

$$ p^n = \underbrace{p \times p \times \ldots \ p}_{n\text{ repetitions}}$$

are $1, p, p^2, p^3, \ldots, p^n$. 

Note that $1 < p < p^2 < \ldots p^n$, since all primes are positive and strictly greater than 1.

So, the smallest factor, greater than 1, is $p$.

Exercise (2.1).3

(a) Let $p$ be prime and assume it does not divide $a$. Prove that $\gcd (a, p) = 1$.

(b) Prove that if $p$ and $q$ are distinct primes then $\gcd (p, q) = 1$.

(a) Let $g=\gcd(a,p)$. This means $g \mid a$ and $g \mid p$. 

Since $p$ is prime, its only factors are 1 and $p$. That means $g$ is either 1 or $p$.

Let's consider the possibility of $g=p$. Since $g \mid a$, we have $p \mid a$. But we are given that $p$ does not divide $a$. So $g \neq p$.

This leaves only $g=1$ as the only possibility, that is $\gcd(a,p)=1$.

(b) Let $g=\gcd(p,q)$. Tis means $g \mid p$ and $g \mid q$.

Since $p$ is prime, its only factors are 1 and $p$. That means $g$ is either 1 or $p$.

Since $q$ is prime, its only factors are 1 and $q$. That means $g$ is either 1 or $q$.

We're given $p$ and $q$ are distinct, so $g=1$ is the only possibility. That is, $\gcd(p,q)=1$.

Exercise (2.1).2

Write the prime decomposition of the following numbers:

(a) 53 (b) 530 (c) 1988 (d) 666 (e) 2021

(a) 53 has no prime decomposition as it is prime itself.

(b) $53 = 2 \times 5 \times 53$

(c) $ 1988 = 2^2 \times 7 \times 71 $

(d) $ 2 \times 3^2 \times 37 $

(e) $ 2021 = 43 \times 47 $

Exercise (2.1).1

Write the prime decomposition of the following numbers:

(a) 56 (b) 57 (c) 200 (d) 360 (e) 1001

(a) $56 = 2^3 \times 7$

(b) $57 = 3 \times 19$

(c) $200 = 2^3 \times 5^2$

(d) $360 = 2^3 \times 3^2 \times 5$

(e) $1001 = 7 \times 11 \times 13$

Exercise (1.4).16

Prove or disprove the following statements:

(a) If $d \mid a$ and $d \mid b$, then the Diophantine equation $ax + by= c$ has solutions.

(b) If $d \mid a$, $d \mid b$ and $d \mid c$, then the Diophantine equation $ax + by= c$ has solutions.

(c) The Diophantine equation $ax + (a + 1) y= 1$ has solutions.

(a) The equation $ax + by = c$ has integer solutions if $\gcd(a,b) \mid c$.

However, we have no reason to believe $\gcd(a,b)$ does indeed divide $c$.

We're given $d \mid a$ and $d \mid b$ but these have no constraint on $c$.

And so the statement is not always true.

(b) The equation $ax + by = c$ has integer solutions if $\gcd(a,b) \mid c$.

We're given $d \mid a$, $d \mid b$ and $d \mid c$, which means for some integers $p,q,r$, 

$$ a = pd $$

$$ b = qd $$

$$ c = rd $$

This gives us

$$ \gcd(a,b) = \gcd(pd, qd) = d \gcd(p,q) $$

The equation has integer solutions if $\gcd(a,b) \mid c$, which is restated as 

$$ d \gcd(p,q) \mid rd $$

That is, $\gcd(a,b)$ devides $c$ is there exists some integer $s$ such that

$$ rd = sd \gcd(p,q)$$

Simplified

$$ r = s \gcd(p,q)$$

There aren't enough constraints for us to determine this.

So in general the statement is not true.

(c) The Diophantine equation $ax + (a + 1) y= 1$ has integer solutions if $\gcd(a, a+1) \mid 1$. 

This is only possible if $\gcd(a, a + 1) = 1$.

We know from exercise (1.1).18 that two consecutive integers are coprime.

So the equation has integer solutions.

Exercise (1.4).15

Let $a ≠ 0$ and consider the linear equation $ax + may= na$. Prove that if $x_0, y_0$ is a particular solution of this equation then the general solution is given by $x = x_0 + mt$ and $y= y_0− t$.

By Proposition (1.18), the general solution is

$$ x = x_0 + \frac{ma}{\gcd(a,ma)}t \quad y = y_0 - \frac{a}{\gcd(a,ma)}t $$

for any integer $t$.

Let's consider $\gcd(a,ma)$

$$\begin{align} \gcd(a,ma) & = a \gcd(1,m) \quad \text{Proposition 1.11} \\ \\ & = a \end{align}$$

So the general solution is

$$ x = x_0 + mt \quad y = y_0 - t $$

for any integer $t$.

Exercise (1.4).14

Prove the following result:

Let $\gcd (a, b) = 1$ and a positive integer $k$ divides $c$. Let $x_0, y_0$ be particular solutions of the equation $$akx + bky= c$$

Then all the other solutions of this equation are given by

$$x = x_0 + (\frac{b}{k})t \quad \text{and} \quad y= y_0− (\frac{a}{k})t$$

where $t$ is any integer.

Using Proposition 1.18, the general solution to the equation $akx + bky= c$, given a particular solution $x_0, y_0$, is

$$x = x_0 + (\frac{bk}{g})t \quad \text{and} \quad y= y_0− (\frac{ak}{g})t$$

where $t$ is any integer, and $g=\gcd(ak,bk)$.

Let's focus on $g$

$$\begin{align} g &= \gcd(ak, bk) \\ \\ & =  k \gcd(a,b) \quad \text{Proposition 1.11} \\ \\ & = k (1) \quad \text{given } \gcd(a,b)=1 \\ \\ &= k \end{align}$$

So the general solution is

$$x = x_0 + bt \quad \text{and} \quad y= y_0− at$$

where $t$ is any integer.

Note: this is not what the exercise says the general solution is, and I believe there is a typo in the textbook.

Exercise (1.4).13

Show that 45x + 81y= 1 has no solutions.

The $\gcd(45,81)= 9$. This does not divide 1. 

Using the result of the previous exercise, this means the equation has no integer solutions.

Exercise (1.4).12

Let $\gcd (a, b) > 1$. Show that the equation $ax + by= 1$ has no solutions.

We'll use Proposition (1.17)

The Diophantine equation $ax + by= c$ has integer solutions if and only if $\gcd (a, b) \mid c$.

By Proposition 1.17 the equation $ax + by =1$ has integer solutions if $ \gcd(a,b) \mid 1$. But since we're given $\gcd(a,b)>1$ this is not possible. A number larger than 1 can't divide 1.

And so $ax + by= 1$  has no (integer) solutions.

Exercise (1.4).11

Prove that $ax + by= 1$ has integer solutions if and only if $\gcd (a, b) = 1$. 

We'll use Proposition (1.17)

The Diophantine equation $ax + by= c$ has integer solutions if and only if $\gcd (a, b) \mid c$.

Proposition 1.17 with $c=1$ is the proposition we want to prove.

Exercise (1.4).10

Prove Corollary (1.19).

Corollary (1.19) is

Let $\gcd (a, b) = 1$ (relatively prime) and $x_0$, $y_0$ be particular solutions of the equation $ax + by= c$.

Then all the other solutions of this equation are given by $x = x_0 + bt$ and $y= y_0− at$ where $t$ is any integer.

This corollary is a special case of Proposition (1.18)

Let $\gcd (a, b) = g$. If $g \mid c$ and $x_0$, $y_0$ are particular solutions of the equation $ax + by= c$, then all the other solutions of this equation are given by 

$$x = x_0 + (\frac{b}{g})t \quad \text{and} \quad y= y_0− (\frac{a}{g})t$$

where $t$ is any integer.

We are given $g = \gcd(a,b)=1$, so Proposition 1.18 simply reduces to Corollary 1.19.

Exercise (1.4).9

An ATM machine distributes £10 and £20 notes. If you ask for £100, what possible combinations of £10 and £20 notes can you get?

We formulate the problem as follows, with $x$ the number of £10 notes, and $y$ £20 notes.

$$ 10x + 20y = 100 $$

The $\gcd(20,10)=10$ which divides 100, so the equation has integer solutions.

By inspection a solution is $x_0 = 10, y_0 = 0$. The general solution is therefore

$$ x = 10 + 2t \quad y = -t$ $$

However, the number of notes $x,y$ must be non-negative, so we have the following inequalities

$$ 10 + 2t \ge 0 \quad \iff \quad t \ge -5 $$

$$ -t \ge 0 \quad \iff \quad 0 \ge t  $$

That is

$$ -5 \le t \le 0 $$

The values of $t$ which generate non-negative $x,y$ are -5, -4, -3, -2, -1 and 0.

The possible combinations of $x$, £10 notes, and $y$, £20 notes are

t	x=10+2t	y=-t	10x+20y
-5	0	5	100
-4	2	4	100
-3	4	3	100
-2	6	2	100
-1	8	1	100
0	10	0	100

Exercise (1.4).8

Each hotdog costs £0.24 and each bun costs £0.14. List the combination(s) of hotdogs and buns that can be purchased with exactly £5. 

We encode the problem as follows, with  $h$ the number of hotdogs, and $b$ the number of buns.

$$ 24h + 14b = 500 $$

The $\gcd(24,14)=2$, which divides 500, and so the equation has integer solutions.

By inspection, a solution is $h_0=8, b_0=22$. So a general solution is

$$ h = 8 + 7t \quad b = 22 - 12t $$

for any integer $t$.

However, the number of hotdogs and buns must be non-negative, so we have the following inequalities

$$ 8 + 7t \ge 0 $$

$$ 22 - 12t \ge 0 $$

Re-arranging,

$$ t \ge -\frac{8}{7} $$

$$ \frac{11}{6} \ge  t $$

Combining,

$$ -\frac{8}{7} \le t \le \frac{11}{6} $$

The values of $t$ which generate non-negative $b$ and $h$ are -1, 0 and 1.

And so the combinations of hotdogs and buns are as follows.

t	h=8+7t	b=22-12t	24h+14b
-1	1	34	500
0	8	22	500
1	15	10	500

Exercise (1.4).7

Assume there are one hundred pence in the pound (£). First-class stamps cost 60p (£0.60) and second-class stamps cost 50p (£0.50) each.

What combination(s) of stamps can you get for exactly £50, leaving no change?

We encode the problem as follows, with $x$ as the number of first class stamps, and $y$ second class stamps.

$$ 60x + 50y = 5000 $$

The $\gcd(60,50)=10$ divides 5000, which tells us the equation has integer solutions.

By inspection, a solution is $x_0=0, y_0=100$. A general solution is

$$ x = 5t, \quad y = 100 - 6t $$

for any integer $t$.

However, we require $x$ and $y$ to be non-negative, so

$$ 5t \geq 0 $$

$$ 100 - 6t \geq  0$$

That is

$$ 0 \leq t \leq \frac{50}{3}t $$

Non-negative integer values for $x$ and $y$ are generated by $t$ ranging from 0 to 16.

t	x=5t	y=100-6t	60x+50y
0	0	100	5000
1	5	94	5000
2	10	88	5000
3	15	82	5000
4	20	76	5000
5	25	70	5000
6	30	64	5000
7	35	58	5000
8	40	52	5000
9	45	46	5000
10	50	40	5000
11	55	34	5000
12	60	28	5000
13	65	22	5000
14	70	16	5000
15	75	10	5000
16	80	4	5000

Exercise (1.4).6

Assume there are one hundred pence in the pound (£). Using just 5p (£0.05) and 10p (£0.10) pieces, how many of each do you need in order to pay a parking meter charge of £3.10.

We encode the problem as followed with $f$ being the number of 5p coins and $t$ the 10p coins

$$ 5f + 10t = 310 $$

The $gcd(5,10)=5$ divides 310, so the equation has integer solutions.

In fact, by inspection we can see 310 is a multiple of 10, so 31 10p coins is a solution. 

Let's find other solutions. We already have one solution $f_0 = 0, t_0 = 31$. The general solution is

$$ f = 0 + \frac{10}{5}n = 2n, \quad t = 31 - \frac{5}{5}n = 31-n$$

for any integer $n$.

So need $f$ and $t$ to be non-negative, which gives us the following inequalities

$$ 2n \ge 0 $$

$$ 31 - n \ge 0$$

That is

$$ 0 \leq n \leq 31 $$

This creates 32 different solutions.

n	f=2n	t=31-n	5f+10t
0	0	31	310
1	2	30	310
2	4	29	310
3	6	28	310
4	8	27	310
5	10	26	310
6	12	25	310
7	14	24	310
8	16	23	310
9	18	22	310
10	20	21	310
11	22	20	310
12	24	19	310
13	26	18	310
14	28	17	310
15	30	16	310
16	32	15	310
17	34	14	310
18	36	13	310
19	38	12	310
20	40	11	310
21	42	10	310
22	44	9	310
23	46	8	310
24	48	7	310
25	50	6	310
26	52	5	310
27	54	4	310
28	56	3	310
29	58	2	310
30	60	1	310
31	62	0	310

Exercise (1.4).5

Suppose in the Die Hard problem we have four- and five-gallon containers and we want to measure exactly three gallons. How can we do this?

We encode the scenario as follows, with $x$ the number of times we fill the four-gallon container, and $y$ the five-gallon container.

$$ 4x + 5y = 3 $$

By inspection, a solution is $x_0 = 2, y_0 = -1$. That is, we fill the four-gallon container twice and empty the five-gallon container once.

• Fill the four-gallon container and pour it into the 5-gallon container, so it only contains 4 gallons.
• Fill the four-gallon container again and pout it into the 5-gallon container. Since it contains 4 gallons already, only one gallon will be transferred.
• Pour away the 5 gallons from the 5-gallon container.
• We will be left with 3 gallons in the 4 gallon-container.

Other solutions are possible. The general solution is

$$ x = 2 + 5t \quad y = -1 - 4t $$

for any integer $t$.

Exercise (1.4).4

A collection of bars costs £2 and a collection of rolls costs £3. List the number of bars and rolls you can purchase with £20, leaving no change. You must buy at least one of each.

We encode the scenario as follows, with $b>0$ being the number of bars, and $r>0$ the number of rolls.

$$ 2b + 3r = 20$$

The coefficients are small enough for us to find solutions by brute force, but we'll follow the procedure we'd use for larger coefficients.

Here $\gcd(2,3)=1$, which divides 20, so the equation has integer solutions.

By inspection a solution is $b_0 = 4, r_0 = 4$. A general solution is

$$ b = 4 + 3t,  r = 4 - 2t $$

for any $t$.

However, since both $b$ and $r$ must be greater than zero we have the following inequalities

$$ 4 + 3t > 0 $$

$$ 4 - 2t > 0 $$

Re-arranging

$$ t > -\frac{4}{3}  $$

$$ 2 > t $$

That is

$$ - \frac{4}{3} < t < 2$$

The only values of $t$ that lead to integer $b$ and $r$ are $t=-1, 0 and 1$. There are therefore 3 solutions:

1. $t=-1$ gives $b=1, r = 6$, that is one bar and six rolls.
2. $t = 0$ gives $b=4, r = 4$, that is four bars and four rolls.
3. $t=1$ gives $b=7, r=2$, that is seven bars and two rolls.

Exercise (1.4).3

Solve the following Diophantine equations for general solutions, if possible:

(a) $101x + 600y= 1001$

(b) $181x + 232y= −100$

(a) Here $\gcd(101, 600) = 1$, which divides 1001. This means the equation has integer solutions.

Because the coefficients are large, we won't use trial and error to find a solution. We'll use Euclid's Algorithm.

$ 600 = 5(101) + 95 $

$ 101 = 1(95) + 6 $

$ 95 = 15(6) + 5 $

$ 6 = 1(5) + 1 $

$ 5 = 5(1) + 0$

Re-arranging

$ 1 = 6 -5 $

$ 1 = 6 - (95 - 15(6)) = -95 + 16(6)$

$ 1 = -95 + 16(101 - 95) $

$ 1 = -17(95) +16(101) $

$ 1 = -17(600 - 5(101)) +16(101) $

$ 1 = -17(600) + 101(101) $

So a solution of $101x + 600y =1$ is $x=101, y=-17$.

Multiplying through by 1001, gives us  $101(101\times 1001) + 600(-17 \times 1001) =1001$.

This means a solution of $101x + 600y= 1001$ is

$$x_0=101101, \quad y_0=-17017$$

A general solution is

$$ x = 101101  + 600t, \quad y = -17017 - 101t$$

for any integer $t$.

(b) Here $\gcd(181,232)=1$, which divides -100. This means the equation has integer solutions.

Because the coefficients are large, we won't use trial and error to find a solution. We'll use Euclid's Algorithm.

$ 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 = 2(1) + 0 $

Re-arranging

$1 = 3 - 2 = (23 - 4(5)) - (5 - 3)$

$ 1= 23 - 5(5) + 3 = 23 - 5(5) + (23 - 4(5))  = 2(23) - 9(5)$

$ 1 = 2(23) - 9(28-23) = 11(23) -9(28) = 11(51 - 28) - 9(28) = 11(51) -20(28) $

$ 1 = 11(232 - 181) - 20(181 -3(51))  = 11(232) -31(181) + 60(51)$

$ 1 = 11(232) -31(181) + 60(232-181) = 71(232) - 91(181) $

So a solution of $181x + 232y= 1$ is $x=-91, y = 71$.

Multiplying through by -100, gives us $181(-91 \times -100) + 232(71 \times -100) = -100$.

This means a solution of $181x + 232y= −100$ is

$$ x_0 = 9100, \quad y_0 = -7100 $$

A general solution is

$$ x = 9100 + 232t, \quad y = -7100 - 181t$$

for any integer $t$.

Exercise (1.4).2

Determine whether the following equations have integer solutions. If they do have solutions, find the general solution:

(a) $2x + 4y= 1$

(b) $48x + 56y= 32$

(c) $54x + 180y= −72$

(a) Here $\gcd(2,4) = 4$, which does not divide 1. Therefore the equation does not have integer solutions.

(b) Here $\gcd(48,56)=8$, which divides 32. Therefore the equation does have integer solutions.

By trial and error we find one solution $x_0=10, y_0=-8$. The general solution is

$$ x = 10 + 7t \quad y =-8 - 6t$$

for any integer $t$.

(c) Here $\gcd(54, 180)=18$, which does divide -72. Therefore the equation does have integer solutions.

By trial and error we find one solution $x_0=2, y_0=-1$. The general solution is

$$ x = 2 + 10t \quad y =-1 - 3t$$

for any integer $t$.

Exercise (1.4).1

Find the general solution of the following Diophantine equations:

(a) $2x + 3y= 5$

(b) $3x + 6y= 9$

(c) $15x − 20y= 10$

For this exercise we make use of Proposition (1.17). 

Let $\gcd (a, b) = g$. The Diophantine equation $ax + by= c$ has integer solutions if and only if $g \mid c$.

We also make use of Proposition (1.18).

Let $\gcd (a, b) = g$. If $g \mid c$ and $x_0, y_0$ are particular solutions of the equation $ax + by= c$, then all the other solutions of this equation are given by $$x = x_0 + (\frac{b}{g} )t \quad \text{and} \quad y= y_0 − (\frac{a}{g} )t$$ where $t$ is any integer. 

(a) Here $g = \gcd(2,3)=1$ and so $g \mid 5$. Therefore, the equation has integer solutions, by Proposition 1.17.

By inspection $x_0=1$ and $y_0=1$ is a solution. The general solution, by Proposition 1.18, is

$$ x = 1 + 3t \quad y = 1 - 2t$$

for any integer $t$.

(b) Here $g = \gcd(3,6) = 3$ and so $g \mid 9$. Therefore, the equation has integer solutions, by Proposition 1.17.

By inspection $x_0 = 1$ and $y_0 = 1$ is a solution. The general solution, by Proposition 1.19, is

$$ x = 1 + 2t \quad y = 1 - t$$

for any integer $t$.

(c) Here $g = \gcd(15,20) = 5$ and so $g \mid 10$. Therefore, the equation has integer solutions, by Proposition 1.17.

By inspection $x_0 = 10$ and $y_0 = 7$ is a solution. The general solution, by Proposition 1.19, is

$$ x = 10  -4t \quad y = 7 - 3t$$

for any integer $t$.

Note: The author's solutions look different. The scaling of $t$ is the same, but the constants are different. We can shift the constants from $x$ and $y$ scaling according to the given equation to solve.

Exercise (1.3).19

Prove that

$$ \gcd (a, b, c) = \gcd (a, \gcd (b, c)) $$

where $a, b, c$ are non-zero.

As shorthand, let $f=\gcd(a,b,c)$, $g=\gcd(a,\gcd(b,c))$ and $h=\gcd(b,c)$. Our aim is to show $f=g$.

By definition of gcd, we have 

$$ g\mid a \quad \quad g \mid h $$

$$ h \mid b \quad \quad h \mid c $$

Since $g \mid h$ and $h \mid b$, we have $g \mid b$, by Theorem 1.2.  Similarly, since $g \mid h$ and $h \mid c$, we have $g \mid c$.

In summary

$$ g\mid a \quad \quad g \mid b \quad \quad g \mid c $$

This tells us $g$ is a common divisor of $a$, $b$ and $c$, but does not tell us it is the greatest common divisor like $f$ is, so

$$g \leq f$$

We also have

$$ f\mid a \quad \quad f \mid b \quad \quad f \mid c $$

The result from exercise (1.3).18 tells us

$$h = \gcd (b, c) \quad \land \quad f\mid b \quad \land \quad f \mid c \quad \implies \quad f \mid h $$

So we have

$$ f \mid a \quad f \mid  \gcd (b, c)$$

This tells is $f$ is a common divisor of $a$ and $gcd(b,c)$, but does tell us it is the greatest common divisor like $g$ is, so

$$ f \leq g $$

Both $g \leq f$ and $f \leq g$ means $f=g$, that is $ \gcd (a, b, c) = \gcd (a, \gcd (b, c)) $.

Exercise (1.3).18

Let $g= \gcd (a, b)$ and $d\mid  a$, $d \mid b$. Prove that $d \mid g$.

The premises $d\mid  a$ and $d \mid b$ mean that for some integers $x,y$ we have

$$ a = x d $$

$$ b = y d $$

Substituting

$$ g = \gcd(xd,  yd) $$

That is, for some integers $m,n$

$$ g =mxd $$

$$ g =nyd $$

This gives us $d \mid g$.

Exercise (1.3).17

Prove Proposition (1.11).

Proposition (1.11) is

Let $\gcd (a, b) = g$. For any positive integer $m$ we have $\gcd (ma, mb) = mg$.

We're given $\gcd (a, b) = g$ which means there exist integers $x,y$ such that

$$ a = xg $$

$$ b = yg $$

Multiplying through by $m$ we have

$$ ma = x(mg) $$

$$ mb = y(mg) $$

So $mg \mid ma$ and $mg \mid mb$. This means there exists some integer $k>0$ such that

$$ \gcd(ma, mb) = k(mg) $$

If we assume, for the purpose of contradiction, that $k>1$, then

$$ \gcd(ma, mb) > mg $$

If we take the particular case of $m=1$, this gives us

$$ \gcd(a, b) > g $$

This contradicts the premise $\gcd(a,b)=g$, and so the assumption $k>1$ is false, meaning $k=1$. That is,

$$ \gcd(ma, mb) = mg $$

So we have shown Proposition 1.11 is true.

Alternative Solution

The alternative solution given by the author is worth exploring.

The $\gcd(ma, mb)$ is the least positive value of $ max + mby = m(ax + by) $ for integers $x,y$.

Since $m>0$, this is $m$ times the least positive value of $(ax + by)$ which is the $m\gcd(a,b) = mg$. 

Exercise (1.3).16

Prove that if $\gcd (a, b) = 1$ then $\gcd (a + b, ab) = 1$.

Let's practice proof by contradiction, something the textbook author uses a lot in his solutions. 

Let's remind ourselves that $A \implies B$ is the same as $\neg B \implies \neg A$. So we'll assume the conclusion $\gcd(a+b,ab)=1$ is false, and aim to show the premise is also false

Since a gcd is only ever more than or equal to 1, the negation of the conclusion is

$$  g = \gcd(a+b, ab) > 1$$

By definition of gcd, this means $g \mid (a + b)$ and $g \mid ab$. Furthermore $g$ is a factor of linear combinations of $(a+b)$ and $ab$, from the Linear Combination Theorem 1.3. 

In particular

$$ g \mid a(a+b) - (ab) \implies g \mid a^2$$

$$ g \mid b(a+b) - (ab) \implies g \mid b^2$$

If $g \mid a^2$ then $g\mid a$, and similarly, if $g \mid b^2$ then $g \mid b$. That is, there exists some integer $k>0$ such that

$$\gcd(a,b) = kg$$

Since we assumed, $g>1$, then this tells us $\gcd(a,b)>1$. This contradicts the premise that $\gcd(a,b)=1$. 

We have shown that

$$\neg \Big ( \gcd(a+b, ab)=1 \Big ) \quad  \implies \quad \neg \Big ( \gcd(a,b) = 1 \Big )$$

That is

$$ \gcd (a, b) = 1 \quad  \implies  \quad \gcd (a + b, ab) = 1$$

Exercise (1.3).15

(i) Prove that

$$ \gcd (a, b) = \gcd (a, c) = 1 \iff \ gcd (a, bc) = 1 $$

(ii) Prove that if

$$ \gcd (a, n_1) = \gcd (a, n_2) = \ldots  = \gcd (a, n_k) = 1 $$

then

$$\gcd (a, n_1 × n_2 \ldots × n_k) = 1$$

(iii) Prove that if $\gcd (a, b) = 1$ then $\gcd (a^n, b^n) = 1$ where $n$ is a natural number.

(i) We need to prove both directions:

• $ \gcd (a, b) = \gcd (a, c) = 1 \implies \gcd (a, bc) = 1 $
• $ \gcd (a, b) = \gcd (a, c) = 1 \impliedby \gcd (a, bc) = 1 $

($\implies$)

We apply Bezout's Identity to $\gcd(a,b)=1$ and $\gcd(a,c)=1$. There exist integers $x,y, p,q$ such that

$$ ax + by = 1 $$

$$ ap + cq = 1 $$

Multiplying

$$ \begin{align} 1 &= a^2xp + axcq + byap + bycq \\ \\ & = a(axp + xcq + byp) + bc(yq) \end{align}$$

The $\gcd(a,bc)$ must also divide 1, which is only possible if

$$ \gcd(a, bc) = 1 $$

($\impliedby$)

We apply Bezout's Identity to $\gcd(a,bc)=1$. There exist integers $m,n$ such that

$$ am + bcn = 1 $$

We can read two facts from this. The $\gcd(a,b)$ divides 1, and $\gcd(a,c)$ divides 1. This is only possible if

$$\begin{align} \gcd(a,b) &= 1 \\ \\ \gcd(a,c) &= 1  \end{align}$$

By showing both ($\implies$) and ($\impliedby$), we have proven the original equivalence.

(ii) This doesn't really require a long proof because it is clear that if $a$ shares no common factors, except 1, with any of $n_1, n_2, \ldots, n_k$, then it doesn't share any common factors with the product $n_1 \times n_2 \times \ldots \times n_k$.

For practise, let's do a proof by induction.

Let's establish the statement $P(m)$ to mean

If $ \gcd (a, n_1) = \gcd (a, n_2) = \ldots  = \gcd (a, n_m) = 1 $ then $\gcd (a, n_1 × n_2 \ldots × n_m) = 1$.

We need to prove a base case and an induction step.

Base Case

The base case is $P(2)$

If $ \gcd (a, n_1) = \gcd (a, n_2)  = 1 $ then $\gcd (a, n_1 × n_2) = 1$

We've shown t his is true in part (i) of the exercise. So the base case is true.

Induction Step

We need to show $P(m) \implies P(m+1)$. The statement $P(m+1)$ is

If $ \gcd (a, n_1) = \gcd (a, n_2) = \ldots  = \gcd (a, n_m) = \gcd(a,n_{m+1}) = 1 $ then $\gcd (a, n_1 × n_2 \ldots × n_m \times n_{m+1}) = 1$

We assume $P(m)$ holds as the induction hypothesis. The assumption under $P(m)$ that $ \gcd (a, n_1) = \gcd (a, n_2) = \ldots  = \gcd (a, n_m) = 1 $ is covered by the assumption for $P(m+1)$. The conclusion of the assumption $P(m)$ is that $\gcd (a, n_1 × n_2 \ldots × n_m) = 1$.

If we rename, for clarity, $n_1 × n_2 \ldots × n_m$ as $b$ then we have two assumptions, $\gcd(a,b)=1$ and $\gcd(a, n_{m+1})=1$. Again by exercise (i), this gives us $\gcd(a, b \times n_{m+1})=1$. This is the conclusion of $P(m+1)$. We have shown $P(m+1)$ follows from $P(m)$.

Thus by induction we have shown that if $ \gcd (a, n_1) = \gcd (a, n_2) = \ldots  = \gcd (a, n_m) = 1 $ then $\gcd (a, n_1 × n_2 \ldots × n_m) = 1$

(iii) We'll use induction.

Let's establish the statement $P(n)$ to mean

If $\gcd (a, b) = 1$ then $\gcd (a^n, b^n) = 1$, for integers $a,b$ and natural number $n$.

We need to show the base case and inductive step are true.

Base Case

The base case is $P(0)$ which is

If $\gcd (a, b) = 1$ then $\gcd (a^0, b^0) = 1$, for integers $a,b$ and natural number $n$.

This is trivially true since $\gcd(a^0, b^0) = \gcd(1, 1) = 1$.

For practice, let's try $P(1)$ which is

If $\gcd (a, b) = 1$ then $\gcd (a^1, b^1) = 1$, for integers $a,b$ and natural number $n$.

Again, this is trivially true, effectively stating $A \implies A$.

Induction Step

We need to show $P(n) \implies P(n+1)$.  $P(n+1)$ is

If $\gcd (a, b) = 1$ then $\gcd (a^{n+1}, b^{n+1}) = 1$, for integers $a,b$ and natural number $n$.

We assume $P(n)$ is true as the induction hypothesis. The conclusion of $P(n)$ is that $\gcd (a^n, b^n) = 1$ is true.

In summary, we assume

• $\gcd (a, b) = 1$
• $\gcd (a^n, b^n) = 1$

From exercise (i) 

$$ \boxed {\gcd (a, b) = \gcd (a, c) = 1 \iff \gcd (a, bc) = 1} $$

Taking $c=b$, we have

$$ \gcd (a, b)  = 1 \iff \gcd (a, b^2) = 1 $$

So the assumption $\gcd(a,b)=1$ gives us $\gcd(a,b^2)=1$. We can then repeatedly apply the result from exercise (i) to reach $\gcd(a,b^{n+1})=1$.

By the symmetry of gcd, that is $\gcd(x,y)=\gcd(y,x)$, a corollary of the result from exercise (i) is

$$ \boxed {\gcd (a, b) = \gcd (c, b) = 1 \iff \gcd (ac, b) = 1} $$

Similarly, taking $a=c$, we have

$$ \gcd (a, b) = 1 \iff \gcd (a^2, b) = 1 $$

So the assumption $\gcd(a,b)=1$ gives us $\gcd(a^2,b)=1$. We can then repeatedly apply the corollary of exercise (i) to reach $\gcd(a^n,b)=1$.

Now, applying the result from exercise (i) to $\gcd(a^n, b^n)=1$ and $\gcd(a^n, b)=1$ we have

$$ \gcd (a^n, b^n) = \gcd (a^n, b) = 1 \iff  \colorbox{pink}{$\gcd (a^n, b^{n+1}) = 1$} $$

Again, applying the corollary of exercise (ii) to  $\gcd(a,b^{n+1})=1$ and $\gcd (a^n, b^{n+1}) = 1$ we finally have

$$ \gcd (a, b^{n+1}) = \gcd (a^n, b^{n+1}) = 1 \iff   \colorbox{pink}{$\gcd (a^{n+1}, b^{n+1}) = 1$} $$

So we have shown that $P(n+1)$ follows from $P(n)$.

By showing both the base case and the inductive step, we have proved that if $\gcd (a, b) = 1$ then $\gcd (a^n, b^n) = 1$ where $n$ is a natural number.

Exercise (1.3).14

Disprove the following:

$$a \mid b^2 \implies  a \mid b$$

We can disprove this with a counter example. 

Let's choose $a=4$ and $b=2$.This gives us

$$ 4 \mid 4 \implies 4 \mid 2 $$

which is false. So the given statement is not true for all integers $a,b$.

Exercise (1.3).13

Prove that if $\gcd (a, b) = 1$ then for any $d$ such that $d \mid a$ we have

$$\gcd (d, b) = 1$$

We're given $\gcd (a,b) = 1$. By Bezout's Identity this means there exist integers $x,y$ such that

$$ ax + by = 1 $$

We're also given $d \mid a$, which means there exists an integer $z$ such that

$$ a = zd $$

Putting these together, we have

$$ (zd)x + by = 1 $$

More explicitly,

$$ d(zx) + by = 1 $$

Here,  the $\gcd(d,b)$ must also divide 1, and that is only possible if $\gcd(d,b)=1$.

Exercise (1.3).12

(i) Prove that if $a \mid c$ and $b \mid c$ and $\gcd (a, b) = 1$ then $(a \times b) \mid c$.

(ii) Prove that if $a_1 \mid c, a_2 \mid c, \ldots , a_n \mid c$ and $\gcd (a_j, a_i) = 1$ where $i \neq j$ then

$$(a_1 \times a_2 \times  \ldots  \times  a_n) \mid  c$$

(i) We're given $a \mid c$ and $b \mid c$, which means for some integers $j,k$

$$\begin{align} c &= ja \\ \\ c &= kb \end{align}$$

We're also given $\gcd(a,b) = 1$. By Bezout's Indentity,  there are integers $x,y$ such that 

$$ ax + by = 1 $$

Multiplying by $c$, 

$$ ax(kb) + by(aj) = c $$

Factorising,

$$ab(xk + yj) = c$$

And so we conclude $(a \times b) \mid c$

(ii) We'll prove this by induction on $n$.

Let's take the statement $P(n)$ to mean:

If $a_1 \mid c, a_2 \mid c, \ldots , a_n \mid c$ and $\gcd (a_j, a_i) = 1$ where $i \neq j$ then $(a_1 \times a_2 \times  \ldots  \times  a_n) \mid  c$.

We need to prove a base case and an induction step.

Base Case

The base case $P(2)$ is

If $a_1 \mid c, a_2 \mid c$ and $\gcd (a_1, a_2) = 1$ where $1 \neq 2$ then $(a_1 \times a_2) \mid  c$.

We proved this base case in exercise (i) above.

Induction Step

We need to show $P(n) \implies P(n+1)$.

We assume $P(n)$ as the induction hypothesis.

The statement $P(n+1)$ means:

If $a_1 \mid c, a_2 \mid c, \ldots , a_n \mid c, a_{n+1}\mid c$ and $\gcd (a_j, a_i) = 1$ where $i \neq j$ then $(a_1 \times a_2 \times  \ldots  \times  a_n \times a_{n+1}) \mid  c$.

The assumption for $P(n+1)$ that $a_1 \mid c, a_2 \mid c, \ldots , a_n \mid c, a_{n+1}\mid c$ where all $a_j, a_{i \ne j}$ are coprime, includes the assumption for $P(n)$ that  $a_1 \mid c, a_2 \mid c, \ldots , a_n \mid c$ where all $a_j, a_{i \ne j}$ are coprime. That means we have $(a_1 \times a_2 \times  \ldots  \times  a_n) \mid  c$.

That is, there exists some integer $p$ such that

$$(a_1 \times a_2 \times  \ldots  \times  a_n) p=  c$$

The additional assumption of $P(n+1)$ is that $a_{n+1} \mid c$, so there exists some integer $q$ such that

$$ a_{n+1}q = c$$

Since $a_{n+1}$ is coprime to all $a_1, a_2, \ldots, a_n$, by Bezout's identity we have, for some integers $r,s$

$$ (a_1 \times a_2 \times  \ldots  \times  a_n) r + a_{n+1} s = 1 $$

Multiplying by $c$

$$ (a_1 \times a_2 \times  \ldots  \times  a_n) ra_{n+1}q + a_{n+1} s(a_1 \times a_2 \times  \ldots  \times  a_n)p = c $$

Factorising

$$ (a_1 \times a_2 \times  \ldots  \times  a_n \times a_{n+1}) (rq + sp) = c $$

So we have $(a_1 \times a_2 \times  \ldots  \times  a_n \times a_{n+1})  \mid c$.

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

By showing the base case and the induction step, we have shown by induction that if $a_1 \mid c, a_2 \mid c$ and $\gcd (a_1, a_2) = 1$ where $1 \neq 2$ then $(a_1 \times a_2) \mid  c$.

Exercise (1.3).11

Prove that if integers $a ≠ 0$ and $b$ such that $a \mid b$ then $\gcd (a, b) = |a|$.

Since $a \mid b$, then for some integer $k$ we have

$$ b = ak $$

Substituting

$$ \begin{align} \gcd(a,b) & = \gcd(a, ak) \\ \\ &= \lvert a \rvert \gcd (\frac{a}{a},\frac{ak}{a}) \\ \\ &= \lvert a \rvert \end{align}$$

The penultimate line uses Proposition 1.5 that if $\gcd (a, b) = g$ then $\gcd (\frac{a}{g}, \frac{b}{g})=1$. We make use of $a \neq 0$ to ensure the division is valid.

The multiplier is $\lvert a \rvert$ because by definition a gcd is greater than zero.

Exercise (1.3).10

Prove that if there are integers $x$ and $y$ such that $ax + by= n$ then $g \mid n$ where $g= gcd (a, b)$.

If $g=\gcd(a,b)$ then we have $g \mid a$ and $g \mid b$. That is, for some integers $c,d$

$$\begin{align} a &= cg \\ \\ b &= dg \end{align}$$

Substituting for $a$ and $b$ in $ax + by = n$ gives us

$$\begin{align} (cg)x + (dg)y & = n \\ \\ g(cx + dy) & = n \end{align}$$

This tells us $g \mid n$.

Exercise (1.3).9

Find different negative integers $a$ and $b$ which satisfy the following:

(a) $\gcd (a, b) = 5$

(b) $\gcd (a, b) = 100$

(c) $\gcd (a, b) = 169$

We can do this exercise by using the negation of the gcd as one of the negative integers, and then for the second we can multiply that negative integer by a prime number such that is not a factor of it.

(a) $\gcd (-5, -10) = 5$

(b) $\gcd (-100, -200) = 100$

(c) $\gcd (-169, -338) = 169$

Exercise (1.3).8

Suppose $198 \mid 5x$. Show that $198 \mid x$.

Euclid's Lemma says that if $a \mid (bc)$ with $\gcd (a, b) = 1$ then $a \mid c$.

Here $\gcd(198,5)=1$ so by Euclid's Lemma $198 \mid x$.

Another way to look at this is that 5 is prime and only has factors 1 and 5.  Therefore 198 can't be a factor of 5, so must be a factor of $x$.

Exercise (1.3).7

Explain why there are no positive integer solutions to $5x + 6y= 1$.

[Hint: Sketch a graph.]

A graph of $5x+6y$ shows that in the quadrant of positive solutions, marked green, there are no integer solution.

The graph is here.

Exercise (1.3).6

Show that there is no integer solution to the linear equation $20x + 28y= 2$.

The smallest positive integer value of $20x + 28y$ is $\gcd(20,28)$, which is 4. 

Therefore the integer values of $20x + 28y$ cannot be 2, so the equation has no integer solutions.

Exercise (1.3).5

Given that $gcd (a, b) = 1$ and integers $x_0$ and $y_0$ are solutions to $ax + by= 1$, determine an integer solution to $ax + by= c$ where $c$ is an integer.

We're given

$$ a(x_0) + b(y_0) = 1 $$

Multiplying though by $c$ we have

$$ a(cx_0) + b(cy_0) = c $$

Here $cx_0$ and $cy_0$ are integers, because $c, x_0, y_0$ are integers.

So $x=cx_0, y=cy_0$ is an integer solution of $ax + by= c$.

Note: We don't make use of $\gcd(a,b)=1$.

Exercise (1.3).4

Find integers $x$ and $y$ in each of the following cases:

(i) $314x + 785y= 157$

(ii) $314x + 785y= 314$

(iii) $314x + 785y= −1570$

(i) The gcd of 214 and 785 is conveniently 157.  This means we can divide through by 157 to give

$ 2x + 5y = 1$

By inspection we have $x=3, y=-1$.

(ii) 314 is $2 \times \gcd(314,785)$. 

$ 314x + 785y = 2 \times 157 $

$ 2x + 5y = 2 $

Since we have $ 2(3) + 5(-1) = 1$, we can see

$ 2(2 \times 3) + 5(2 \times -1) = 2 $

So a solution is $x = 6, y=-2$

(iii) -1570 is $-10 \times \gcd(314, 785)$. 

Since we have $ 2(3) + 5(-1) = 1$, we can see

$ 2(-10 \times 3) + 5(-10 \times -1) = -10 $

So a solution is $x = 30, y=10$

Exercise (1.3).3

Determine the least positive integer values of the following linear combinations ($x$ and $y$ are integers):

(a) $132x + 174y$

(b) $102x + 207y$

(c) $99x + 1008y$

(d) $666x + 3020y$

The least positive integer values of $ax + by$ is $\gcd(a,b)$.

(a) 6

(b) 3

(c) 9

(d) 2