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
[edit | edit source]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
[edit | edit source]Factorise the following numbers. (note: I know you didn't have to, this is just for those who are curious)
- 13 is prime
- 59 is prime
- 101 is prime
Recursive Factorisation Exercises
[edit | edit source]Factorise using recursion.
Prime Sieve Exercises
[edit | edit source]- 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:
- 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
[edit | edit source]- alternatively, -1 = 10, -5 = 6: 10 × 6 = 60 = 5× 11 + 5 = 5
An easier list: 2, 4, 8, 5, 10, 9, 7, 3, 6, 1
Notice that it is not necessary to actually
compute to find mod 11.
If you know mod 11 = 6.
You can find mod 11 = (2*( 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
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 - x^{2} = -2 = 9
Just look at the list above and you'll see that
Division and Inverses Exercises
[edit | edit source]1.
- therefore the inverse does not exist
2.
3.
4.
0 | 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
[edit | edit source]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
[edit | edit source]1.
- There is no solution, because can never become an integer.
2.
- 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
[edit | edit source]1.
Question 1
[edit | edit source]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
if and only if a + b + c = 3k for some k. But a, b and c are the digits of x.
Question 2
[edit | edit source]"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
[edit | edit source]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
[edit | edit source]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
[edit | edit source]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