#set document(title: "6.2 Introduction to Number Theory", author: "OpenStax / XYZ Homework") #set page(width: 8.5in, height: auto, margin: 1in) #import "@preview/cetz:0.5.2" #set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en") #show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math")) #set par(justify: true, leading: 0.62em, spacing: 0.9em) #set enum(spacing: 1.1em) // room between list items so tall inline fractions don't collide #set list(spacing: 1.1em) #set table(stroke: 0.5pt + rgb("#c7ccd3")) #let BLUE = rgb("#183B6F") // brand navy — section bars + example/solution labels (white on navy 11.09:1) #let ORANGE = rgb("#A94509") // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text) #let RED = rgb("#DC2626") // brand error-600 #let GREEN = rgb("#059669") // brand success-600 (decoration only; small green text uses green-text #007942) #show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt, fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt, text(fill: white, weight: "bold", size: 19pt, it.body)) #show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt, fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt, text(fill: white, weight: "bold", size: 12pt, it.body)) #show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body) #show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body) #let examplebox(label, title, body) = block(width: 100%, breakable: true, fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt, above: 12pt, below: 12pt)[ #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt, text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]] #body] // rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade #let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint, stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt), above: 11pt, below: 11pt)[ #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)] #linebreak() #body] #let solutionbox(body) = block(above: 4pt, below: 8pt)[ #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body] #let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"), stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[ #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))] // Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a // consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the // print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a // degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero. #let _STD_W = 3.5 #let _WIDE_W = 5.6 #let _MAX_H = 3.4 #let _ASPECT_WIDE = 2.2 #let _UPSCALE_MAX = 1.15 #let stdfig(body) = context { let m = measure(body) let w = calc.max(m.width / 1in, 0.01) let h = calc.max(m.height / 1in, 0.01) let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W } let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX) align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body))) } #show figure: set block(breakable: false) #set figure(gap: 8pt) #show figure.caption: set text(size: 8.5pt, fill: rgb("#555")) == 6.2#h(0.6em)Introduction to Number Theory We have used the natural numbers to solve problems. This was the right set of numbers to work with in discrete mathematics because we always dealt with a whole number of things. The natural numbers have been a tool. Let's take a moment now to inspect that tool. What mathematical discoveries can we make #emph[about] the natural numbers themselves? This is the main question of number theory: a huge, ancient, complex, and above all, beautiful branch of mathematics. Historically, number theory was known as the Queen of Mathematics and was very much a branch of #emph[pure] mathematics, studied for its own sake instead of as a means to understanding real world applications. This has changed in recent years however, as applications of number theory have been unearthed. Probably the most well known example of this is RSA cryptography, one of the methods used in encrypt data on the internet. It is number theory that makes this possible. What sorts of questions belong to the realm of number theory? Here is a motivating example. Recall in our study of induction, we asked: Which amounts of postage can be made exactly using just 5-cent and 8-cent stamps? We were able to prove that #emph[any] amount greater than 27 cents could be made. You might wonder what would happen if we changed the denomination of the stamps. What if we instead had 4- and 9-cent stamps? Would there be some amount after which all amounts would be possible? Well, again, we could replace two 4-cent stamps with a 9-cent stamp, or three 9-cent stamps with seven 4-cent stamps. In each case we can create one more cent of postage. Using this as the inductive case would allow us to prove that any amount of postage greater than 23 cents can be made. What if we had 2-cent and 4-cent stamps. Here it looks less promising. If we take some number of 2-cent stamps and some number of 4-cent stamps, what can we say about the total? Could it ever be odd? Doesn't look like it. #emph[Why] does 5 and 8 work, 4 and 9 work, but 2 and 4 not work? What is it about these numbers? If I gave you a pair of numbers, could you tell me right away if they would work or not? We will answer these questions, and more, after first investigating some simpler properties of numbers themselves. === Divisibility It is easy to add and multiply natural numbers. If we extend our focus to all integers, then subtraction is also easy (we need the negative numbers so we can subtract any number from any other number, even larger from smaller). Division is the first operation that presents a challenge. If we wanted to extend our set of numbers so any division would be possible (maybe excluding division by 0) we would need to look at the rational numbers (the set of all numbers which can be written as fractions). This would be going too far, so we will refuse this option. In fact, it is a good thing that not every number can be divided by other numbers. This helps us understand the structure of the natural numbers and opens the door to many interesting questions and applications. If given numbers #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$], it is possible that #math.equation(block: false, alt: "a divided by b")[$a ÷ b$] gives a whole number. In this case, we say that #math.equation(block: false, alt: "b")[$b$] #emph[divides] #math.equation(block: false, alt: "a")[$a$], in symbols, we write #math.equation(block: false, alt: "b ∣ a")[$b ∣ a$]. If this holds, then #math.equation(block: false, alt: "b")[$b$] is a divisor or factor of #math.equation(block: false, alt: "a")[$a$], and #math.equation(block: false, alt: "a")[$a$] is a multiple of #math.equation(block: false, alt: "b")[$b$]. In other words, if #math.equation(block: false, alt: "b ∣ a")[$b ∣ a$], then #math.equation(block: false, alt: "a equals b k")[$a = b k$] for some integer #math.equation(block: false, alt: "k")[$k$] (this is saying #math.equation(block: false, alt: "a")[$a$] is some multiple of #math.equation(block: false, alt: "b")[$b$]). #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[The Divisibility Relation] Given integers #math.equation(block: false, alt: "m")[$m$] and #math.equation(block: false, alt: "n")[$n$], we say “#math.equation(block: false, alt: "m")[$m$] divides #math.equation(block: false, alt: "n")[$n$]” and write #math.equation(block: true, alt: "m ∣ n")[$m ∣ n$] provided #math.equation(block: false, alt: "n divided by m")[$n ÷ m$] is an integer. Thus the following assertions mean the same thing: + #math.equation(block: false, alt: "m ∣ n")[$m ∣ n$] + #math.equation(block: false, alt: "n equals m k")[$n = m k$] for some integer #math.equation(block: false, alt: "k")[$k$] + #math.equation(block: false, alt: "m")[$m$] is a factor (or divisor) of #math.equation(block: false, alt: "n")[$n$] + #math.equation(block: false, alt: "n")[$n$] is a multiple of #math.equation(block: false, alt: "m")[$m$]. ] Notice that #math.equation(block: false, alt: "m ∣ n")[$m ∣ n$] is a statement. It is either true or false. On the other hand, #math.equation(block: false, alt: "n divided by m")[$n ÷ m$] or #math.equation(block: false, alt: "n / m")[$n / m$] is some number. If we want to claim that #math.equation(block: false, alt: "n / m")[$n / m$] is not an integer, so #math.equation(block: false, alt: "m")[$m$] does not divide #math.equation(block: false, alt: "n")[$n$], then we can write #math.equation(block: false, alt: "m ∤ n")[$m ∤ n$]. #examplebox("Example 1")[][ Decide whether each of the statements below are true or false. + #math.equation(block: false, alt: "4 ∣ 20")[$4 ∣ 20$] + #math.equation(block: false, alt: "20 ∣ 4")[$20 ∣ 4$] + #math.equation(block: false, alt: "0 ∣ 5")[$0 ∣ 5$] + #math.equation(block: false, alt: "5 ∣ 0")[$5 ∣ 0$] + #math.equation(block: false, alt: "7 ∣ 7")[$7 ∣ 7$] + #math.equation(block: false, alt: "1 ∣ 37")[$1 ∣ 37$] + #math.equation(block: false, alt: "minus 3 ∣ 12")[$− 3 ∣ 12$] + #math.equation(block: false, alt: "8 ∣ 12")[$8 ∣ 12$] + #math.equation(block: false, alt: "1642 ∣ 136299")[$1642 ∣ 136299$] #solutionbox[ + True. 4 “goes into” 20 five times without remainder. In other words, #math.equation(block: false, alt: "20 divided by 4 equals 5")[$20 ÷ 4 = 5$], an integer. We could also justify this by saying that #math.equation(block: false, alt: "20")[$20$] is a multiple of 4: #math.equation(block: false, alt: "20 equals 4 times 5")[$20 = 4 ⋅ 5$]. + False. While 20 is a multiple of 4, it is false that #math.equation(block: false, alt: "4")[$4$] is a multiple of 20. + False. #math.equation(block: false, alt: "5 divided by 0")[$5 ÷ 0$] is not even defined, let alone an integer. + True. In fact, #math.equation(block: false, alt: "x ∣ 0")[$x ∣ 0$] is true for all #math.equation(block: false, alt: "x")[$x$]. This is because 0 is a multiple of every number: #math.equation(block: false, alt: "0 equals x times 0")[$0 = x ⋅ 0$]. + True. In fact, #math.equation(block: false, alt: "x ∣ x")[$x ∣ x$] is true for all #math.equation(block: false, alt: "x")[$x$]. + True. 1 divides every number (other than 0). + True. Negative numbers work just fine for the divisibility relation. Here #math.equation(block: false, alt: "12 equals minus 3 times 4")[$12 = − 3 ⋅ 4$]. It is also true that #math.equation(block: false, alt: "3 ∣ minus 12")[$3 ∣ − 12$] and that #math.equation(block: false, alt: "minus 3 ∣ minus 12")[$− 3 ∣ − 12$]. + False. Both 8 and 12 are divisible by 4, but this does not mean that #math.equation(block: false, alt: "12")[$12$] is divisible by #math.equation(block: false, alt: "8")[$8$]. + False. See below. ] ] This last example raises a question: how might one decide whether #math.equation(block: false, alt: "m ∣ n")[$m ∣ n$]? Of course, if you had a trusted calculator, you could ask it for the value of #math.equation(block: false, alt: "n divided by m")[$n ÷ m$]. If it spits out anything other than an integer, you know #math.equation(block: false, alt: "m ∤ n")[$m ∤ n$]. This seems a little like cheating though: we don't have division, so should we really use division to check divisibility? While we don't really know how to divide, we do know how to multiply. We might try multiplying #math.equation(block: false, alt: "m")[$m$] by larger and larger numbers until we get close to #math.equation(block: false, alt: "n")[$n$]. How close? Well, we want to be sure that if we multiply #math.equation(block: false, alt: "m")[$m$] by the next larger integer, we go over #math.equation(block: false, alt: "n")[$n$]. For example, let's try this to decide whether #math.equation(block: false, alt: "1642 ∣ 136299")[$1642 ∣ 136299$]. Start finding multiples of 1642: #math.equation(block: true, alt: "1642 times 2 equals 32841642 times 3 equals 49261642 times 4 equals 6568 ⋯")[$1642 ⋅ 2 = 3284 #h(2em) 1642 ⋅ 3 = 4926 #h(2em) 1642 ⋅ 4 = 6568 #h(2em) ⋯$] . All of these are well less than 136299. I suppose we can jump ahead a bit: #math.equation(block: true, alt: "1642 times 50 equals 821001642 times 80 equals 1313601642 times 85 equals 139570")[$1642 ⋅ 50 = 82100 #h(2em) 1642 ⋅ 80 = 131360 #h(2em) 1642 ⋅ 85 = 139570$] . Ah, so we need to look somewhere between 80 and 85. Try 83: #math.equation(block: true, alt: "1642 times 83 equals 136286")[$1642 ⋅ 83 = 136286$] . Is this the best we can do? How far are we from our desired 136299? If we subtract, we get #math.equation(block: false, alt: "136299 minus 136286 equals 13")[$136299 − 136286 = 13$]. So we know we cannot go up to 84, that will be too much. In other words, we have found that #math.equation(block: true, alt: "136299 equals 83 times 1642 plus 13")[$136299 = 83 ⋅ 1642 + 13$] . Since #math.equation(block: false, alt: "13 less than 1642")[$13 < 1642$], we can now safely say that #math.equation(block: false, alt: "1642 ∤ 136299")[$1642 ∤ 136299$]. It turns out that the process we went through above can be repeated for any pair of numbers. We can always write the number #math.equation(block: false, alt: "a")[$a$] as some multiple of the number #math.equation(block: false, alt: "b")[$b$] plus some remainder. We know this because we know about #strong[division with remainder] from elementary school. This is just a way of saying it using multiplication. Due to the procedural nature that can be used to find the remainder, this fact is usually called the #strong[division algorithm]: #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[The Division Algorithm] Given any two integers #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$], we can always find an integer #math.equation(block: false, alt: "q")[$q$] such that #math.equation(block: true, alt: "a equals q b plus r")[$a = q b + r$] where #math.equation(block: false, alt: "r")[$r$] is an integer satisfying #math.equation(block: false, alt: "0 less than or equal to r less than vertical bar b vertical bar")[$0 ≤ r < | b |$] ] The idea is that we can always take a large enough multiple of #math.equation(block: false, alt: "b")[$b$] so that the remainder #math.equation(block: false, alt: "r")[$r$] is as small as possible. We do allow the possibility of #math.equation(block: false, alt: "r equals 0")[$r = 0$], in which case we have #math.equation(block: false, alt: "b ∣ a")[$b ∣ a$]. === Remainder Classes The division algorithm tells us that there are only #math.equation(block: false, alt: "b")[$b$] possible remainders when dividing by #math.equation(block: false, alt: "b")[$b$]. If we fix this divisor, we can group integers by the remainder. Each group is called a #strong[remainder class modulo #math.equation(block: false, alt: "b")[$b$]] (or sometimes #strong[residue class]). #examplebox("Example 2")[][ Describe the remainder classes modulo #math.equation(block: false, alt: "5")[$5$]. #solutionbox[ We want to classify numbers by what their remainder would be when divided by #math.equation(block: false, alt: "5")[$5$]. From the division algorithm, we know there will be exactly 5 remainder classes, because there are only 5 choices for what #math.equation(block: false, alt: "r")[$r$] could be (#math.equation(block: false, alt: "0 less than or equal to r less than 5")[$0 ≤ r < 5$]). First consider #math.equation(block: false, alt: "r equals 0")[$r = 0$]. Here we are looking for all the numbers divisible by #math.equation(block: false, alt: "5")[$5$] since #math.equation(block: false, alt: "a equals 5 q plus 0")[$a = 5 q + 0$]. In other words, the multiples of 5. We get the infinite set #math.equation(block: true, alt: "open brace and so on , minus 15 , minus 10 , minus 5 , 0 , 5 , 10 , 15 , 20 , and so on close brace")[$\{ … , − 15 , − 10 , − 5 , 0 , 5 , 10 , 15 , 20 , … \}$] . Notice we also include negative integers. Next consider #math.equation(block: false, alt: "r equals 1")[$r = 1$]. Which integers, when divided by 5, have remainder 1? Well, certainly 1, does, as does 6, and 11. Negatives? Here we must be careful: #math.equation(block: false, alt: "minus 6")[$− 6$] does NOT have remainder 1. We can write #math.equation(block: false, alt: "minus 6 equals minus 2 times 5 plus 4")[$− 6 = − 2 ⋅ 5 + 4$] or #math.equation(block: false, alt: "minus 6 equals minus 1 times 5 minus 1")[$− 6 = − 1 ⋅ 5 − 1$], but only one of these is a “correct” instance of the division algorithm: #math.equation(block: false, alt: "r equals 4")[$r = 4$] since we need #math.equation(block: false, alt: "r")[$r$] to be non-negative. So in fact, to get #math.equation(block: false, alt: "r equals 1")[$r = 1$], we would have #math.equation(block: false, alt: "minus 4")[$− 4$], or #math.equation(block: false, alt: "minus 9")[$− 9$], etc. Thus we get the remainder class #math.equation(block: true, alt: "open brace and so on , minus 14 , minus 9 , minus 4 , 1 , 6 , 11 , 16 , 21 , and so on close brace")[$\{ … , − 14 , − 9 , − 4 , 1 , 6 , 11 , 16 , 21 , … \}$] . There are three more to go. The remainder classes for #math.equation(block: false, alt: "2")[$2$], #math.equation(block: false, alt: "3")[$3$], and #math.equation(block: false, alt: "4")[$4$] are, respectively #math.equation(block: true, alt: "open brace and so on , minus 13 , minus 8 , minus 3 , 2 , 7 , 12 , 17 , 22 , and so on close brace")[$\{ … , − 13 , − 8 , − 3 , 2 , 7 , 12 , 17 , 22 , … \}$] #math.equation(block: true, alt: "open brace and so on , minus 12 , minus 7 , minus 2 , 3 , 8 , 13 , 18 , 23 , and so on close brace")[$\{ … , − 12 , − 7 , − 2 , 3 , 8 , 13 , 18 , 23 , … \}$] #math.equation(block: true, alt: "open brace and so on , minus 11 , minus 6 , minus 1 , 4 , 9 , 14 , 19 , 24 , and so on close brace")[$\{ … , − 11 , − 6 , − 1 , 4 , 9 , 14 , 19 , 24 , … \}$] . ] ] Note that in the example above, #emph[every] integer is in exactly one remainder class. The technical way to say this is that the remainder classes modulo #math.equation(block: false, alt: "b")[$b$] form a #strong[partition] of the integers. It is possible to develop a mathematical theory of partitions, prove statements about all partitions in general and then apply those observations to our case here. The most important fact about partitions, is that it is possible to define an #strong[equivalence relation] from a partition: this is a relationship between pairs of numbers which acts in all the important ways like the “equals” relationship. Again, there is a mathematical theory of equivalence relations which applies in many more instances than the one we look at here. All fun technical language aside, the idea is really simple. If two numbers belong to the same remainder class, then in some way, they are the same. That is, they are the same #emph[up to division by #math.equation(block: false, alt: "b")[$b$]]. In the case where #math.equation(block: false, alt: "b equals 5")[$b = 5$] above, the numbers #math.equation(block: false, alt: "8")[$8$] and #math.equation(block: false, alt: "23")[$23$], while not the same number, are the same when it comes to dividing by 5, because both have remainder #math.equation(block: false, alt: "3")[$3$]. It matters what the divisor is: #math.equation(block: false, alt: "8")[$8$] and #math.equation(block: false, alt: "23")[$23$] are the same up to division by #math.equation(block: false, alt: "5")[$5$], but not up to division by #math.equation(block: false, alt: "7")[$7$], since #math.equation(block: false, alt: "8")[$8$] has remainder of 1 when divided by 7 while 23 has a remainder of 2. With all this in mind, let's introduce some notation. We want to say that #math.equation(block: false, alt: "8")[$8$] and 23 are basically the same, even though they are not equal. It would be wrong to say #math.equation(block: false, alt: "8 equals 23")[$8 = 23$]. Instead, we write #math.equation(block: false, alt: "8 ≡ 23")[$8 ≡ 23$]. But this is not always true. It works if we are thinking division by 5, so we need to denote that somehow. What we will actually write is this: #math.equation(block: true, alt: "8 ≡ 23 open parenthesis mod 5 close parenthesis")[$8 ≡ 23 #h(1em) ( mod #h(0.333em) 5 )$] which is read, “8 is congruent to 23 modulo 5” (or just “mod 5”). Of course then we could observe that #math.equation(block: true, alt: "8 ≢ 23 open parenthesis mod 7 close parenthesis")[$8 ≢ 23 #h(1em) ( mod #h(0.333em) 7 )$] . #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Congruence Modulo #math.equation(block: false, alt: "n")[$n$]] We say #strong[#math.equation(block: false, alt: "a")[$a$] is congruent to #math.equation(block: false, alt: "b")[$b$] modulo #math.equation(block: false, alt: "n")[$n$]], and write, #math.equation(block: true, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(1em) ( mod #h(0.333em) n )$] provided #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] have the same remainder when divided by #math.equation(block: false, alt: "n")[$n$]. In other words, provided #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] belong to the same remainder class modulo #math.equation(block: false, alt: "n")[$n$]. ] Many books define congruence modulo #math.equation(block: false, alt: "n")[$n$] slightly differently. They say that #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$] if and only if #math.equation(block: false, alt: "n ∣ a minus b")[$n ∣ a − b$]. In other words, two numbers are congruent modulo #math.equation(block: false, alt: "n")[$n$], if their difference is a multiple of #math.equation(block: false, alt: "n")[$n$]. So which definition is correct? Turns out, it doesn't matter: they are equivalent. To see why, consider two numbers #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] which are congruent modulo #math.equation(block: false, alt: "n")[$n$]. Then #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] have the same remainder when divided by #math.equation(block: false, alt: "n")[$n$]. We have #math.equation(block: true, alt: "a equals q sub 1 n plus r b equals q sub 2 n plus r")[$a = q_(1) n + r #h(2em) #h(2em) b = q_(2) n + r$] . Here the two #math.equation(block: false, alt: "r")[$r$]'s really are the same. Consider what we get when we take the difference of #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$]: #math.equation(block: true, alt: "a minus b equals q sub 1 n plus r minus open parenthesis q sub 2 n plus r close parenthesis equals q sub 1 n minus q sub 2 n equals open parenthesis q sub 1 minus q sub 2 close parenthesis n")[$a − b = q_(1) n + r − ( q_(2) n + r ) = q_(1) n − q_(2) n = ( q_(1) − q_(2) ) n$] . So #math.equation(block: false, alt: "a minus b")[$a − b$] is a multiple of #math.equation(block: false, alt: "n")[$n$], or equivalently, #math.equation(block: false, alt: "n ∣ a minus b")[$n ∣ a − b$]. On the other hand, if we assume first that #math.equation(block: false, alt: "n ∣ a minus b")[$n ∣ a − b$], so #math.equation(block: false, alt: "a minus b equals k n")[$a − b = k n$], then consider what happens if we divide each term by #math.equation(block: false, alt: "n")[$n$]. Dividing #math.equation(block: false, alt: "a")[$a$] by #math.equation(block: false, alt: "n")[$n$] will leave some remainder, as will dividing #math.equation(block: false, alt: "b")[$b$] by #math.equation(block: false, alt: "n")[$n$]. However, dividing #math.equation(block: false, alt: "k n")[$k n$] by #math.equation(block: false, alt: "n")[$n$] will leave 0 remainder. So the remainders on the left-hand side must cancel out. That is, the remainders must be the same. Thus we have: #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Congruence and Divisibility] For any integers #math.equation(block: false, alt: "a")[$a$], #math.equation(block: false, alt: "b")[$b$], and #math.equation(block: false, alt: "n")[$n$], we have #math.equation(block: true, alt: "a ≡ b open parenthesis mod n close parenthesis if and only if n ∣ open parenthesis a minus b close parenthesis")[$a ≡ b #h(1em) ( mod #h(0.333em) n ) #h(2em) " if and only if " #h(2em) n ∣ ( a − b )$] . ] It will also be useful to switch back and forth between congruences and regular equations. The above fact helps with this. We know that #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$] if and only if #math.equation(block: false, alt: "n ∣ a minus b")[$n ∣ a − b$], if and only if #math.equation(block: false, alt: "a minus b equals k n")[$a − b = k n$] for some integer #math.equation(block: false, alt: "k")[$k$]. Rearranging that equation, we get #math.equation(block: false, alt: "a equals b plus k n")[$a = b + k n$]. In other words, if #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] are congruent modulo #math.equation(block: false, alt: "n")[$n$], then #math.equation(block: false, alt: "a")[$a$] is #math.equation(block: false, alt: "b")[$b$] more than some multiple of #math.equation(block: false, alt: "n")[$n$]. This conforms with our earlier observation that all the numbers in a particular remainder class are the same amount larger than the multiples of #math.equation(block: false, alt: "n")[$n$]. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Congruence and Equality] For any integers #math.equation(block: false, alt: "a")[$a$], #math.equation(block: false, alt: "b")[$b$], and #math.equation(block: false, alt: "n")[$n$], we have #math.equation(block: true, alt: "a ≡ b open parenthesis mod n close parenthesis if and only if a equals b plus k n for some integer k")[$a ≡ b #h(1em) ( mod #h(0.333em) n ) #h(2em) " if and only if " #h(2em) a = b + k n " for some integer " k$] . ] === Properties of Congruence We said earlier that congruence modulo #math.equation(block: false, alt: "n")[$n$] behaves, in many important ways, the same way equality does. Specifically, we could prove that congruence modulo #math.equation(block: false, alt: "n")[$n$] is an #strong[equivalence relation], which would require checking the following three facts: #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Congruence Modulo #math.equation(block: false, alt: "n")[$n$] is an Equivalence Relation] Given any integers #math.equation(block: false, alt: "a")[$a$], #math.equation(block: false, alt: "b")[$b$], and #math.equation(block: false, alt: "c")[$c$], and any positive integer #math.equation(block: false, alt: "n")[$n$], the following hold: + #math.equation(block: false, alt: "a ≡ a open parenthesis mod n close parenthesis")[$a ≡ a #h(0.444em) ( mod #h(0.333em) n )$]. + If #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$] then #math.equation(block: false, alt: "b ≡ a open parenthesis mod n close parenthesis")[$b ≡ a #h(0.444em) ( mod #h(0.333em) n )$]. + If #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$] and #math.equation(block: false, alt: "b ≡ c open parenthesis mod n close parenthesis")[$b ≡ c #h(0.444em) ( mod #h(0.333em) n )$], then #math.equation(block: false, alt: "a ≡ c open parenthesis mod n close parenthesis")[$a ≡ c #h(0.444em) ( mod #h(0.333em) n )$]. In other words, congruence modulo #math.equation(block: false, alt: "n")[$n$] is reflexive, symmetric, and transitive, so is an equivalence relation. ] You should take a minute to convince yourself that each of the properties above actually hold of congruence. Try explaining each using both the remainder and divisibility definitions. Next, consider how congruence behaves when doing basic arithmetic. We already know that if you subtract two congruent numbers, the result will be congruent to 0 (be a multiple of #math.equation(block: false, alt: "n")[$n$]). What if we add something congruent to 1 to something congruent to 2? Will we get something congruent to 3? #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Congruence and Arithmetic] Suppose #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$] and #math.equation(block: false, alt: "c ≡ d open parenthesis mod n close parenthesis")[$c ≡ d #h(0.444em) ( mod #h(0.333em) n )$]. Then the following hold: + #math.equation(block: false, alt: "a plus c ≡ b plus d open parenthesis mod n close parenthesis")[$a + c ≡ b + d #h(0.444em) ( mod #h(0.333em) n )$]. + #math.equation(block: false, alt: "a minus c ≡ b minus d open parenthesis mod n close parenthesis")[$a − c ≡ b − d #h(0.444em) ( mod #h(0.333em) n )$]. + #math.equation(block: false, alt: "a c ≡ b d open parenthesis mod n close parenthesis")[$a c ≡ b d #h(0.444em) ( mod #h(0.333em) n )$]. ] The above facts might be written a little strangely, but the idea is simple. If we have a true congruence, and we add the same thing to both sides, the result is still a true congruence. This sounds like we are saying: If #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$] then #math.equation(block: false, alt: "a plus c ≡ b plus c open parenthesis mod n close parenthesis")[$a + c ≡ b + c #h(0.444em) ( mod #h(0.333em) n )$]. Of course this is true as well, it is the special case where #math.equation(block: false, alt: "c equals d")[$c = d$]. But what we have works in more generality. Think of congruence as being “basically equal.” If we have two numbers which are basically equal, and we add basically the same thing to both sides, the result will be basically equal. This seems reasonable. Is it really true? Let's prove the first fact: #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ Suppose #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$] and #math.equation(block: false, alt: "c ≡ d open parenthesis mod n close parenthesis")[$c ≡ d #h(0.444em) ( mod #h(0.333em) n )$]. That means #math.equation(block: false, alt: "a equals b plus k n")[$a = b + k n$] and #math.equation(block: false, alt: "c equals d plus j n")[$c = d + j n$] for integers #math.equation(block: false, alt: "k")[$k$] and #math.equation(block: false, alt: "j")[$j$]. Add these equations: #math.equation(block: true, alt: "a plus c equals b plus d plus k n plus j n")[$a + c = b + d + k n + j n$] . But #math.equation(block: false, alt: "k n plus j n equals open parenthesis k plus j close parenthesis n")[$k n + j n = ( k + j ) n$], which is just a multiple of #math.equation(block: false, alt: "n")[$n$]. So #math.equation(block: false, alt: "a plus c equals b plus d plus open parenthesis j plus k close parenthesis n")[$a + c = b + d + ( j + k ) n$], or in other words, #math.equation(block: false, alt: "a plus c ≡ b plus d open parenthesis mod n close parenthesis")[$a + c ≡ b + d #h(0.444em) ( mod #h(0.333em) n )$] ] The other two facts can be proved in a similar way. One of the important consequences of these facts about congruences, is that we can basically replace any number in a congruence with any other number it is congruent to. Here are some examples to see how (and why) that works: #examplebox("Example 3")[][ Find the remainder of #math.equation(block: false, alt: "3491")[$3491$] divided by #math.equation(block: false, alt: "9")[$9$]. #solutionbox[ We could do long division, but there is another way. We want to find #math.equation(block: false, alt: "x")[$x$] such that #math.equation(block: false, alt: "x ≡ 3491 open parenthesis mod 9 close parenthesis")[$x ≡ 3491 #h(0.444em) ( mod #h(0.333em) 9 )$]. Now #math.equation(block: false, alt: "3491 equals 3000 plus 400 plus 90 plus 1")[$3491 = 3000 + 400 + 90 + 1$]. Of course #math.equation(block: false, alt: "90 ≡ 0 open parenthesis mod 9 close parenthesis")[$90 ≡ 0 #h(0.444em) ( mod #h(0.333em) 9 )$], so we can replace the 90 in the sum with 0. Why is this okay? We are actually subtracting the “same” thing from both sides: #math.equation(block: true, alt: "x, ≡ 3000 plus 400 plus 90 plus 1 open parenthesis mod 9 close parenthesis; minus 0, ≡ 90 open parenthesis mod 9 close parenthesis; x, ≡ 3000 plus 400 plus 0 plus 1 open parenthesis mod 9 close parenthesis .")[$x & ≡ 3000 + 400 + 90 + 1 #h(1em) ( mod #h(0.333em) 9 ) \ − " " " " 0 & ≡ 90 #h(1em) ( mod #h(0.333em) 9 ) \ x & ≡ 3000 + 400 + 0 + 1 #h(1em) ( mod #h(0.333em) 9 ) .$] Next, note that #math.equation(block: false, alt: "400 equals 4 times 100")[$400 = 4 ⋅ 100$], and #math.equation(block: false, alt: "100 ≡ 1 open parenthesis mod 9 close parenthesis")[$100 ≡ 1 #h(0.444em) ( mod #h(0.333em) 9 )$] (since #math.equation(block: false, alt: "9 ∣ 99")[$9 ∣ 99$]). So we can in fact replace the 400 with simply a 4. Again, we are appealing to our claim that we can replace congruent elements, but we are really appealing to property 3 about the arithmetic of congruence: we know #math.equation(block: false, alt: "100 ≡ 1 open parenthesis mod 9 close parenthesis")[$100 ≡ 1 #h(0.444em) ( mod #h(0.333em) 9 )$], so if we multiply both sides by #math.equation(block: false, alt: "4")[$4$], we get #math.equation(block: false, alt: "400 ≡ 4 open parenthesis mod 9 close parenthesis")[$400 ≡ 4 #h(0.444em) ( mod #h(0.333em) 9 )$]. Similarly, we can replace 3000 with 3, since #math.equation(block: false, alt: "1000 equals 1 plus 999 ≡ 1 open parenthesis mod 9 close parenthesis")[$1000 = 1 + 999 ≡ 1 #h(0.444em) ( mod #h(0.333em) 9 )$]. So our original congruence becomes #math.equation(block: true, alt: "x ≡ 3 plus 4 plus 0 plus 1 open parenthesis mod 9 close parenthesis")[$x ≡ 3 + 4 + 0 + 1 #h(1em) ( mod #h(0.333em) 9 )$] #math.equation(block: true, alt: "x ≡ 8 open parenthesis mod 9 close parenthesis")[$x ≡ 8 #h(1em) ( mod #h(0.333em) 9 )$] . Therefore #math.equation(block: false, alt: "3491")[$3491$] divided by 9 has remainder 8. ] ] The above example should convince you that the well known divisibility test for 9 is true: the sum of the digits of a number is divisible by 9 if and only if the original number is divisible by 9. In fact, we now know something more: any number is congruent to the sum of its digits, modulo 9. This works for 3 as well, but definitely not for any modulus in general. Let's try another: #examplebox("Example 4")[][ Find the remainder when #math.equation(block: false, alt: "3 to the power 123")[$3^(123)$] is divided by 7. #solutionbox[ Of course, we are working with congruence because we want to find the smallest positive #math.equation(block: false, alt: "x")[$x$] such that #math.equation(block: false, alt: "x ≡ 3 to the power 123 open parenthesis mod 7 close parenthesis")[$x ≡ 3^(123) #h(0.444em) ( mod #h(0.333em) 7 )$]. Now first write #math.equation(block: false, alt: "3 to the power 123 equals open parenthesis 3 cubed close parenthesis to the power 41")[$3^(123) = ( 3^(3) )^(41)$]. We have: #math.equation(block: true, alt: "3 to the power 123 equals 27 to the power 41 ≡ 6 to the power 41 open parenthesis mod 7 close parenthesis")[$3^(123) = 27^(41) ≡ 6^(41) #h(1em) ( mod #h(0.333em) 7 )$] , since #math.equation(block: false, alt: "27 ≡ 6 open parenthesis mod 7 close parenthesis")[$27 ≡ 6 #h(0.444em) ( mod #h(0.333em) 7 )$]. Notice further that #math.equation(block: false, alt: "6 squared equals 36")[$6^(2) = 36$] is congruent to 1 modulo 7. Thus we can simplify further: #math.equation(block: true, alt: "6 to the power 41 equals 6 times open parenthesis 6 squared close parenthesis to the power 20 ≡ 6 times 1 to the power 20 open parenthesis mod 7 close parenthesis")[$6^(41) = 6 ⋅ ( 6^(2) )^(20) ≡ 6 ⋅ 1^(20) #h(1em) ( mod #h(0.333em) 7 )$] . But #math.equation(block: false, alt: "1 to the power 20 equals 1")[$1^(20) = 1$], so we are done: #math.equation(block: true, alt: "3 to the power 123 ≡ 6 open parenthesis mod 7 close parenthesis")[$3^(123) ≡ 6 #h(1em) ( mod #h(0.333em) 7 )$] . ] ] In the above example, we are using the fact that if #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$], then #math.equation(block: false, alt: "a to the power p ≡ b to the power p open parenthesis mod n close parenthesis")[$a^(p) ≡ b^(p) #h(0.444em) ( mod #h(0.333em) n )$]. This is just applying property 3 a bunch of times. So far we have seen how to add, subtract and multiply with congruences. What about division? There is a reason we have waited to discuss it. It turns out that we cannot simply divide. In other words, even if #math.equation(block: false, alt: "a d ≡ b d open parenthesis mod n close parenthesis")[$a d ≡ b d #h(0.444em) ( mod #h(0.333em) n )$], we do not know that #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$]. Consider, for example: #math.equation(block: true, alt: "18 ≡ 42 open parenthesis mod 8 close parenthesis")[$18 ≡ 42 #h(1em) ( mod #h(0.333em) 8 )$] . This is true. Now #math.equation(block: false, alt: "18")[$18$] and #math.equation(block: false, alt: "42")[$42$] are both divisible by 6. However, #math.equation(block: true, alt: "3 ≢ 7 open parenthesis mod 8 close parenthesis")[$3 ≢ 7 #h(1em) ( mod #h(0.333em) 8 )$] . While this doesn't work, note that #math.equation(block: false, alt: "3 ≡ 7 open parenthesis mod 4 close parenthesis")[$3 ≡ 7 #h(0.444em) ( mod #h(0.333em) 4 )$]. We cannot divide #math.equation(block: false, alt: "8")[$8$] by 6, but we can divide 8 by the greatest common factor of #math.equation(block: false, alt: "8")[$8$] and #math.equation(block: false, alt: "6")[$6$]. Will this always happen? Suppose #math.equation(block: false, alt: "a d ≡ b d open parenthesis mod n close parenthesis")[$a d ≡ b d #h(0.444em) ( mod #h(0.333em) n )$]. In other words, we have #math.equation(block: false, alt: "a d equals b d plus k n")[$a d = b d + k n$] for some integer #math.equation(block: false, alt: "k")[$k$]. Of course #math.equation(block: false, alt: "a d")[$a d$] is divisible by #math.equation(block: false, alt: "d")[$d$], as is #math.equation(block: false, alt: "b d")[$b d$]. So #math.equation(block: false, alt: "k n")[$k n$] must also be divisible by #math.equation(block: false, alt: "d")[$d$]. Now if #math.equation(block: false, alt: "n")[$n$] and #math.equation(block: false, alt: "d")[$d$] have no common factors (other than 1), then we must have #math.equation(block: false, alt: "d ∣ k")[$d ∣ k$]. But in general, if we try to divide #math.equation(block: false, alt: "k n")[$k n$] by #math.equation(block: false, alt: "d")[$d$], we don't know that we will get an integer multiple of #math.equation(block: false, alt: "n")[$n$]. Some of the #math.equation(block: false, alt: "n")[$n$] might get divided as well. To be safe, let's divide as much of #math.equation(block: false, alt: "n")[$n$] as we can. Take the largest factor of both #math.equation(block: false, alt: "d")[$d$] and #math.equation(block: false, alt: "n")[$n$], and cancel that out from #math.equation(block: false, alt: "n")[$n$]. The rest of the factors of #math.equation(block: false, alt: "d")[$d$] will come from #math.equation(block: false, alt: "k")[$k$], no problem. We will call the largest factor of both #math.equation(block: false, alt: "d")[$d$] and #math.equation(block: false, alt: "n")[$n$] the #math.equation(block: false, alt: "gcd open parenthesis d , n close parenthesis")[$gcd ( d , n )$], for #emph[greatest common divisor]. In our example above, #math.equation(block: false, alt: "gcd open parenthesis 6 , 8 close parenthesis equals 2")[$gcd ( 6 , 8 ) = 2$] since the greatest divisor common to 6 and 8 is 2. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Congruence and Division] Suppose #math.equation(block: false, alt: "a d ≡ b d open parenthesis mod n close parenthesis")[$a d ≡ b d #h(0.444em) ( mod #h(0.333em) n )$]. Then #math.equation(block: false, alt: "a ≡ b open parenthesis mod the fraction n over gcd open parenthesis d , n close parenthesis close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) frac(n, gcd ( d "," n )) )$]. If #math.equation(block: false, alt: "d")[$d$] and #math.equation(block: false, alt: "n")[$n$] have no common factors then #math.equation(block: false, alt: "gcd open parenthesis d , n close parenthesis equals 1")[$gcd ( d , n ) = 1$], so #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$]. ] #examplebox("Example 5")[][ Simplify the following congruences using division: (a) #math.equation(block: false, alt: "24 ≡ 39 open parenthesis mod 5 close parenthesis")[$24 ≡ 39 #h(0.444em) ( mod #h(0.333em) 5 )$] and (b) #math.equation(block: false, alt: "24 ≡ 39 open parenthesis mod 15 close parenthesis")[$24 ≡ 39 #h(0.444em) ( mod #h(0.333em) 15 )$]. #solutionbox[ (a) Both #math.equation(block: false, alt: "24")[$24$] and #math.equation(block: false, alt: "39")[$39$] are divisible by #math.equation(block: false, alt: "3")[$3$], and #math.equation(block: false, alt: "3")[$3$] and #math.equation(block: false, alt: "5")[$5$] have no common factors, so we get #math.equation(block: true, alt: "8 ≡ 13 open parenthesis mod 5 close parenthesis")[$8 ≡ 13 #h(1em) ( mod #h(0.333em) 5 )$] . (b) Again, we can divide by 3. However, doing so blindly gives us #math.equation(block: false, alt: "8 ≡ 13 open parenthesis mod 15 close parenthesis")[$8 ≡ 13 #h(0.444em) ( mod #h(0.333em) 15 )$] which is no longer true. Instead, we must also divide the modulus 15 by the greatest common factor of #math.equation(block: false, alt: "3")[$3$] and #math.equation(block: false, alt: "15")[$15$], which is #math.equation(block: false, alt: "3")[$3$]. Again we get #math.equation(block: true, alt: "8 ≡ 13 open parenthesis mod 5 close parenthesis")[$8 ≡ 13 #h(1em) ( mod #h(0.333em) 5 )$] . ] ] === Solving Congruences Now that we have some algebraic rules to govern congruence relations, we can attempt to solve for an unknown in a congruence. For example, is there a value of #math.equation(block: false, alt: "x")[$x$] that satisfies, #math.equation(block: true, alt: "3 x plus 2 ≡ 4 open parenthesis mod 5 close parenthesis")[$3 x + 2 ≡ 4 #h(1em) ( mod #h(0.333em) 5 )$] , and if so, what is it? In this example, since the modulus is small, we could simply try every possible value for #math.equation(block: false, alt: "x")[$x$]. There are really only 5 to consider, since any integer that satisfied the congruence could be replaced with any other integer it was congruent to modulo 5. Here, when #math.equation(block: false, alt: "x equals 4")[$x = 4$] we get #math.equation(block: false, alt: "3 x plus 2 equals 14")[$3 x + 2 = 14$] which is indeed congruent to 4 modulo 5. This means that #math.equation(block: false, alt: "x equals 9")[$x = 9$] and #math.equation(block: false, alt: "x equals 14")[$x = 14$] and #math.equation(block: false, alt: "x equals 19")[$x = 19$] and so on will each also be a solution because as we saw above, replacing any number in a congruence with a congruent number does not change the truth of the congruence. So in this example, simply compute #math.equation(block: false, alt: "3 x plus 2")[$3 x + 2$] for values of #math.equation(block: false, alt: "x ∈ open brace 0 , 1 , 2 , 3 , 4 close brace")[$x ∈ \{ 0 , 1 , 2 , 3 , 4 \}$]. This gives 2, 5, 8, 11, and 14 respectively, for which only 14 is congruent to 4. Let's also see how you could solve this using our rules for the algebra of congruences. Such an approach would be much simpler than the trial and error tactic if the modulus was larger. First, we know we can subtract 2 from both sides: #math.equation(block: true, alt: "3 x ≡ 2 open parenthesis mod 5 close parenthesis")[$3 x ≡ 2 #h(1em) ( mod #h(0.333em) 5 )$] . Then to divide both sides by 3, we first add 0 to both sides. Of course, on the right-hand side, we want that 0 to be a 10 (yes, #math.equation(block: false, alt: "10")[$10$] really is 0 since they are congruent modulo 5). This gives, #math.equation(block: true, alt: "3 x ≡ 12 open parenthesis mod 5 close parenthesis")[$3 x ≡ 12 #h(1em) ( mod #h(0.333em) 5 )$] . Now divide both sides by 3. Since #math.equation(block: false, alt: "gcd open parenthesis 3 , 5 close parenthesis equals 1")[$gcd ( 3 , 5 ) = 1$], we do not need to change the modulus: #math.equation(block: true, alt: "x ≡ 4 open parenthesis mod 5 close parenthesis")[$x ≡ 4 #h(1em) ( mod #h(0.333em) 5 )$] . Notice that this in fact gives the #emph[general solution]: not only can #math.equation(block: false, alt: "x equals 4")[$x = 4$], but #math.equation(block: false, alt: "x")[$x$] can be any number which is congruent to 4. We can leave it like this, or write “#math.equation(block: false, alt: "x equals 4 plus 5 k")[$x = 4 + 5 k$] for any integer #math.equation(block: false, alt: "k")[$k$].” #examplebox("Example 6")[][ Solve the following congruences for #math.equation(block: false, alt: "x")[$x$]. + #math.equation(block: false, alt: "7 x ≡ 12 open parenthesis mod 13 close parenthesis")[$7 x ≡ 12 #h(0.444em) ( mod #h(0.333em) 13 )$]. + #math.equation(block: false, alt: "84 x minus 38 ≡ 79 open parenthesis mod 15 close parenthesis")[$84 x − 38 ≡ 79 #h(0.444em) ( mod #h(0.333em) 15 )$]. + #math.equation(block: false, alt: "20 x ≡ 23 open parenthesis mod 14 close parenthesis")[$20 x ≡ 23 #h(0.444em) ( mod #h(0.333em) 14 )$]. #solutionbox[ + All we need to do here is divide both sides by 7. We add 13 to the right-hand side repeatedly until we get a multiple of 7 (adding 13 is the same as adding 0, so this is legal). We get #math.equation(block: false, alt: "25")[$25$], #math.equation(block: false, alt: "38")[$38$], #math.equation(block: false, alt: "51")[$51$], #math.equation(block: false, alt: "64")[$64$], #math.equation(block: false, alt: "77")[$77$] – got it. So we have: #math.equation(block: true, alt: "7 x, ≡ 12 open parenthesis mod 13 close parenthesis; 7 x, ≡ 77 open parenthesis mod 13 close parenthesis; x, ≡ 11 open parenthesis mod 13 close parenthesis .")[$7 x & ≡ 12 #h(1em) ( mod #h(0.333em) 13 ) \ 7 x & ≡ 77 #h(1em) ( mod #h(0.333em) 13 ) \ x & ≡ 11 #h(1em) ( mod #h(0.333em) 13 ) .$] + Here, since we have numbers larger than the modulus, we can reduce them prior to applying any algebra. We have #math.equation(block: false, alt: "84 ≡ 9")[$84 ≡ 9$], #math.equation(block: false, alt: "38 ≡ 8")[$38 ≡ 8$] and #math.equation(block: false, alt: "79 ≡ 4")[$79 ≡ 4$]. Thus, #math.equation(block: true, alt: "84 x minus 38, ≡ 79 open parenthesis mod 15 close parenthesis; 9 x minus 8, ≡ 4 open parenthesis mod 15 close parenthesis; 9 x, ≡ 12 open parenthesis mod 15 close parenthesis; 9 x, ≡ 72 open parenthesis mod 15 close parenthesis .")[$84 x − 38 & ≡ 79 #h(1em) ( mod #h(0.333em) 15 ) \ 9 x − 8 & ≡ 4 #h(1em) ( mod #h(0.333em) 15 ) \ 9 x & ≡ 12 #h(1em) ( mod #h(0.333em) 15 ) \ 9 x & ≡ 72 #h(1em) ( mod #h(0.333em) 15 ) .$] We got the 72 by adding #math.equation(block: false, alt: "0 ≡ 60 open parenthesis mod 15 close parenthesis")[$0 ≡ 60 #h(0.444em) ( mod #h(0.333em) 15 )$] to both sides of the congruence. Now divide both sides by 9. However, since #math.equation(block: false, alt: "gcd open parenthesis 9 , 15 close parenthesis equals 3")[$gcd ( 9 , 15 ) = 3$], we must divide the modulus by 3 as well: #math.equation(block: true, alt: "x ≡ 8 open parenthesis mod 5 close parenthesis")[$x ≡ 8 #h(1em) ( mod #h(0.333em) 5 )$]. So the solutions are those values which are congruent to 8, or equivalently 3, modulo 5. This means that in some sense there are 3 solutions modulo 15: 3, 8, and 13. We can write the solution: #math.equation(block: true, alt: "x ≡ 3 open parenthesis mod 15 close parenthesis ; x ≡ 8 open parenthesis mod 15 close parenthesis ; x ≡ 13 open parenthesis mod 15 close parenthesis")[$x ≡ 3 #h(1em) ( mod #h(0.333em) 15 ) ; " " " " x ≡ 8 #h(1em) ( mod #h(0.333em) 15 ) ; " " " " x ≡ 13 #h(1em) ( mod #h(0.333em) 15 )$]. + First, reduce modulo 14: #math.equation(block: true, alt: "20 x ≡ 23 open parenthesis mod 14 close parenthesis")[$20 x ≡ 23 #h(1em) ( mod #h(0.333em) 14 )$] #math.equation(block: true, alt: "6 x ≡ 9 open parenthesis mod 14 close parenthesis")[$6 x ≡ 9 #h(1em) ( mod #h(0.333em) 14 )$]. We could now divide both sides by 3, or try to increase 9 by a multiple of 14 to get a multiple of 6. If we divide by 3, we get, #math.equation(block: true, alt: "2 x ≡ 3 open parenthesis mod 14 close parenthesis")[$2 x ≡ 3 #h(1em) ( mod #h(0.333em) 14 )$]. Now try adding multiples of 14 to 3, in hopes of getting a number we can divide by 2. This will not work! Every time we add 14 to the right side, the result will still be odd. We will never get an even number, so we will never be able to divide by 2. Thus there are no solutions to the congruence. ] ] The last congruence above illustrates the way in which congruences might not have solutions. We could have seen this immediately in fact. Look at the original congruence: #math.equation(block: true, alt: "20 x ≡ 23 open parenthesis mod 14 close parenthesis")[$20 x ≡ 23 #h(1em) ( mod #h(0.333em) 14 )$] . If we write this as an equation, we get #math.equation(block: true, alt: "20 x equals 23 plus 14 k")[$20 x = 23 + 14 k$] , or equivalently #math.equation(block: false, alt: "20 x minus 14 k equals 23")[$20 x − 14 k = 23$]. We can easily see there will be no solution to this equation in integers. The left-hand side will always be even, but the right-hand side is odd. A similar problem would occur if the right-hand side was divisible by #emph[any] number the left-hand side was not. So in general, given the congruence #math.equation(block: true, alt: "a x ≡ b open parenthesis mod n close parenthesis")[$a x ≡ b #h(1em) ( mod #h(0.333em) n )$] , if #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "n")[$n$] are divisible by a number which #math.equation(block: false, alt: "b")[$b$] is not divisible by, then there will be no solutions. In fact, we really only need to check one divisor of #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "n")[$n$]: the greatest common divisor. Thus, a more compact way to say this is: #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Congruences with no solutions] If #math.equation(block: false, alt: "gcd open parenthesis a , n close parenthesis ∤ b")[$gcd ( a , n ) ∤ b$], then #math.equation(block: false, alt: "a x ≡ b open parenthesis mod n close parenthesis")[$a x ≡ b #h(0.444em) ( mod #h(0.333em) n )$] has no solutions. ] === Solving Linear Diophantine Equations Discrete math deals with whole numbers of things. So when we want to solve equations, we usually are looking for #emph[integer] solutions. Equations which are intended to only have integer solutions were first studied by in the third century by the Greek mathematician Diophantus of Alexandria, and as such are called #emph[Diophantine equations]. Probably the most famous example of a Diophantine equation is #math.equation(block: false, alt: "a squared plus b squared equals c squared")[$a^(2) + b^(2) = c^(2)$]. The integer solutions to this equation are called #strong[Pythagorean triples]. In general, solving Diophantine equations is hard (in fact, there is provably no general algorithm for deciding whether a Diophantine equation has a solution, a result known as Matiyasevich's Theorem). We will restrict our focus to #emph[linear] Diophantine equations, which are considerably easier to work with. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Diophantine Equations] An equation in two or more variables is called a #strong[Diophantine equation] if only integers solutions are of interest. A #strong[linear] Diophantine equation takes the form #math.equation(block: false, alt: "a sub 1 x sub 1 plus a sub 2 x sub 2 plus ⋯ plus a sub n x sub n equals b")[$a_(1) x_(1) + a_(2) x_(2) + ⋯ + a_(n) x_(n) = b$] for constants #math.equation(block: false, alt: "a sub 1 , and so on , a sub n , b")[$a_(1) , … , a_(n) , b$]. A #strong[solution] to a Diophantine equation is a solution to the equation consisting only of integers. ] We have the tools we need to solve linear Diophantine equations. We will consider, as a main example, the equation #math.equation(block: true, alt: "51 x plus 87 y equals 123")[$51 x + 87 y = 123$] . The general strategy will be to convert the equation to a congruence, then solve that congruence. This is certainly not the only way to proceed. A more common technique would be to apply the #strong[Euclidean algorithm]. Our way can be a little faster, and is presented here primarily for variety. Let's work this particular example to see how this might go. First, check if perhaps there are no solutions because a divisor of #math.equation(block: false, alt: "51")[$51$] and #math.equation(block: false, alt: "87")[$87$] is not a divisor of #math.equation(block: false, alt: "123")[$123$]. Really, we just need to check whether #math.equation(block: false, alt: "gcd open parenthesis 51 , 87 close parenthesis ∣ 123")[$gcd ( 51 , 87 ) ∣ 123$]. This greatest common divisor is 3, and yes #math.equation(block: false, alt: "3 ∣ 123")[$3 ∣ 123$]. At this point, we might as well factor out this greatest common divisor. So instead, we will solve: #math.equation(block: true, alt: "17 x plus 29 y equals 41")[$17 x + 29 y = 41$] . Now observe that if there are going to be solutions, then for those values of #math.equation(block: false, alt: "x")[$x$] and #math.equation(block: false, alt: "y")[$y$], the two sides of the equation must have the same remainder as each other, no matter what we divide by. In particular, if we divide both sides by 17, we must get the same remainder. Thus we can safely write #math.equation(block: true, alt: "17 x plus 29 y ≡ 41 open parenthesis mod 17 close parenthesis")[$17 x + 29 y ≡ 41 #h(1em) ( mod #h(0.333em) 17 )$] . We choose 17 because #math.equation(block: false, alt: "17 x")[$17 x$] will have remainder 0. This will allow us to reduce the congruence to just one variable. We could have also moved to a congruence modulo 29, although there is usually a good reason to select the smaller choice, as this will allow us to reduce the other coefficient. In our case, we reduce the congruence as follows: #math.equation(block: true, alt: "17 x plus 29 y, ≡ 41 open parenthesis mod 17 close parenthesis; 0 x plus 12 y, ≡ 7 open parenthesis mod 17 close parenthesis; 12 y, ≡ 24 open parenthesis mod 17 close parenthesis; y, ≡ 2 open parenthesis mod 17 close parenthesis .")[$17 x + 29 y & ≡ 41 #h(1em) ( mod #h(0.333em) 17 ) \ 0 x + 12 y & ≡ 7 #h(1em) ( mod #h(0.333em) 17 ) \ 12 y & ≡ 24 #h(1em) ( mod #h(0.333em) 17 ) \ y & ≡ 2 #h(1em) ( mod #h(0.333em) 17 ) .$] Now at this point we know #math.equation(block: false, alt: "y equals 2 plus 17 k")[$y = 2 + 17 k$] will work for any integer #math.equation(block: false, alt: "k")[$k$]. If we haven't made a mistake, we should be able to plug this back into our original Diophantine equation to find #math.equation(block: false, alt: "x")[$x$]: #math.equation(block: true, alt: "17 x plus 29 open parenthesis 2 plus 17 k close parenthesis, equals 41; 17 x, equals minus 17 minus 29 times 17 k; x, equals minus 1 minus 29 k .")[$17 x + 29 ( 2 + 17 k ) & = 41 \ 17 x & = − 17 − 29 ⋅ 17 k \ x & = − 1 − 29 k .$] We have now found all solutions to the Diophantine equation. For each #math.equation(block: false, alt: "k")[$k$], #math.equation(block: false, alt: "x equals minus 1 minus 29 k")[$x = − 1 − 29 k$] and #math.equation(block: false, alt: "y equals 2 plus 17 k")[$y = 2 + 17 k$] will satisfy the equation. We could check this for a few cases. If #math.equation(block: false, alt: "k equals 0")[$k = 0$], the solution is #math.equation(block: false, alt: "open parenthesis minus 1 , 2 close parenthesis")[$( − 1 , 2 )$], and yes, #math.equation(block: false, alt: "minus 17 plus 2 times 29 equals 41")[$− 17 + 2 ⋅ 29 = 41$]. If #math.equation(block: false, alt: "k equals 3")[$k = 3$], the solution is #math.equation(block: false, alt: "open parenthesis minus 88 , 53 close parenthesis")[$( − 88 , 53 )$]. If #math.equation(block: false, alt: "k equals minus 2")[$k = − 2$], we get #math.equation(block: false, alt: "open parenthesis 57 , minus 32 close parenthesis")[$( 57 , − 32 )$]. To summarize this process, to solve #math.equation(block: false, alt: "a x plus b y equals c")[$a x + b y = c$], we, + Divide both sides of the equation by #math.equation(block: false, alt: "gcd open parenthesis a , b close parenthesis")[$gcd ( a , b )$] (if this does not leave the right-hand side as an integer, there are no solutions). Let's assume that #math.equation(block: false, alt: "a x plus b y equals c")[$a x + b y = c$] has already been reduced in this way. + Pick the smaller of #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] (here, assume it is #math.equation(block: false, alt: "b")[$b$]), and convert to a congruence modulo #math.equation(block: false, alt: "b")[$b$]: #math.equation(block: true, alt: "a x plus b y ≡ c open parenthesis mod b close parenthesis")[$a x + b y ≡ c #h(1em) ( mod #h(0.333em) b )$]. This will reduce to a congruence with one variable, #math.equation(block: false, alt: "x")[$x$]: #math.equation(block: true, alt: "a x ≡ c open parenthesis mod b close parenthesis")[$a x ≡ c #h(1em) ( mod #h(0.333em) b )$]. + Solve the congruence as we did in the previous section. Write your solution as an equation, such as, #math.equation(block: true, alt: "x equals n plus k b")[$x = n + k b$]. + Plug this into the original Diophantine equation, and solve for #math.equation(block: false, alt: "y")[$y$]. + If we want to know solutions in a particular range (for example, #math.equation(block: false, alt: "0 less than or equal to x , y less than or equal to 20")[$0 ≤ x , y ≤ 20$]), pick different values of #math.equation(block: false, alt: "k")[$k$] until you have all required solutions. Here is another example: #examplebox("Example 7")[][ How can you make \$6.37 using just 5-cent and 8-cent stamps? What is the smallest and largest number of stamps you could use? #solutionbox[ First, we need a Diophantine equation. We will work in numbers of cents. Let #math.equation(block: false, alt: "x")[$x$] be the number of #math.equation(block: false, alt: "5")[$5$]-cent stamps, and #math.equation(block: false, alt: "y")[$y$] be the number of 8-cent stamps. We have: #math.equation(block: true, alt: "5 x plus 8 y equals 637")[$5 x + 8 y = 637$] . Convert to a congruence and solve: #math.equation(block: true, alt: "8 y, ≡ 637 open parenthesis mod 5 close parenthesis; 3 y, ≡ 2 open parenthesis mod 5 close parenthesis; 3 y, ≡ 12 open parenthesis mod 5 close parenthesis; y, ≡ 4 open parenthesis mod 5 close parenthesis .")[$8 y & ≡ 637 #h(1em) ( mod #h(0.333em) 5 ) \ 3 y & ≡ 2 #h(1em) ( mod #h(0.333em) 5 ) \ 3 y & ≡ 12 #h(1em) ( mod #h(0.333em) 5 ) \ y & ≡ 4 #h(1em) ( mod #h(0.333em) 5 ) .$] Thus #math.equation(block: false, alt: "y equals 4 plus 5 k")[$y = 4 + 5 k$]. Then #math.equation(block: false, alt: "5 x plus 8 open parenthesis 4 plus 5 k close parenthesis equals 637")[$5 x + 8 ( 4 + 5 k ) = 637$], so #math.equation(block: false, alt: "x equals 121 minus 8 k")[$x = 121 − 8 k$]. This says that one way to make \$6.37 is to take 121 of the 5-cent stamps and 4 of the 8-cent stamps. To find the smallest and largest number of stamps, try different values of #math.equation(block: false, alt: "k")[$k$]. #figure(table( columns: 3, align: left, inset: 6pt, table.header([#math.equation(block: false, alt: "k")[$k$]], [#math.equation(block: false, alt: "open parenthesis x , y close parenthesis")[$( x , y )$]], [Stamps]), [], [], [], [-1], [(129, -1)], [not possible], [0], [(121, 4)], [125], [1], [(113, 9)], [122], [2], [(105, 13)], [119], [#math.equation(block: false, alt: "⋮")[$⋮$]], [#math.equation(block: false, alt: "⋮")[$⋮$]], [#math.equation(block: false, alt: "⋮")[$⋮$]], )) This is no surprise. Having the most stamps means we have as many 5-cent stamps as possible, and to get the smallest number of stamps would require have the least number of 5-cent stamps. To minimize the number of 5-cent stamps, we want to pick #math.equation(block: false, alt: "k")[$k$] so that #math.equation(block: false, alt: "121 minus 8 k")[$121 − 8 k$] is as small as possible (but still positive). When #math.equation(block: false, alt: "k equals 15")[$k = 15$], we have #math.equation(block: false, alt: "x equals 1")[$x = 1$] and #math.equation(block: false, alt: "y equals 79")[$y = 79$]. Therefore, to make \$6.37, you can us as few as 80 stamps (1 5-cent stamp and 79 8-cent stamps) or as many as 125 stamps (121 5-cent stamps and 4 8-cent stamps). ] ] Using this method, as long as you can solve linear congruences in one variable, you can solve linear Diophantine equations of two variables. There are times though that solving the linear congruence is a lot of work. For example, suppose you need to solve, #math.equation(block: true, alt: "13 x ≡ 6 open parenthesis mod 51 close parenthesis")[$13 x ≡ 6 #h(1em) ( mod #h(0.333em) 51 )$] . You #emph[could] keep adding 51 to the right side until you get a multiple of 13: You would get 57, 108, 159, 210, 261, 312, and 312 is the first of these that is divisible by 13. This works, but is really too much work. Instead we could convert #emph[back] to a Diophantine equation: #math.equation(block: true, alt: "13 x equals 6 plus 51 k")[$13 x = 6 + 51 k$] . Now solve #emph[this] like we have in this section. Write it as a congruence modulo 13: #math.equation(block: true, alt: "0, ≡ 6 plus 51 k open parenthesis mod 13 close parenthesis; minus 12 k, ≡ 6 open parenthesis mod 13 close parenthesis; 2 k, ≡ minus 1 open parenthesis mod 13 close parenthesis; 2 k, ≡ 12 open parenthesis mod 13 close parenthesis; k, ≡ 6 open parenthesis mod 13 close parenthesis .")[$0 & ≡ 6 + 51 k #h(1em) ( mod #h(0.333em) 13 ) \ − 12 k & ≡ 6 #h(1em) ( mod #h(0.333em) 13 ) \ 2 k & ≡ − 1 #h(1em) ( mod #h(0.333em) 13 ) \ 2 k & ≡ 12 #h(1em) ( mod #h(0.333em) 13 ) \ k & ≡ 6 #h(1em) ( mod #h(0.333em) 13 ) .$] so #math.equation(block: false, alt: "k equals 6 plus 13 j")[$k = 6 + 13 j$]. Now go back and figure out #math.equation(block: false, alt: "x")[$x$]: #math.equation(block: true, alt: "13 x, equals 6 plus 51 open parenthesis 6 plus 13 j close parenthesis; x, equals 24 plus 51 j .")[$13 x & = 6 + 51 ( 6 + 13 j ) \ x & = 24 + 51 j .$] Of course you could do this switching back and forth between congruences and Diophantine equations as many times as you like. If you #emph[only] used this technique, you would essentially replicate the Euclidean algorithm, a more standard way to solve Diophantine equations. Suppose #math.equation(block: false, alt: "a")[$a$], #math.equation(block: false, alt: "b")[$b$], and #math.equation(block: false, alt: "c")[$c$] are integers. Prove that if #math.equation(block: false, alt: "a ∣ b")[$a ∣ b$], then #math.equation(block: false, alt: "a ∣ b c")[$a ∣ b c$]. #solutionbox[ #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ Suppose #math.equation(block: false, alt: "a ∣ b")[$a ∣ b$]. Then #math.equation(block: false, alt: "b")[$b$] is a multiple of #math.equation(block: false, alt: "a")[$a$], or in other words, #math.equation(block: false, alt: "b equals a k")[$b = a k$] for some #math.equation(block: false, alt: "k")[$k$]. But then #math.equation(block: false, alt: "b c equals a k c")[$b c = a k c$], and since #math.equation(block: false, alt: "k c")[$k c$] is an integer, this says #math.equation(block: false, alt: "b c")[$b c$] is a multiple of #math.equation(block: false, alt: "a")[$a$]. In other words, #math.equation(block: false, alt: "a ∣ b c")[$a ∣ b c$]. ] ] Suppose #math.equation(block: false, alt: "a")[$a$], #math.equation(block: false, alt: "b")[$b$], and #math.equation(block: false, alt: "c")[$c$] are integers. Prove that if #math.equation(block: false, alt: "a ∣ b")[$a ∣ b$] and #math.equation(block: false, alt: "a ∣ c")[$a ∣ c$] then #math.equation(block: false, alt: "a ∣ b plus c")[$a ∣ b + c$] and #math.equation(block: false, alt: "a ∣ b minus c")[$a ∣ b − c$]. Write out the remainder classes for #math.equation(block: false, alt: "n equals 4")[$n = 4$]. #solutionbox[ #math.equation(block: true, alt: "open brace and so on , minus 8 , minus 4 , 0 , 4 , 8 , 12 , and so on close brace")[$\{ … , − 8 , − 4 , 0 , 4 , 8 , 12 , … \}$], #math.equation(block: true, alt: "open brace and so on , minus 7 , minus 3 , 1 , 5 , 9 , 13 , and so on close brace")[$\{ … , − 7 , − 3 , 1 , 5 , 9 , 13 , … \}$], #math.equation(block: false, alt: "open brace and so on , minus 6 , minus 2 , 2 , 6 , 10 , 14 , and so on close brace")[$\{ … , − 6 , − 2 , 2 , 6 , 10 , 14 , … \}$], and #math.equation(block: false, alt: "open brace and so on , minus 5 , minus 1 , 3 , 7 , 11 , 15 , and so on close brace")[$\{ … , − 5 , − 1 , 3 , 7 , 11 , 15 , … \}$]. ] What is the largest #math.equation(block: false, alt: "n")[$n$] such that #math.equation(block: false, alt: "16")[$16$] and #math.equation(block: false, alt: "25")[$25$] are in the same remainder class modulo #math.equation(block: false, alt: "n")[$n$]? Write out the remainder class they both belong to and give an example of a number more than 100 in that class. Let #math.equation(block: false, alt: "a")[$a$], #math.equation(block: false, alt: "b")[$b$], #math.equation(block: false, alt: "c")[$c$], and #math.equation(block: false, alt: "n")[$n$] be integers. Prove that if #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$] and #math.equation(block: false, alt: "c ≡ d open parenthesis mod n close parenthesis")[$c ≡ d #h(0.444em) ( mod #h(0.333em) n )$], then #math.equation(block: false, alt: "a minus c ≡ b minus d open parenthesis mod n close parenthesis")[$a − c ≡ b − d #h(0.444em) ( mod #h(0.333em) n )$]. #solutionbox[ #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ Assume #math.equation(block: false, alt: "a ≡ b open parenthesis mod n close parenthesis")[$a ≡ b #h(0.444em) ( mod #h(0.333em) n )$] and #math.equation(block: false, alt: "c ≡ d open parenthesis mod n close parenthesis")[$c ≡ d #h(0.444em) ( mod #h(0.333em) n )$]. This means #math.equation(block: false, alt: "a equals b plus k n")[$a = b + k n$] and #math.equation(block: false, alt: "c equals d plus j n")[$c = d + j n$] for some integers #math.equation(block: false, alt: "k")[$k$] and #math.equation(block: false, alt: "j")[$j$]. Consider #math.equation(block: false, alt: "a minus c")[$a − c$]. We have: #math.equation(block: true, alt: "a minus c equals b plus k n minus open parenthesis d plus j n close parenthesis equals b minus d plus open parenthesis k minus j close parenthesis n")[$a − c = b + k n − ( d + j n ) = b − d + ( k − j ) n$] . In other words, #math.equation(block: false, alt: "a minus c")[$a − c$] is #math.equation(block: false, alt: "b minus d")[$b − d$] more than some multiple of #math.equation(block: false, alt: "n")[$n$], so #math.equation(block: false, alt: "a minus c ≡ b minus d open parenthesis mod n close parenthesis")[$a − c ≡ b − d #h(0.444em) ( mod #h(0.333em) n )$]. ] ] Find the remainder of #math.equation(block: false, alt: "3 to the power 456")[$3^(456)$] when divided by + 2. + 5. + 7. + 9. #solutionbox[ + #math.equation(block: false, alt: "3 to the power 456 ≡ 1 to the power 456 equals 1 open parenthesis mod 2 close parenthesis")[$3^(456) ≡ 1^(456) = 1 #h(0.444em) ( mod #h(0.333em) 2 )$]. + #math.equation(block: false, alt: "3 to the power 456 equals 9 to the power 228 ≡ open parenthesis minus 1 close parenthesis to the power 228 equals 1 open parenthesis mod 5 close parenthesis")[$3^(456) = 9^(228) ≡ ( − 1 )^(228) = 1 #h(0.444em) ( mod #h(0.333em) 5 )$]. + #math.equation(block: false, alt: "3 to the power 456 equals 9 to the power 228 ≡ 2 to the power 228 equals 8 to the power 76 ≡ 1 to the power 76 equals 1 open parenthesis mod 7 close parenthesis")[$3^(456) = 9^(228) ≡ 2^(228) = 8^(76) ≡ 1^(76) = 1 #h(0.444em) ( mod #h(0.333em) 7 )$]. + #math.equation(block: false, alt: "3 to the power 456 equals 9 to the power 228 ≡ 0 to the power 228 equals 0 open parenthesis mod 9 close parenthesis")[$3^(456) = 9^(228) ≡ 0^(228) = 0 #h(0.444em) ( mod #h(0.333em) 9 )$]. ] Repeat the previous exercise, this time dividing #math.equation(block: false, alt: "2 to the power 2019")[$2^(2019)$]. Determine which of the following congruences have solutions, and find any solutions (between 0 and the modulus) by trial and error. + #math.equation(block: false, alt: "4 x ≡ 5 open parenthesis mod 6 close parenthesis")[$4 x ≡ 5 #h(0.444em) ( mod #h(0.333em) 6 )$]. + #math.equation(block: false, alt: "6 x ≡ 3 open parenthesis mod 9 close parenthesis")[$6 x ≡ 3 #h(0.444em) ( mod #h(0.333em) 9 )$]. + #math.equation(block: false, alt: "x squared ≡ 2 open parenthesis mod 4 close parenthesis")[$x^(2) ≡ 2 #h(0.444em) ( mod #h(0.333em) 4 )$]. #solutionbox[ For all of these, just plug in all integers between 0 and the modulus to see which, if any, work. + No solutions. + #math.equation(block: false, alt: "x equals 2")[$x = 2$], #math.equation(block: false, alt: "x equals 5")[$x = 5$], #math.equation(block: false, alt: "x equals 8")[$x = 8$]. + No solutions. ] Determine which of the following congruences have solutions, and find any solutions (between 0 and the modulus) by trial and error. + #math.equation(block: false, alt: "4 x ≡ 5 open parenthesis mod 7 close parenthesis")[$4 x ≡ 5 #h(0.444em) ( mod #h(0.333em) 7 )$]. + #math.equation(block: false, alt: "6 x ≡ 4 open parenthesis mod 9 close parenthesis")[$6 x ≡ 4 #h(0.444em) ( mod #h(0.333em) 9 )$]. + #math.equation(block: false, alt: "x squared ≡ 2 open parenthesis mod 7 close parenthesis")[$x^(2) ≡ 2 #h(0.444em) ( mod #h(0.333em) 7 )$]. Solve the following congruence #math.equation(block: false, alt: "5 x plus 8 ≡ 11 open parenthesis mod 22 close parenthesis")[$5 x + 8 ≡ 11 #h(0.444em) ( mod #h(0.333em) 22 )$]. That is, describe the general solution. #solutionbox[ #math.equation(block: false, alt: "x equals 5 plus 22 k")[$x = 5 + 22 k$] for #math.equation(block: false, alt: "k ∈ Z")[$k ∈ Z$]. ] Solve the congruence: #math.equation(block: false, alt: "6 x ≡ 4 open parenthesis mod 10 close parenthesis")[$6 x ≡ 4 #h(0.444em) ( mod #h(0.333em) 10 )$]. Solve the congruence: #math.equation(block: false, alt: "4 x ≡ 24 open parenthesis mod 30 close parenthesis")[$4 x ≡ 24 #h(0.444em) ( mod #h(0.333em) 30 )$]. #solutionbox[ #math.equation(block: false, alt: "x equals 6 plus 15 k")[$x = 6 + 15 k$] for #math.equation(block: false, alt: "k ∈ Z")[$k ∈ Z$]. ] Solve the congruence: #math.equation(block: false, alt: "341 x ≡ 2941 open parenthesis mod 9 close parenthesis")[$341 x ≡ 2941 #h(0.444em) ( mod #h(0.333em) 9 )$]. First reduce each number modulo 9, which can be done by adding up the digits of the numbers. I'm thinking of a number. If you multiply my number by 7, add 5, and divide the result by 11, you will be left with a remainder of 2. What remainder would you get if you divided my original number by 11? #solutionbox[ We must solve #math.equation(block: false, alt: "7 x plus 5 ≡ 2 open parenthesis mod 11 close parenthesis")[$7 x + 5 ≡ 2 #h(0.444em) ( mod #h(0.333em) 11 )$]. This gives #math.equation(block: false, alt: "x ≡ 9 open parenthesis mod 11 close parenthesis")[$x ≡ 9 #h(0.444em) ( mod #h(0.333em) 11 )$]. In general, #math.equation(block: false, alt: "x equals 9 plus 11 k")[$x = 9 + 11 k$], but when you divide any such #math.equation(block: false, alt: "x")[$x$] by 11, the remainder will be 9. ] Solve the following linear Diophantine equation, using modular arithmetic (describe the general solutions). #math.equation(block: true, alt: "6 x plus 10 y equals 32")[$6 x + 10 y = 32$] . #solutionbox[ Divide through by 2: #math.equation(block: false, alt: "3 x plus 5 y equals 16")[$3 x + 5 y = 16$]. Convert to a congruence, modulo 3: #math.equation(block: false, alt: "5 y ≡ 16 open parenthesis mod 3 close parenthesis")[$5 y ≡ 16 #h(0.444em) ( mod #h(0.333em) 3 )$], which reduces to #math.equation(block: false, alt: "2 y ≡ 1 open parenthesis mod 3 close parenthesis")[$2 y ≡ 1 #h(0.444em) ( mod #h(0.333em) 3 )$]. So #math.equation(block: false, alt: "y ≡ 2 open parenthesis mod 3 close parenthesis")[$y ≡ 2 #h(0.444em) ( mod #h(0.333em) 3 )$] or #math.equation(block: false, alt: "y equals 2 plus 3 k")[$y = 2 + 3 k$]. Plug this back into #math.equation(block: false, alt: "3 x plus 5 y equals 16")[$3 x + 5 y = 16$] and solve for #math.equation(block: false, alt: "x")[$x$], to get #math.equation(block: false, alt: "x equals 2 minus 5 k")[$x = 2 − 5 k$]. So the general solution is #math.equation(block: false, alt: "x equals 2 minus 5 k")[$x = 2 − 5 k$] and #math.equation(block: false, alt: "y equals 2 plus 3 k")[$y = 2 + 3 k$] for #math.equation(block: false, alt: "k ∈ Z")[$k ∈ Z$]. ] Solve the following linear Diophantine equation, using modular arithmetic (describe the general solutions). #math.equation(block: true, alt: "17 x plus 8 y equals 31")[$17 x + 8 y = 31$] . Solve the following linear Diophantine equation, using modular arithmetic (describe the general solutions). #math.equation(block: true, alt: "35 x plus 47 y equals 1")[$35 x + 47 y = 1$] . You have a 13 oz. bottle and a 20 oz. bottle, with which you wish to measure exactly 2 oz. However, you have a limited supply of water. If any water enters either bottle and then gets dumped out, it is gone forever. What is the least amount of water you can start with and still complete the task? Solve the Diophantine equation #math.equation(block: false, alt: "13 x plus 20 y equals 2")[$13 x + 20 y = 2$] (why?). Then consider which value of #math.equation(block: false, alt: "k")[$k$] (the parameter in the solution) is optimal.