Essential Mathematics: Number Theory

Open University

67 flashcards · Mathematics · by lakesare

1. Try to divide 38 by 5, and show quotient and remainder.

   38 = 7 (quotient) * 5 + 3 (remainder)

2. Try to divide (-38) by 5, and show quotient and remainder.

   -38 = (-8) (quotient) * 5 + 2 (remainder) Remainder is always positive!

3. Why is remainder defined to be always positive?

   To simplify Euclid's algorithm. This time, the quotient is negative (the first eight jumps are to the left, rather than to the right), but it is chosen so that the remainder is still positive. The reason why we choose the quotient in this way to give a positive remainder is because this choice simplifies Euclid’s algorithm, which you’ll meet in the next subsection.

4. Name 2 ways to find the highest common factor (HCF) of two numbers. Also known as GCD (Greatest Common Divisor)

   1. Prime factorization Perform prime factorization of both numbers, and multiply together the lowest power of each prime (including 0 powers).2. Euclid's algorithm Divide a by b,then divide b by prev_remainderthen divide prev_prev_remainder by prev_remainderthen divide prev_prev_remainder by prev_remainderthen divide prev_prev_remainder by prev_remainderthen divide prev_prev_remainder by prev_remainderAnd in the end the second-before-last remainder will be our HCF. E.g., to find HCF(207, 60):

5. What is the essence of the Euclid's algorithm (for finding the highest common factor)?

   The idea is that remainder always has the highest common divisor in it, - and we're reducing our remainder with each step, distilling out our hcf. hcf(78, 66) = hcf(66, 12) = hcf(12, 6)

6. Find the highest common factor of 209 and 78 using Euclid's algorithm.

7. Explain Bezout's identity: av + bw = d.

   a, b - nonzero integers. d - hcf(a, b) Integers v and w exist (to satisfy this equation).

8. What's Bezout's identity for hcf(207, 60) given this is the Euclid's algorithm? [no need for solution, just give the form]

   207 v + 60 w = 3

9. Name 2 steps to find integers v and w that satisfy Bezout's identity.

   Find hcf by Euclid's algorithm (highest common factor) Back substitute all numbers except for a and b, so that we have d = a*some_number + b*some_number.

10. Find the highest common factor d of 185 and 49, and then find integers v and w such that 185v + 49w = d.

    185 × (−9) + 49 × 34 = 1. 1. Euclid's algorithm gives 185 = 3 × 49 + 38 49 = 1 × 38 + 11 38 = 3 × 11 + 5 11 = 2 × 5 + 1 5 = 5 × 1 + 0. So the highest common factor of 185 and 49 is 1.2. Use backwards substitution to find integers v and w with 185v + 49w = 1. So 185 × (−9) + 49 × 34 = 1.

11. [Finding integers v and w with av + bw = d when a and b are not both positive] How to find integers v and w, when a or b are not positive? E.g. find the highest common factor d of 126 and −33, and then find integers v and w such that 126v − 33w = d.

    Just find hcf(126, 33) - it's the same with hcf(126, -33)! Back substitute as usual, - just don't forget to change the sign of v or w in the end.

12. When are two integers a and b congruent modulo n?

    If they each have the same remainder on division by n.

13. Name 2 ways to check the congruence -8 ≡ 10 (mod 6).

    1. Because -8 = 6 * (-2) + 4 10 = 6 * 1 + 4 2. Because -8 - 10 = 6 * 3 + 0 Quotients and remainders are in orange.

14. Express in notation the 'residue class of a modulo n'.

    { b | a ≡ b (mod n) } A residue class of 'a mod n' is a set of all integers congruent to a (mod n).

15. Another name for residue class?

    Congruence class.

16. Why do we call the congruence class a residue class?

    'Residue' means 'remainder'. Residue class is all integers that have the same remainder as a when divided by n. This term is used because the residue class of a modulo n is the class of those integers that have the same remainder on division by n as a does.

17. Plot: residue class of 1 modulo 3 residue class of 1 modulo 4

    Residue class of 1 modulo 3 Residue class of 1 modulo 4

18. What's the least residue of a modulo n?

    a % n. Simply the remainder! The least residue of a modulo n is the remainder r that you obtain when you divide a by n.

19. Find the least residue of −33 modulo 7.

    −33 % 7 = 2. Because 33 = 7 * (−5) + 2

20. What's the simple description for the residue class of 1 mod 3?

    All integers congruent to 1 mod 3.

