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$.