Exercise (3.5).14

Factorise the following integers into their prime factors:

(a) 9999 (b) 999 999

Hint: Consider $10^n− 1$.

(c) Repunits $R_n$ are given by.

$$ R_n = \underbrace{11 \ldots 1}_{n \text{ ones}} $$

For example $R_5 = \overbrace{11 \ldots 1}^{n \text{ ones}}$.

Factorize (i) $R_4$ (ii) $R_6$.

(a) We start with $9999=10^4-1= (10^2)^2 - 1^2$.

And so

$$ \begin{align} 9999 & \equiv 0 \pmod {9999} \\ \\ (10^2)^2  - 1^2 & \equiv 0 \pmod {9999} \\ \\  (10^2)^2  &  \equiv 1^2 \pmod {9999} \end{align} $$

Here $10^2 \not \equiv \pm 1 \pmod {9999}$ and so $\gcd(10^2-1,9999)=99$ is a non-trivial factor of 9999.

Here 99 is easier to factor into $99 = 3^2 \times 11$.

And so $9999 =  3^2 \times 11 \times 101$.

(b) We start with $999999=10^6-1= (10^3)^2 - 1^2$.

And so

$$ \begin{align} 999999 & \equiv 0 \pmod {999999} \\ \\  (10^3)^2 - 1^2 & \equiv 0 \pmod {999999} \\ \\ (10^3)^2 & \equiv 1^2 \pmod {999999} \end{align}$$

Here $10^3 \not \equiv \pm 1 \pmod {999999}$ and so $\gcd(10^3-1, 999999) = 999$ is a non-trivial factor of 999999.

Here 999 is easier to factor into $999 = 3^3 \times 37$. Also $999999/999 = 1001 = 7 \times 11 \times 13$.

And so $999999 = 3^3 \times 7 \times 11 \times 13 \times 37$.

(c) (i) We start with $R_4 = 1111 = 9999 / 3^2 $, and using the above factorisation of 9999, we have

$$ R_4 = 1111 = 11 \times 101$$

(ii) We start with $R_6=111111 = 999999 / 3^2$, and using the above factorisation of 999999, we have

$$ R_6 = 111111 = 3 \times 7 \times 11 \times 13 \times 37 $$

Exercise (3.5).13

What type of integer $n$ do we have if $a^2 ≡ b^2 \pmod n ⇒ a ≡ ±b \pmod n$ ?

Proposition 3.14(b) which states that if $p$ is prime, then $a^2 ≡ b^2 \pmod p \iff a ≡ ±b \pmod p$.

So if $a^2 ≡ b^2 \pmod n$ and $n$ is prime, then $a ≡ ±b \pmod n$.

Exercise (3.5).12

Factorise the following integers using modular arithmetic:

(a) 2201 (b) 2189 (c) 9211

We will use the Factorisation Theorem (3.26). 

Let $a$ and $b$ be integers which satisfy the congruence $a^2 ≡ b^2 \pmod n$ and $a ≢ ±b \pmod n$. Then $\gcd (a− b, n)$ is a non-trivial factor of $n$.

(a) We start with $\lceil \sqrt{2201} \rceil = 47$.

The following table shows values $x$ from 47, $x^2-2201$, and the resulting factorisation.

x	x^2-2201	prime factors
47	8	2^3
48	103	103
49	200	2^3, 5^2
50	299	13, 23
51	400	2^4, 5^2
52	503	503
53	608	2^5, 19^1
54	715	5, 11, 13
55	824	2^3, 103

We pick out

$ 47^2 \equiv 2^3 \pmod {2201} $

$ 48^2 \equiv 103 \pmod {2201} $

$ 55^2 \equiv 2^3 \times 103 \pmod {2201} $

Multiplying gives

$ (47 \times 48 \times 55)^2 \equiv (2^3 \times 103)^2 \pmod {2201} $

$ (124080)^2 \equiv (824)^2 \pmod {2201} $

Unfortunately, $124080 \equiv 824 \pmod {2201}$, so we can't use the Factorisation Theorem.

Let's consider multiples of 2201, that is $2201k$.

k	x	x^2-2201k	prime factors
1	47	8	2^3
2	67	87	3, 29
3	82	121	11^2
4	94	32	2^5
5	105	20	2^2, 5
6	115	19	19
7	125	218	2, 109
8	133	81	3^4
9	141	72	2^3, 3^2
10	149	191	191
11	156	125	5^3

We pick out

$ 47^2 \equiv 2^3 \pmod {2201} $

$ 133^2 \equiv 3^4 \pmod {2201} $

$ 141^2 \equiv 2^3 \times 3^2 \pmod {2201} $

Multiplying

$ (47 \times 133 \times 141)^2 \equiv (2^3 \times 3^3)^2 $

Here $ 881391 \not \equiv \pm 216 \pmod {2201}$ so we can use the Factorisation Theorem.

This means $\gcd(881391-216, 2201) = 31$ is a non-trivial factor of $n$. 

This gives us $2201 = 31 \times 71$.

(b) We start with $\lceil \sqrt{2189} \rceil = 47$

The following table shows values $x$ from 47, $x^2-2189$, and the resulting factorisation.

x	x^2-2189	prime factors
47	20	2^2, 5
48	115	5, 23
49	212	2^2, 53
50	311	311
51	412	2^2, 103
52	515	5, 103
53	620	2^2, 5, 31
54	727	727
55	836	2^2, 11, 19
56	947	947
57	1060	2^2, 5, 53
58	1175	5^2, 47

We pick out

$ 47^2 \equiv 2^2 \times 5 \pmod {2189} $

$ 51^2 \equiv 2^2 \times 103 \pmod {2189} $