21. Here is a plot of the residue class of −1 modulo 4 on a number line. What's the least residue of −1 modulo 4?

    −1 % 4 = 3. 'Least residue' is the smallest (nonnegative) element of the residue class - which is naturally the remainder.

22. Name 2 most famous Fermat's theorems. Pierre de Fermat

    Fermat's Last Theorem - about integer solutions to an + bn = cn Fermat's Little Theorem - about congruence modulo primeNumber The theorem is named after Pierre de Fermat, who stated it in 1640. It is called the "little theorem" to distinguish it from Fermat's last theorem.

23. What's the common thread between congruency rules?

    Each time we converge our numbers to smaller numbers, so that it's easier to find the least modulo.

24. Prove the addition rule in modular arithmetic.

25. [Adding in modular arithmetic] What are the 2 ways to find the least residue of 171 + 169 modulo 17.

    Modulos first. Addition first: 171 + 169.

26. [Adding in modular arithmetic] Find the least residue of 67 + 68 modulo 6 by writing out the related congruence rule.

27. [Multiplying in modular arithmetic] Find the least residue of 52 × 37 modulo 7.

28. [Multiplying in modular arithmetic] Find the least residue of 17 × 14 modulo 19. Sometimes it is better to choose an integer in a residue class other than the least residue, as this example demonstrates.

29. [Raising to a power in modular arithmetic] Find the least residue of 116 modulo 9.

    116 = 26 ≡ 23 × 23 ≡ (−1) × (−1) ≡ 1 (mod 9).

30. [Raising to a power in modulo 13] Find the least residue of 2525 modulo 13.

31. [Raising to the fourth power modulo 5] Find the least residues of the following integers modulo 5.

32. State Fermat's little theorem.

33. Why do we specify 'a not a multiple of p' in Fermat's little theorem?

    Because if a was a multiple of p, then ap-1 ≡ 0 (mod p).

34. How to derive the alternative version of Fermat's little theorem ap ≡ a (mod p). The theorem is less easy to apply in this alternative form but has the advantage that it is valid even if a is a multiple of p.

    By multiplying both sides by a.

35. What are Carmichael numbers?

    Nonprime numbers that Fermat's little theorem holds for (smallest being 561). Fermat's little theorem is stated for primes only. However, it holds for some nonprime numbers too! These numbers are called Carmichael numbers.

36. [Applying Fermat’s little theorem] Find the least residue of 420 modulo 7.

37. [Applying Fermat’s little theorem with p = 7] Find the least residue of 56 modulo 7.

    1.

38. Why is it okay to multiply both sides of the congruency by the same number? a ≡ b (mod c) → am ≡ bm (mod c)

    ckm becomes the new constant, thus keeping the congruency. a - b = ck (for some int k)am - bm = ckm (and this km is the new constant!)

39. [Applying Fermat’s little theorem with p = 7] Find the least residue of 1818 modulo 7.

    1.

40. [Applying Fermat’s little theorem with p = 7] Find the least residue of (-11)33 modulo 7.

    6.

41. Prove that the digit sum divisibility by 3 test works.

    This argument also works with congruences modulo 9 instead of modulo 3, and so there is a similar test for divisibility by 9.

42. How to check whether the number is divisible by 3 VS 9?

    For instance, 5847 is not divisible by 9 because its digit sum is 24 which is not divisible by 9, whereas 5841 is divisible by 9 because its digit sum is 18 which is divisible by 9.

43. [Testing divisibility by 9] Is 8469 divisible by 9?

    8469 IS divisible by 9. The digit sum of 8469 is 8+4+6+9 = 27. This is divisible by 9, so 8469 is divisible by 9.

44. How to test whether the number is divisible by 11?

    Alternating digit sum should be divisible by 11. To test whether an integer is divisible by 11, you should first find the alternating digit sum of the integer. The alternating digit sum is found by alternately adding and subtracting the digits of the integer, starting from the units digit, and working backwards through the other digits.

45. How to test whether the number is divisible by 4? By 8?

    By 2 - check whether last digit is divisible by 2. By 4 - check whether last 2 digits are divisible by 4. Note 4 = 22By 8 - check whether last 3 digits are divisible by 8. Note 8 = 23

46. Name 2 common types of barcodes.

    UPC - Universal Product Code Barcode widely used in the United States, Canada, Europe, Australia, New Zealand, and other countries for tracking trade items in stores.ISBN - International Standard Book Number System of numbering used on books.

