Determine the least non-negative remainder when $3^{2013}$ is divided by 43.
We want to solve
$$ 3^{2013} \equiv a \pmod {43} $$
Since 43 is prime and does not divide 3, we can use the FlT,
$ 3^{42} \equiv 1 \pmod {43} $
And so
$ 3^{2013} \equiv (3^{42})^{47} \times 3^{39} \equiv 3^{39} \pmod {43} $
We also use $3^{12} \equiv 4 \pmod {43}$
$ 3^{2013} \equiv (3^{12})^3 \times 3^3 \equiv 4^3 \times 3^3 \equiv 8 \pmod {43} $
So the remainder is 8 when $3^{2013}$ is divided by 43.
(i) Let $p$ be prime and $p \not \mid n$. Prove that the solutions of $nx \equiv a \pmod p$ is
given by
$$ x \equiv n^{p−2}a \pmod p $$
(ii) Solve the linear congruence
$$ 10x \equiv 11 \pmod {17}$$
(i) Since $p$ is prime, and does not divide $n$, we can use FlT
$ n^{p-1} \equiv 1 \pmod p $
Multiplying both sides by $a$
$ n^{p-1}a \equiv a \pmod p $
That is
$ n ( n^{p-2}a) \equiv a \pmod p $
Comparing this to $nx \equiv a \pmod p$ tells us $x \equiv n^{p-2}a \pmod p$.
(ii) Using the result from (i) we have
$ x \equiv 10^{15} \times 11 \pmod {17} $
Using $10^5 \equiv 100000 \equiv 6 \pmod {17}$, we have
$ x \equiv ({10^ 5})^3 \times 11 \equiv 6^3 \times 11 \equiv 2376 \equiv 13 \pmod {17} $
That is,
$ x \equiv 13 \pmod {17} $
Prove the following:
(a) $1^{p−1} + 2^{p−1} + 3^{p−1} + \ldots + (p−1)^{p−1} \equiv −1 \pmod p$
where $p$ is prime.
(b) $1^p + 2^p + 3^p + \ldots + (p− 1)^p \equiv 0 \pmod p$
where $p$ is an odd prime.
You may find the following result helpful: $1 + 2 + 3 + \ldots + n = \frac{n(n+1)}{2}$
(a) All the numbers $1, 2, 3, \ldots, (p-1)$ are not divisible by the prime $p$. This means we can apply FlT.
$$ \begin{align} 1^{p−1} + 2^{p−1} + 3^{p−1} + \ldots + (p−1)^{p−1} & \equiv 1 + 1 + 1 + \ldots + 1 \pmod p \\ \\ & \equiv (p-1) \pmod p \\ \\ & \equiv -1 \pmod p \end{align} $$
(b) Using Corollary 4.2, which says that for any integer $a$ and prime $p$, we have $a^p \equiv a \pmod p$.
This gives us
$$ \begin{align} 1^p + 2^p + 3^p + \ldots + (p− 1)^p & \equiv 1 + 2 + 3 + \ldots + (p− 1) \pmod p \\ \\ & \equiv \frac{(p-1)(p)}{2} \pmod p \\ \\ & \equiv kp \pmod p \\ \\ & \equiv 0 \pmod p\end{align} $$
where $k = \frac{p-1}{2}$ is an integer since $p$ is odd.
Find a solution of $x^{101} ≡ 5 \pmod {13}$.
There are two cases to consider: 13 divides $x$ and 13 does not divide $x$. In the first case, there is no solution because then $x \equiv 0 \pmod {13} \implies x^{101} \equiv 0 \pmod {13}$.
So we are left with the second case where 13 does not divide $x$. This means we can use the FlT, and so we have
$x^{12} \equiv 1 \pmod {13}$
$(x^{12})^{8} \equiv x^{96} \equiv 1 \pmod {13}$
And so
$x^{101} \equiv x^{96} \times x^{5} \equiv x^5 \equiv 5 \pmod {13}$
The following table shows some $x^5 \pmod{13}$.
| x | x^5 | x^5 mod 13 |
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 32 | 6 |
| 3 | 243 | 9 |
| 4 | 1024 | 10 |
| 5 | 3125 | 5 |
| 6 | 7776 | 2 |
We can see $x=5$ is a solution, and our assumption 13 does not divide $x=5$ holds.
Given that $2^{1234566} ≡ 899557 \pmod {1 234 567}$, is the number $1234567$ composite or prime?
The FlT says that if $p$ is prime and doesn't divide $a$, then $a^{p-1} \equiv 1 \pmod p$.
This is a statement of the form $P \implies Q$. If this is true, then the contrapositive is also true, $\neg Q \implies \neg P$.
The contrapositive here states that if $a^{p-1} \not \equiv 1 \pmod p$ then ($p$ is not prime or $p$ divides $a$).
We have that $a^{p-1} \not \equiv 1 \pmod p$, but $p \not \mid a$, and so it must be the case that $p$ is not prime.
Show that
$$ 7^{40 353 606} \equiv 0 \pmod {40 353 607} $$
Is $40 353 607$ prime?
Trial and error leads us to
$7^9 \equiv 40353607 \equiv 0 \pmod {40353607}$
We also have $40353606 = 9 \times 4483734$. And so
$7^{40353606} \equiv (7^9)^{4483734} \equiv 0^{4483734} \equiv 0 \pmod {40353607}$
We have shown above that 40353607 has factors of 7, and so is not a prime.
Show that $2^{2046} ≡ 1 \pmod {2047}$. Check whether 2047 is prime.
We start with $2^{11} = 2048$, and so
$ 2^{11} \equiv 1 \pmod {2047} $
$ 2^{2046} \equiv (2^{11})^{186} \equiv 1 \pmod {2047}$.
2047 is not prime since $2047 = 23 \times 89$.
(a) Show that $2^{8190} ≡ 1 \pmod {8191}$. What can you say about the number 8191?
(b) Show that $2^{65536} ≡ 1 \pmod {65537}$. What can you say about the number 65537?
(a) From experience we know that 8192 is a power of 2. In fact, $2^{13} = 8192$. And so
$2^{13} \equiv 1 \pmod {8191}$
$ 2^{8190} \equiv (2^{13})^{630} \equiv 1 \pmod {8191}$
This suggests 8191 is a candidate for being a prime.
(b) Similarly, we know that $2^{16}=65536$ and so
$ 2^{16} \equiv -1 \pmod {65537} $
$ 2^{65536} \equiv (2^{16})^{4096} \equiv 1 \pmod {65537} $
This suggests 65537 is a candidate for being a prime.
(i) Find $8^{21} \pmod {23}$.
(ii) Solve the equation $8x ≡ 7 \pmod {23}$.
(i) Since 23 is a prime, and does not divide 8, we can use the FlT.
$ 8^{22} \equiv 1 \pmod {23} $
$ 8^{21} \times 8 \equiv 1 \pmod {23} $
By inspection we can see that $8^{21} \equiv 3 \pmod {23}$ gives us $3 \times 8 \equiv 24 \equiv 1 \pmod {23}$.
And so $8^{21} \equiv 3 \pmod {23}$.
(ii) From above we have $ 8^{21} \times 8 \equiv 1 \pmod {23} $ and $8^{21} \equiv 3 \pmod {23}$, and so
$ 3 \times 8 \equiv 1 \pmod {23} $
$ 3 \times 8 \times 7 \equiv 7 \pmod {23} $
Which gives us $x \equiv 21 \pmod {23}$.
(i) Determine the remainder when $6^{2014}$ is divided by 11.
(ii) Determine the remainder when $6^{2013}$ is divided by 11.
(i) We need to solve
$$ 6^{2014} \equiv x \pmod {11} $$
Since 11 is prime, and does not divide 6, we have by FlT
$ 6^{10} \equiv 1 \pmod {11} $
And so
$ 6^{2014} \equiv (6^{10})^{201} \times 6^4 \equiv 6^4 \equiv 1296 \pmod {11} $
$ 6^{2014} \equiv 9 \pmod {11} $
So the remainder when $6^{2014}$ is divided by 11 is 9.
(ii) This is very similar to the above. The difference leads to
$ 6^{2013} \equiv (6^{10})^{201} \times 6^3 \equiv 6^3 \equiv 216 \pmod {11} $
$ 6^{2013} \equiv 7 \pmod {11} $
So the remainder when $6^{2013}$ is divided by 11 is 7.
Determine the multiplicative inverse of the following numbers by using Fermat’s Little Theorem. Give your answer as the least non-negative residue.
(a) $5 \pmod {11}$
(b) $9 \pmod {23}$
(c) $2 \pmod {37}$
(d) $5 \pmod {41}$
For integer $a$ and prime $p$, where $p \not \mid a$, we have
$$ a^{p-1} \equiv 1 \pmod p \; \implies \; a(a^{p-2}) \equiv 1 \pmod p \; \implies \; a^{-1} \equiv a^{p-2} \pmod p $$
(a) Here 11 is prime, and does not divide 5, and so
$ 5^{-1} \equiv 5^{9} \pmod {11} $
Using $5^3 \equiv 125 \equiv 4 \pmod {11}$, we have
$ 5^{-1} \equiv (5^{3})^3 \equiv 4^3 \equiv 64 \pmod {11} $
$ 5^{-1} \equiv 9 \pmod {11} $
(b) Here 23 is prime, and does not divide 9, and so
$ 9^{-1} \equiv 9^{21} \pmod {23} $
Using $9^7 \equiv 4782969 \equiv 4 \pmod {23}$, we have
$ 9^{-1} \equiv (9^{7})^3 \equiv 64 \pmod {23} $
$ 9^{-1} \equiv 18 \pmod {23} $
(c) Here 37 is prime, and does not divide 2, and so
$ 2^{-1} \equiv 2^{35} \pmod {37} $
Using $2^7 \equiv 128 \equiv 17 \pmod {37}$, we have
$ 2^{-1} \equiv (2^{7})^5 \equiv 17^5 \pmod {37} $
Using $17^2 \equiv 289 \equiv 30 \pmod {37}$, we have
$ 2^{-1} \equiv (17^2)^2 \times 17 \equiv 30^2 \times 17 \equiv 15300 \pmod {37} $
$ 2^{-1} \equiv 19 \pmod {37} $
(d) Here 41 is prime, and does not divide 5, and so
$ 5^{-1} \equiv 5^{39} \pmod {41}$
Using $5^{13} \equiv 1220703125 \equiv 39 \pmod {41}$, we have
$ 5^{-1} \equiv (5^{13})^3 \equiv 39^3 \equiv 59319 \pmod {41}$
$ 5^{-1} \equiv 33 \pmod {41} $
Determine the least non-negative residue $x$ of the following congruences:
(a) $7^{101} ≡ x \pmod {11}$
(b) $2^{1976} ≡ x \pmod {13}$
(c) $5^{1961} ≡ x \pmod {7}$
(d) $3^{2013} ≡ x \pmod {23}$
(e) $26^{2013} ≡ x \pmod {23}$
We remind ourselves of Fermat's Little Theorem (FlT). For integer $a$ and prime $p$, where $p \not \mid a$, we have
$$ a^{p-1} \equiv 1 \pmod {p} $$
(a) Since 11 is prime, and doesn't divide 7, we can use the FlT.
$ 7^{10} \equiv 1 \pmod {11} $
$ (7^{10})^{10} \equiv 1^{10} \pmod {11} $
$ 7^{100} \equiv 1 \pmod {11} $
$ 7^{100} \times 7 \equiv 7 \pmod {11} $
$ 7^{101} \equiv 7 \pmod {11} $
(b) Since 13 is prime, and doesn't divide 2. we can use the FlT.
$ 2^{12} \equiv 1 \pmod{13} $
$ (2^{12})^{164} \equiv 1 \pmod{13} $
$ 2^{1968} \times 2^8 \equiv 256 \equiv 9 \pmod{13} $
$ 2^{1976} \equiv 9 \pmod {13} $
(c) Since 7 is prime, and doesn't divide 5, we can use the FlT.
$ 5^{6} \equiv 1 \pmod 7 $
$ (5^{6})^{326} \equiv 1 \pmod 7 $
$ 5^{1956} \times 5^5 \equiv 3125 \equiv 3 \pmod 7 $
$ 5^{1961} \equiv 3 \pmod 7 $
(d) Since 23 is prime, and doesn't divide 3, we can use the FlT.
$ 3^{22} \equiv 1 \pmod {23} $
$ (3^{22})^{91} \equiv 1 \pmod {23} $
$ 3^{2002} \times 3^{11} \equiv 177147 \equiv 1 \pmod {23} $
$ 3^{2013} \equiv 1 \pmod {23} $
(d) We first note that
$ 26 \equiv 3 \pmod {23} $
$ 26^{2013} \equiv 3^{2013} \equiv 1 \pmod {23} $ using (d) above.
Determine the prime decomposition of
$$ 8^8 − 1 = 16 777 215 $$
We have
$$ \begin{align} 16 777 215 & = (8^4-1)(8^4+1) \\ \\ & = (8^2-1)(8^2+1) \times 4097 \\ \\ & = 63 \times 65 \times 4097 \end{align} $$
We can factorise these separately
$ 63 = 3^2 \times 7 $
$ 65 = 5 \times 13 $
$ 4097 = 17 \times 241 $
And so
$$ 8^8 -1 = 3^2 \times 5 \times 7 \times 13 \times 17 \times 241 $$
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 $$
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$.
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$.
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$.
(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.
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.
So the only prime of the form $n^2-1$ is 3.
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.
(i) Factorise 3397301 (you don’t need to factorise this into prime factors).
(ii) Solve $x^2 + 164x− 3 397 301 = 0$ without using the quadratic formula.
(i) $\lceil \sqrt{3397301} \rceil = 1844$, and $1844^2 - 3397301 = 3035$ which is not a perfect square.
$1845^2 - 3397301 = 82^2$, and so $3397301 = (1845-82)(1845+82) = 1927 \times 1763$.
The factorisation $3397301 = 1927 \times 1763$ is sufficient.
(ii) We notice that $1927-1763=164$, we have
$$ \begin{align} 0 & = x^2 + 164x - 3397301 \\ \\ & = x^2 +(1927-1763)x - (1927 \times 1763) \\ \\ &= (x+1927)(x-1763) \end{align} $$
And so the solutions are $x=-1927$ and $x+1763$.
Factorise $18 861 649$. Hence or otherwise solve the quadratic
$$ x^2 − 18 861 649 = 0$$
We find that $\sqrt{18861649} = 4343$ exactly. So we can work on 4343.
$\lceil \sqrt{4343} \rceil = 66$, and $66^2 - 4343 = 13$ which is not a perfect square.
By additional trials we find $72^2 - 4343 = 29^2$, and so $4343 = (72-29)(72+29) = 43 \times 101$.
So the factorisation is $18861649 = 43^2 \times 101^2$.
Using the above factorisation we have
$$ \begin{align} 0 & = x^2 - 18861649 \\ \\ &= x^2 - (43 \times 101)^2 \\ \\ & = (x - 4343)(x+4343) \end{align} $$
And so $x = \pm 4343$.
(i) Factorise each of the following integers:
(a) 713 (b) 1271 (c) 403
(ii) Solve the quadratic equation
$$ 403x^2 + 1271x + 713 = 0 $$
leaving your answer in surd form.
(iii) Simplify the following fractions:
$$ \frac{713}{1271}, \quad \frac{403}{1271}, \quad \frac{403}{713} $$
(i) (a) We have $\lceil \sqrt{713} \rceil = 27$, and $27^2 - 713 = 4^2$, and so $713 = (27-4)(27+4) = 23 \times 31$.
The factorisation is $713 = 23 \times 31$.
(b) $\lceil \sqrt{1271} \rceil = 36$, and $36^2 - 1271 = 5^2$, and so $1271 = (36-5)(36+5) = 31 \times 41$.
The factorisation is $1271 = 31 \times 41$
(c) $\lceil \sqrt{403} \rceil = 21$, and $21^2 - 403 = 38$, which is not a perfect square.
$22^2 - 403 = 9^2$, and so $403 = (22-9)(22+9) = 13 \times 31$.
The factorisation is $403 = 13 \times 31$
(ii) We can use the factorisations above
$$ \begin{align} 0 & = 403x^2 + 1271x + 713 \\ \\ & = (13 \cdot 31)x^2 + (31 \cdot 41)x + (23 \cdot 31) \\ \\ & = 13x^2 +41x +23 \end{align} $$
Using the general solution $x= \frac{-b \pm \sqrt{b^2-4ac}}{2a}$, we have
$$ \begin{align} x & = \frac{-41 \pm \sqrt{41^2-4(13)(23)}}{2(41)} \\ \\ x & = \frac{-41 \pm \sqrt{485}}{26} \end{align} $$
(iii) $$ \frac{713}{1271} = \frac{23 \cdot 31}{31 \cdot 41} = \frac{23}{41}$$
$$ \frac{403}{1271} = \frac{13 \cdot 31}{31 \cdot 41} = \frac{13}{41} $$
$$ \frac{403}{713} = \frac{13 \cdot 31}{23 \cdot 31} = \frac{13}{23} $$
Factorize 1 236 519.
$\lceil \sqrt{1236519} \rceil = 1112$, and $1112^2 - 1236519 = 5^2$, and so $1236519 = 1112^2 0 5^2 = (1112+5)(1112-5) = 1117 \times 1107$.
We notice that the digits of 1107 sum to 9, and so is divisible by 9. In fact, we find it is divisible by 27, leaving prime 41. We also find the 1117 is prime, by testing up to $\sqrt{1117}$.
So the factorisation is $1236519 = 3^3 \times 41 \times 1117$.
Let $n$ be an odd integer. Show that
$$ \left( \frac{n+1}{2} \right )^2 - \left( \frac{n-1}{2} \right )^2 = n $$
$$ \begin{align} \left( \frac{n+1}{2} \right )^2 - \left( \frac{n-1}{2} \right )^2 & = \left( \frac{n^2 + 2n +1}{4} \right ) - \left( \frac{n^2 -2n +1}{4} \right ) \\ \\ & = \left( \frac{4n}{4} \right ) \\ \\ & = n \end{align} $$
Factorise the following into their prime factors:
(a) 9271 (b) 2146 (c) 2 974 791
(a) $\lceil \sqrt{9271} \rceil = 97$, and $ 97^2 - 9271 = 138 $, which is not a perfect square.
$ 98^2 - 9271 = 333 $, which is not a perfect square.
$ 99^2 - 9271 = 530 $, which is not a perfect square.
$ 100^2 - 9271 = 27^2 $, and so $9271 = 100^2 - 27^2 = (100-27)(100+27) = 73 \times 127$.
The prime factorisation is $9271 = 73 \times 127$.
(b) Since 2146 is even, we can factor out 2, and work on the odd 1073.
$\lceil \sqrt{1073} \rceil = 33$, and $ 33^2 - 1073 = 4^2 $, and so $1073 = 33^2 - 4^2 = (33+4)(33-4) = 37 \times 29$.
The prime factorisation is $2146 = 2 \times 29 \times 37$.
(c) The Fermat factorisation approach doesn't yield easy results for several trials and so we reduce the number by factoring out 3, and working on 991597 as a smaller odd number.
$\lceil \sqrt{991597} \rceil = 996$, and $996^2 - 991597 = 419$ which is not a perfect square.
We keep trying until we find $1001^2 - 991597 = 102^2$, and so $991597 = 1001^2 - 102^2 = (1001 - 102)(1001 + 102) = 1103 \times 899 = 1103 \times 29 \times 31 $.
The prime factorisation is $2974791 = 3 \times 29 \times 31 \times 1103$.
Factorise the following integers into their prime factors:
(a) 299 (b) 851 (c) 10403 (d) 2479
We will use Fermat difference of two squares factorisation method.
(a) $\lceil \sqrt(299) \rceil = 18$, and $18^2-299 = 5^2$.
So $299 = 18^2 - 5^2 = (18+5)(18-5) = 23 \times 13$.
So the prime factorisation is $299=23 \times 13$.
(b) $\lceil \sqrt(851) \rceil = 30$, and $30^2-851 = 7^2$.
So $851 = 30^2 - 7^2 = (30+7)(30-7) = 37 \times 23$.
So the prime factorisation is $851 = 37 \times 23$.
(c) $\lceil \sqrt(10403) \rceil = 102$, and $102^2-10403 = 1^2$.
So $10403 = (102^2+1)(102^2-1) = 103 \times 101$.
So the prime factorisation is $10403 = 103 \times 101$.
(d) $\lceil \sqrt(2479) \rceil = 50$, and $50^2-2479 = 21$ which is not a perfect square.
So we try $51^2-2479=122$, also not a perfect square.
So we try $52^2 - 2479 = 15^2$, and so $2479 = 52^2 - 15^2 = (52+15)(52-15)= 67 \times 37$.
So $2479 = 67 \times 37$.