$ 52^2 \equiv5 \times 103 \pmod {2189} $

Multiplying

$ (47 \times 51 \times 52)^2 \equiv (2^2 \times 5 \times 103)^2 \pmod {2189} $

Unfortunately, $124644 \equiv 2060 \pmod {2189}$ so we can't use the Factorisation Theorem.

Let's consider multiples of 2189, that is $2189k$.

k	x	x^2-2189k	prime factors
1	47	20	2^2, 5
2	67	111	3, 37
3	82	157	157
4	94	80	2^4, 5
5	105	80	2^4, 5

We pick out

$ 47^2 \equiv 2^2 \times 5 \pmod {2189} $

$ 105^2 \equiv 2^4 \times 5 \pmod{2189}  $

Multiplying

$ (47 \times 105)^2 \equiv (2^3 \times 5)^2 \pmod {2189} $

Here $4935 \not \equiv \pm 40 \pmod {2189}$ and so we can use the Factorisation Theorem.

This means $\gcd(4935-40, 2189)=11$ is a non-trivial factor of 2189.

This gives us $2189 = 11 \times 199$.

(c) We start with $\lceil \sqrt{9211} \rceil = 96$

The following table shows values $x$ from 47, $x^2-9211$, and the resulting factorisation.

x	x^2-9211	prime factors
96	5	5
97	198	2, 3^2, 11
98	393	3, 131
99	590	2, 5, 59
100	789	3, 263
101	990	2, 3^2, 5, 11

We pick out

$ 96^2 \equiv 5 \pmod {9211} $

$ 97^2 \equiv 2 \times 3^2 \times 11 \pmod {9211} $

$ 101^2 \equiv 2 \times 3^2 \times 5 \times 11 \pmod{9211} $

Multiplying

$ (96 \times 97 \times 101 )^2 \equiv (2 \times 3^2 \times 5 \times 11 )^2 \pmod {9211} $

Unfortunately, $940512 \equiv 990 \pmod {9211}$ so we can't use the Factorisation Theorem.

Let's consider multiples of 9211,  that is $9211k$

k	x	x^2-9211k	prime factors
1	96	5	5
2	136	74	2, 37
3	167	256	2^8
4	192	20	2^2, 5

We pick out

$ 167^2 \equiv 16^2 \pmod {9211} $

We check that $167 \not \equiv \pm 16 \pmod {9211}$, so we can use the Factorisation Theorem.

This means $\gcd(167-16,9211) = 151$ is a non-trivial factor of 9211.

This gives us $9211 = 151 \times 61$.

Exercise (3.5).11

Factorise the following trapdoor functions (these small numbers are not good candidates for the trapdoor

functions) into two primes:

(a) 411 (b) 2419 (c) 17 947

(a) Since 411 is not too large, we can test primes up to $\sqrt{411}$.

We find that 3 is a factor, leaving, 137. Testing primes up to $\sqrt{137}$ tells us 137 is prime.

So $411 = 3 \times 137$.

(b) $\lceil \sqrt{2419} \rceil = 50$, and $50^2 - 2419 = 9^2$, and so $2419 = (50-9)(50+9) = 41 \times 59$.

So $2419 = 41 \times 59$.

(c) $\lceil \sqrt{17947} \rceil = 134$ and $134^2 - 17947 = 3^2$, and so $17947 = (134+3)(134-3) = 131 \times 137$.

So $17947 = 131 \times 137$.

Exercise (3.5).10

(i) Show that $3^n− 1$ is a composite integer for $n > 1$.

(ii) Show that $x^n− 1$ is a composite integer for $n > 1$ and $x ≥ 3$.

Hint: $a^n− b^n = (a− b) (a^{n−1}+ a^{n−2}b + a^{n−3}b^2 + ⋯ + ab^{n−2} + b^{n−1})$ for $n > 1$.

(i) We can write, for $n>1$,

$$ 3^n-1 = (3-1)(3^{n−1}+ 3^{n−2} + 3^{n−3} + ⋯ + 3 + 1)  $$

This is composite with a factor $(3-1)=2$. 

(ii) We can write, for $n>1$,

$$ x^n -1 = (x− 1) (x^{n−1}+ x^{n−2} + x^{n−3}+ ⋯ + x + 1)  $$

The condition $x \ge 3$ means $x-1 \ge 2$ and so $(x-1)$ is a factor of 2 or more, and so $x^n-1$ is composite.

Exercise (3.5).9

Prove that the only prime of the form $n^2− 1$ is 3, where $n$ is a natural number.

We have

$$n^2-1 = (n+1)(n-1) $$

The only way $(n+1)(n-1)$ is prime and not a composite number is if either $(n+1)$ or $(n-1)$ is 1

Let's consider each case.

• Case $(n+1)=1$ means $n=0$ in which case $(n+1)(n-1)$ is 0, and not a prime.
• Case $(n-1)=1$ means $n=2$ in which case $(n+1)(n-1)=3$.

So the only prime of the form $n^2-1$ is 3.

Exercise (3.5).8

Factorise 53 using the difference of two squares method.

What do you notice about this approach in factorising 53?

We first notice that 53 is prime, but we proceed anyway.

$\lceil \sqrt{53} \rceil = 8$, and $8^2 - 53 = 11$, which is not a perfect square.

Trying many integers incrementing upwards from 8 leads to $27^2 - 53 = 26^2$.

That is, 

$$ 53 = (27+26)(27-26) =  53 \times 1$$

The difference of two squares method leads to a factorisation where one of the factors is 1. 

Note the author's solution states that 53 is a prime that cannot be expressed as the difference of two squares, but we have just shown that it can.