# High School Mathematics Extensions/Primes/Solutions

* HSME
* Content
* Primes
* Modular Arithmetic
* Problems & Projects
* Problem Set
* Project
* Solutions
* Exercise Solutions
* Problem Set Solutions
* Misc.
* Definition Sheet
* Full Version
* PDF Version

## HSE Primes|Primes and Modular Arithmetic

At the moment, the main focus is on authoring the main content of each chapter. Therefore this exercise solutions section may be out of date and appear disorganised.
If you have a question please leave a comment in the "discussion section" or contact the author or any of the major contributors.

### Factorisation Exercises

Factorise the following numbers. (note: I know you didn't have to, this is just for those who are curious)
* 13 is prime
* $26=13\cdot 2$
* 59 is prime
* $82=41\cdot 2$
* 101 is prime
* $121=11\cdot 11$
* $2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3$

### Recursive Factorisation Exercises

Factorise using recursion.
* $45=3\cdot 3\cdot 5$
* $4050=2\cdot 3\cdot 3\cdot 3\cdot 3\cdot 5\cdot 5$
* $2187=3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3\cdot 3$

### Prime Sieve Exercises

* Use the above result to quickly work out the numbers that still need to be crossed out in the table below, knowing 5 is the next prime:
    ${\begin{matrix}X&2_{p}&3_{p}&X&5&X&7&X&X&X\\11&X&13&X&X&X&17&X&19&X\\X&X&23&X&25&X&X&X&29&X\\31&X&X&X&35&X&37&X&X&X\\41&X&43&X&X&X&47&X&49&X\\\end{matrix}}$
    The next prime number is 5. Because 5 is an unmarked prime number, and 5 * 5 = 25, cross out 25. Also, 7 is an unmarked prime number, and 5 * 7 = 35, so cross off 35. However, 5 * 11 = 55, which is too high, so mark 5 as prime ad move on to 7. The only number low enough to be marked off is 7 * 7, which equals 49. You can go no higher.
2. Find all primes below 200.
    The method will not be outlined here, as it is too long. However, all primes below 200 are:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199

### Modular Arithmetic Exercises

* $(-1)\cdot (-5)\mod {11}=5$alternatively, -1 = 10, -5 = 6: 10 × 6 = 60 = 5&times 11 + 5 = 5
* $3\cdot 7\mod {11}=21=10$
* $2^{1}=2,2^{2}=4,2^{3}=8,2^{4}=16=5$ $2^{5}=32=10,2^{6}=64=9,2^{7}=128=7$ $2^{8}=256=3,2^{9}=512=6,2^{10}=1024=1$ An easier list: 2, 4, 8, 5, 10, 9, 7, 3, 6, 1 Notice that it is not necessary to actually compute $2^{10}$ to find $2^{10}$ mod 11. If you know $2^{9}$ mod 11 = 6. You can find $2^{10}$ mod 11 = (2*($2^{9}$ mod 11)) mod 11 = 2*6 mod 11 = 12 mod 11 = 1. We can note that 2$^9$ = 6 and 2$^{10}$ = 1, we can calculate 6$^2$ easily: 6$^2$ = 2$^{18}$ = 2^8 = 3. OR by the above method $6^{1}=6,6^{2}=36=3,6^{3}=6*3=18=7,$ $6^{4}=6*7=42=9,6^{5}=6*9=54=10,6^{6}=6*10=60=5,$ $6^{7}=6*5=30=8,6^{8}=6*8=48=4,6^{9}=6*4=24=2,6^{10}=6*2=12=1.$ An easier list: 6, 3, 7, 9, 10, 5, 8, 4, 2, 1.
* 0$^2$ = 0, 1$^2$ = 1, 2$^2$ = 4, 3$^2$ = 9, 4$^2$ = 16 = 5, 5$^2$ = 25 = 5, 6$^2$ = 36 = 3, 7$^2$ = 49 = 3, 8$^2$ = 64 = 9, 9$^2$ = 81 = 4, 10$^2$ = 100 = 1 An easier list: 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1 Thus${\sqrt {4}}=2{\mbox{ and }}{\sqrt {4}}=9$
* x$^2$ = -2 = 9 Just look at the list above and you'll see that${\sqrt {-2}}=8{\mbox{ and }}{\sqrt {-2}}=3$

### Division and Inverses Exercises

1.
    $x=2^{-1}=4$
    $x=3^{-1}=5$
    $x=4^{-1}=2$
    $x=5^{-1}=3$
    $x=6^{-1}=6$
    $x=7^{-1}=0^{-1}$ therefore the inverse does not exist
2. $x={\frac {28}{7}}=4\ \ {\mbox{(mod 29)}}$
    $7^{-1}=25\ \ {\mbox{(mod 29)}}$
    $x=28\cdot 25=4\ \ {\mbox{(mod 29)}}$
3.
    $x=5^{99}\times (40+{\frac {1}{3}})\ \ {\mbox{(mod 11)}}$
    $x=5^{99}\times (40+4)\ \ {\mbox{(mod 11)}}$
    $x=5^{99}\times 0\ \ {\mbox{(mod 11)}}$
    $x=0\ \ {\mbox{(mod 11)}}$
4.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
| 1 | | | | | | | | | | | | | | | | | | mod 2 |
| 1 | 2 | | | | | | | | | | | | | | | | | mod 3 |
| 1 | | 3 | | | | | | | | | | | | | | | | mod 4 |
| 1 | 3 | 2 | 4 | | | | | | | | | | | | | | | mod 5 |
| 1 | | | | 5 | | | | | | | | | | | | | | mod 6 |
| 1 | 4 | 5 | 2 | 3 | 6 | | | | | | | | | | | | | mod 7 |
| 1 | | 3 | | 5 | | 7 | | | | | | | | | | | | mod 8 |
| 1 | 5 | | 7 | 2 | | 4 | 8 | | | | | | | | | | | mod 9 |
| 1 | | 7 | | | | 3 | | 9 | | | | | | | | | | mod 10 |
| 1 | 6 | 4 | 3 | 9 | 2 | 8 | 7 | 5 | 10 | | | | | | | | | mod 11 |
| 1 | | | | 5 | | 7 | | | | 11 | | | | | | | | mod 12 |
| 1 | 7 | 9 | 10 | 8 | 11 | 2 | 5 | 3 | 4 | 6 | 12 | | | | | | | mod 13 |
| 1 | | 5 | | 3 | | | | 11 | | 9 | | 13 | | | | | | mod 14 |
| 1 | 8 | | 4 | | | 13 | 2 | | | 11 | | 7 | 14 | | | | | mod 15 |
| 1 | | 11 | | 13 | | 7 | | 9 | | 3 | | 5 | | 15 | | | | mod 16 |
| 1 | 9 | 6 | 13 | 7 | 3 | 5 | 15 | 2 | 12 | 14 | 10 | 4 | 11 | 8 | 16 | | | mod 17 |
| 1 | | | | 11 | | 13 | | | | 5 | | 7 | | | | 17 | | mod 18 |
| 1 | 10 | 13 | 5 | 4 | 16 | 11 | 12 | 17 | 2 | 7 | 8 | 3 | 15 | 14 | 6 | 9 | 18 | mod 19 |

### Coprime and greatest common divisor Exercises

1.
    1.
| smaller | larger |
| 5050 | 5051 |
| 1 | 5050 |
| 0 | 1 |
       5050 and 5051 are coprime
    2.
| smaller | larger |
| 59 | 78 |
| 19 | 59 |
| 2 | 19 |
| 1 | 2 |
| 0 | 1 |
       59 and 79 are coprime
    3.
| smaller | larger |
| 111 | 369 |
| 36 | 111 |
| 3 | 36 |
| 0 | 3 |
       111 and 369 are not coprime
    4.
| smaller | larger |
| 2021 | 4032 |
| 2011 | 2021 |
| 10 | 2011 |
| 1 | 10 |
| 0 | 1 |
       2021 and 4032 are coprime
2. We first calculate the gcd for all combinations
| smaller | larger |
| 15 | 510 |
| 0 | 15 |
| smaller | larger |
| 15 | 375 |
| 0 | 15 |
| smaller | larger |
| 375 | 510 |
| 135 | 375 |
| 105 | 135 |
| 30 | 105 |
| 15 | 30 |
| 0 | 15 |
    The gcd for any combination of the numbers is 15 so the gcd is 15 for the three numbers.

### Diophantine equation Exercises

1.
    ${\begin{matrix}216x&=&1+816b\\216c&=&1+168b\\48c&=&1+168d\\48e&=&1+24d\\24e&=&1+24f\\\end{matrix}}$
    There is no solution, because can never become an integer.
2.
    ${\begin{matrix}42x&=&7+217b\\42c&=&7+7b\\7c&=&0+7d\\\end{matrix}}$
    We choose d=1, then x=26.
3.
    (a)
| smaller | larger | PQ |
| 33 | 101 | 3 |
| 2 | 33 | 16 |
| 1 | 2 | 2 |
| 0 | 1 | |
| | | 3 | 16 | 2 |
| 0 | 1 | 3 | 49 | 101 |
| 1 | 0 | 1 | 16 | 33 |
    (b) To be added
4.
    (a)
| smaller | larger | PQ |
| 17 | 317 | 18 |
| 11 | 17 | 1 |
| 6 | 11 | 1 |
| 5 | 6 | 1 |
| 1 | 5 | 5 |
| 0 | 1 | |
| | | 18 | 1 | 1 | 1 | 5 |
| 0 | 1 | 18 | 19 | 37 | 56 | 317 |
| 1 | 0 | 1 | 1 | 2 | 3 | 17 |
       (b) To be added

### Chinese remainder theorem exercises

1.
    ${\begin{matrix}3x&\equiv &5{\pmod {14}}\\x&\equiv &11{\pmod {14}}\\x&=&11+14a\\2x&=&2(11+14a)&\equiv &-3{\pmod {17}}\\&&22+28a&\equiv &-3{\pmod {17}}\\&&11a&\equiv &-8{\pmod {17}}\\&&a&=&7+17b\\x&=&11+14(7+17b)&\equiv &6{\pmod {15}}\\&=&109+238b&\equiv &6{\pmod {15}}\\&=&4+13b&\equiv &6{\pmod {15}}\\&=&13b&\equiv &2{\pmod {15}}\\&&b&\equiv &14{\pmod {15}}\\&&b&=&14+15c\\x&=&109+238(14+15c)\\x&=&3441+3570c\end{matrix}}$

### Question 1

Show that the divisible-by-3 theorem works for any 3 digits numbers (Hint: Express a 3 digit number as 100a + 10b + c, where a, b and c are ≥ 0 and < 10)
Solution 1 Any 3 digits integer x can be expressed as follows
    x = 100a + 10b + c
where a, b and c are positive integer between 0 and 9 inclusive. Now
    $x\equiv 100a+10b+c\equiv a+b+c{\pmod {3}}$
    $x\equiv 0{\pmod {3}}$
if and only if a + b + c = 3k for some k. But a, b and c are the digits of x.

### Question 2

"A number is divisible by 9 if and only if the sum of its digits is divisible by 9." True or false? Determine whether 89, 558, 51858, and 41857 are divisible by 9. Check your answers.
Solution 2 The statement is true and can be proven as in question 1.

### Question 4

The prime sieve has been applied to the table of numbers above. Notice that every number situated directly below 2 and 5 are crossed out. Construct a rectangular grid of numbers running from 1 to 60 so that after the prime sieve has been performed on it, all numbers situated directly below 3 and 5 are crossed out. What is the width of the grid?
Solution 4 The width of the grid should be 15 or a multiple of it.

### Question 6

Show that n - 1 has itself as an inverse modulo n.
Solution 6
    (n - 1)$^2$ = n$^2$ - 2n + 1 = 1 (mod n)
Alternatively
    (n - 1)$^2$ = (-1)$^2$ = 1 (mod n)

### Question 7

Show that 10 does not have an inverse modulo 15.
Solution 7 Suppose 10 does have an inverse x mod 15,
    10x = 1 (mod 15)
    2×5x = 1 (mod 15)
    5x = 8 (mod 15)
    5x = 8 + 15k
for some integer k
    x = 1.6 + 3k
but now x is not an integer, therefore 10 does not have an inverse