47. For 10-digit ISBNs - what should the check digit be?

    An ISBN must satisfy this congruence in order to be valid. If the congruence is not satisfied, then there is an error and the number is not an ISBN. The check digit a1 is one of the integers 0, 1, 2,... , 10. When a1 is 10, it is denoted in the ISBN by an X (the Roman numeral for 10) to ensure that it is represented by a single symbol.

48. [Checking whether a 10-digit code could be an ISBN] Does the following 10-digit code satisfy the ISBN congruence check? 0521683726

49. When are a and b coprime?

    When gcd(a, b) = 1 (that is, when they have no common dividers). Two integers whose highest common factor is 1 are said to be coprime.

50. Division doesn't work in modular arithmetic (see the image). What operation can we use instead of normal division in modular arithmetic?

    Multiplicative inverse of a modulo n. For example, 5 is a multiplicative inverse of 2 modulo 9,because 2 × 5 ≡ 1 (mod 9).

51. Write down why 5 is a multiplicative inverse of 2 mod 9.

52. [Finding multiplicative inverses modulo 9] Find a multiplicative inverse modulo 9 of each of the following integers.

53. [Showing that some integers don't have a multiplicative inverse modulo 9] Show that each of the following integers doesn't have a multiplicative inverse modulo 9.

54. What integers a have multiplicative inverse modulo n?

    Integers a comprime with n. gcd(a, n) = 1

55. Name 3 multiplicative inverses of 2 modulo 9.

    5, 14, and -4 - and the entire congruence class!

56. Name 2 ways to find the multiplicative inverse.

    Try values 1, 2, 3, ~, 13. Bezout's identity algorithm where gcd(a, n) = 1. In general, you can use whichever method you wish, although a helpful rule to follow is that you should use the first method when n ≤ 13, and otherwise use the second method. The reason for the integer 13 is that in modular arithmetic modulo n, where n ≤ 13, the only pairs of integers that you’ll need to multiply together are those that fall within the familiar 1 to 12 multiplication tables (providing that each of your…

57. [Finding multiplicative inverses modulo n] Find the multiplicative inverse of 5 modulo 13 (if it exists!).

58. [Finding multiplicative inverses modulo n] Find the multiplicative inverse of 30 modulo 73 (if it exists!).

59. What's a linear congruence?

    In this subsection, you’ll learn how to solve linear congruences in which a and n are coprime. You’ll learn about linear congruences in which a and n are not coprime in the next subsection. You’ll see that some linear congruences have no solutions.

60. Name 3 possible ways to solve the linear congruence.

    If gcd(a, n) = 1 - solve x ≡ vb(mod n), where v is multiplicative inverse If gcd(a, n) ≠ 1 AND b is divisible by gcd(a, n) - solve a new linear congruence with each term is divided by gcd(a, n). If gcd(a, n) ≠ 1 AND b is NOT divisible by gcd(a, n) - then there's NO SOLUTION.

61. [Solving a linear congruence when a and n are coprime and n ≤ 13] Solve the linear congruence.

62. [Solving a linear congruence when a and n are coprime and n > 13] Solve the linear congruence.

63. How are multiplicative inverses connected to Bezout's identity?

    Just like with any linear congruence, we find multiplicative inverses by writing the congruence in the form of the Bezout's identity. Finding multiplicative inverses, just like solving any linear congruence, can be solved via framing them as a Bezout's identity and finding the integers via the Euclid's algorithm.

64. What's the most important step in solving the linear congruence?

    It's all about finding gcd(a, n), and deciding whether it divides b. Other conclusions follow by writing out these congruences as ax - b = nk.

65. Explain why this linear congruence doesn't have a solution.

    Because left-hand side of this equation is divisible by 3, and right-hand side is NOT divisible by 3.

66. What's the geometrical intuition behind Euclid's algorithm (for finding the highest common factor)?

    Subtraction-based animation of the Euclidean algorithm. The initial rectangle has dimensions a = 1071 and b = 462. Squares of size 462×462 are placed within it leaving a 462×147 rectangle. This rectangle is tiled with 147×147 squares until a 21×147 rectangle is left, which in turn is tiled with 21×21 squares, leaving no uncovered area. The smallest square size, 21, is the GCD of 1071 and 462.

67. How to solve any linear congruence? How do Euclid's algorithm, Bezout's identity and HCFs connect?

    Write your linear congruence as Bezout's Identity Solve the Bezout's identity via Euclid's algorithm HCFs come in when we want to see whether a given linear congruence has the solution - but this can be deduced by writing your linear congruence in the form of Bezout's identity.