Modular Arithmetic

10 Key excerpts on "Modular Arithmetic"

• 

  eBook - PDF

  An Experimental Introduction to Number Theory

  • Benjamin Hutz(Author)
  • 2018(Publication Date)
  • American Mathematical Society

    (Publisher)

  Chapter 2 Modular Arithmetic 1. Basic Arithmetic We saw in Chapter 1 that given any two positive integers n and m , we can always split a collection of n objects into groups of m with possibly some number left over. We expressed this mathematically as the division algorithm (Theorem 1.8), n = qm + r, 0 ≤ r < m. We call this unique r the remainder after division by m . In this chapter we explore the arithmetic of these remainders. For example, consider two people each with some number of apples. One person has one apple left over after dividing his apples into groups of five and the other person has two apples left over when dividing her apples into groups of five. If these two people combine their apples, the resulting total number of apples has three left over when divided into groups of five. Notice that the total remainder does not depend how many groups of five each person has, only the remainder left over. We have added their remainders together. + = Another familiar example is a 12-hour clock, which divides the time into groups of twelve, and the current time is the remainder. For example, if it is currently 11 a.m., what time is 4 hours later? The answer is of course 3 p.m. The mathematics behind this answer is to take 11 + 4 = 15 and consider the remainder after division by 12: 15 = 1 · 12 + 3 . To make a formal definition we use the language of divisibility. Definition 2.1. Let a , r , and n be integers with n > 0. We say that a is congruent to r modulo n if n divides ( a − r ), i.e., n | ( a − r ), and we write a ≡ r (mod n ). The number n is called the modulus . 39 40 2. Modular Arithmetic Example 2.2. Our clock example becomes 15 ≡ 3 mod 12 since 12 | (15 − 3) . Keep in mind that the previous definition is really just remainder after division as in the division algorithm.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Cryptography

  Theory and Practice

  • Douglas Robert Stinson, Maura Paterson(Authors)
  • 2018(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  Appendix A Number Theory and Algebraic Concepts for Cryptography A.1 Modular Arithmetic Definition A.1.1 (congruences) Suppose a and b are integers, and m is a positive integer. Then we write a ≡ b ( mod m ) if m divides b -a . The phrase a ≡ b ( mod m ) is called a congruence , and it is read as “ a is congruent to b modulo m .” The integer m is called the modulus . Definition A.1.2 (modular reduction) Suppose we divide a and b by m , obtaining integer quotients and remainders, where the remainders are between 0 and m -1. That is, a = q 1 m + r 1 and b = q 2 m + r 2 , where 0 ≤ r 1 ≤ m -1 and 0 ≤ r 2 ≤ m -1. Then it is not difficult to see that a ≡ b ( mod m ) if and only if r 1 = r 2 . We will use the notation a mod m (without parentheses) to denote the remainder when a is divided by m , i.e., the value r 1 above. Thus a ≡ b ( mod m ) if and only if a mod m = b mod m . If we replace a by a mod m , we say that a is reduced modulo m . This process is called modular reduction . Example A.1.3 To compute 101 mod 7, we write 101 = 7 × 14 + 3. Since 0 ≤ 3 ≤ 6, it follows that 101 mod 7 = 3. As another example, suppose we want to compute ( -101 ) mod 7. In this case, we write -101 = 7 × ( -15 ) + 4. Since 0 ≤ 4 ≤ 6, it follows that ( -101 ) mod 7 = 4. Remark A.1.4 Some computer programming languages define a mod m to be the remainder in the range -m + 1, . . . , m -1 having the same sign as a . For example, ( -101 ) mod 7 would be -3, rather than 4 as we defined it above. But for our pur-poses, it is much more convenient to define a mod m always to be non-negative. Definition A.1.5 (arithmetic modulo m ) We now define arithmetic modulo m : Z m is the set { 0, . . . , m -1 } , equipped with two operations, + (addition) and · (multi-plication). Addition and multiplication in Z m work exactly like real addition and multiplication, except that the results are reduced modulo m . Example A.1.6 Suppose we want to compute 11 + 13 in Z 16 .

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Elementary Number Theory with Programming

  • Marty Lewinter, Jeanine Meyer(Authors)
  • 2015(Publication Date)
  • Wiley

    (Publisher)

  5 Modular Arithmetic

  Modular Arithmetic sheds light on the relation of integers to their remainders when they are divided by a given positive integer. It is useful in both number theory and computer science.

  CONGRUENCE CLASSES MOD k

  The integers behave in a periodic way when we examine their expressions as one of the forms, for example, 3n, 3n + 1, and 3n + 2. Every third integer is a multiple of 3 and can therefore be written 3n for some integer n. Thus, 3 = 3 × 1, 6 = 3 × 2, 9 = 3 × 3, 12 = 3 × 4, and so on. On the other hand, the numbers 4, 7, 10, 13, etc. can be written 3n + 1, since they are one more than some multiple of 3. Similarly, 5, 8, 11, 14, etc. can be written 3n + 2. Thus, the sequence of consecutive numbers 3, 4, 5 yield numbers of the form 3n, 3n + 1, and 3n + 2. The next number, 6, signifies that the pattern repeats. In fact, the next three numbers, 6, 7, 8, mimic their three predecessors perfectly, following the same format as 3n, 3n + 1, 3n + 2. Of course, the n changes from 1 to 2, but the pattern persists. Every third number is of the same format.

  There are three classes of numbers: 3n, 3n + 1, and 3n + 2. All numbers belong to one of these mutually exclusive and jointly exhaustive classes. Even 0 is a member of one of the classes, namely, the 3n class. Negative numbers are included, as well, since n may be negative.

  The entire analysis can be repeated for the coefficient 5 or any other coefficient. Every integer is in one of the forms 5n, 5n + 1, 5n + 2, 5n + 3, and 5n + 4. Of course, if we continued this consecutive sequence to 5n + 5, we would needlessly be introducing an extra class, since 5n + 5 = 5(n + 1), which is in the same class as 5n. One could let m = n + 1, in which case 5n + 5 = 5m. There’s nothing sacred about n.

  Notice there are five classes when we use the coefficient 5 and, more generally, there are k classes when we use the coefficient k. Instead of the word coefficient, mathematicians refer to the modulus k. The k classes are called congruence classes mod k, and the whole subject is called Modular Arithmetic. Two numbers, a and b, in the same class are called congruent mod k. This is written a = b (mod k). If a and b belong to different classes, they are called incongruent mod k. This is written a ≠ b (mod k

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Mathematical Excursions

  • Richard Aufmann, Joanne Lockwood, Richard Nation, Daniel K. Clegg(Authors)
  • 2017(Publication Date)
  • Cengage Learning EMEA

    (Publisher)

  457 8.1 Modular Arithmetic 8.2 Applications of Modular Arithmetic 8.3 Introduction to Group Theory Mathematical Systems It’s a dark, rainy night as you pull up to the drive at your home. You press a remote in your car that opens your garage door and you drive in. You press the remote again and the garage door closes. Unbeknownst to you, there is a crook lurking on the street with a radio scanner who picks up the signal from your remote. The next time you’re not home, the crook plans on using the saved signal to open your garage door and burglarize your home. However, when the crook arrives and sends the signal, the door doesn’t open. Now suppose you want to make a purchase on the Internet using a credit card. You may have noticed that the typical http:// that precedes a web address is replaced by https://. The “s” at the end indicates a secure website. This means that someone who may be trying to steal credit card information cannot inter- cept the information you send. Although a garage door opener and a secure website may seem to be quite different, the mathematics behind each of these is similar. Both are based on mod- ular arithmetic, one of the topics of this chapter. Modular Arithmetic, in turn, is part of a branch of mathematics called group theory, another topic in this chapter. Group theory is used in a variety of many seem- ingly unrelated subjects such as the structure of a diamond, wall- paper patterns, quantum physics, and the 12-tone chromatic scale in music. 8 AptTone/Shutterstock.com MrJafari/Shutterstock.com ussr/Shutterstock.com dencg/Shutterstock.com All of these are related to group theory. Copyright 2018 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s). Editorial review has deemed that any suppressed content does not materially affect the overall learning experience.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Fundamental Number Theory with Applications

  • Richard A. Mollin(Author)
  • 2008(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  The following gathers together the totality of the laws underlying Modular Arithmetic that will give us the structure to dive deeper into number-theoretic concepts and their applications. The reader is encouraged to review the funda-mental laws for arithmetic beginning on page 289, so that we will see that these seemingly trivial laws have a generalization to the following important scenario. Theorem 2.1 Modular Arithmetic Let n ∈ N and suppose that for any x ∈ Z , x denotes the congruence class of x modulo n . Then for any a, b, c ∈ Z the following hold. 78 2. Modular Arithmetic (a) a ± b = a ± b . (Modular additive closure) (b) a b = ab . (Modular multiplicative closure) (c) a + b = b + a . (Commutativity of modular addition) (d) ( a + b ) + c = a + ( b + c ). (Associativity of modular addition) (e) 0 + a = a + 0 = a . (Additive modular identity) (f) a + -a = -a + a = -a + a = 0. (Additive modular inverse) (g) a b = b a . (Commutativity of modular multiplication) (h) ( a b ) c = a ( b c ). (Associativity of modular multiplication) (i) 1 a = a 1 = a . (Multiplicative modular identity) (j) a ( b + c ) = a b + a c . (Modular distributivity) Proof . Parts (a)–(b) are a consequence of Proposition 2.1. Also see Re-mark 2.3 on page 74. Part (c) can be established using part (a) since a + b = a + b = b + a = b + a. In other words, the commutativity property is inherited from the integers Z . Part (d) also follows from part (a) since ( a + b ) + c = a + b + c = a + b + c = a + ( b + c ) = a + ( b + c ) . Part (e) is a consequence of parts (c) and (a) since 0 + a = a + 0 = a + 0 = a , where the first equality holds by part (c) and the second equality holds by part (a). The first equality of part (f) follows from parts (a) and (c) in exactly the same fashion, whereas the second part follows from part (b). Part (g) follows from the ordinary commutativity of multiplication of integers and part (b), since a b = ab = ba = b a .

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  A Concrete Approach to Abstract Algebra

  • W. W. Sawyer(Author)
  • 2018(Publication Date)
  • Dover Publications

    (Publisher)

  Chapter 2 Arithmetics and Polynomials

  WE HAVE NOW met three kinds of arithmetic. Our ordinary arithmetic is the first kind. It deals with numbers 0, 1, 2, · · · , that go on forever.

  The arithmetic modulo 5 is the second kind. It contains only 0, 1,2, 3, 4, but in spite of this it is remarkably like ordinary arithmetic. I can still ask you quite conventional questions in algebra—to multiply expressions, to do long division, to solve a quadratic, to factor a polynomial, to prove the remainder theorem.

  The third type is shown by arithmetic modulo 4 or modulo 6. It diverges still further from ordinary arithmetic. A quadratic may have more than two roots; still more striking, division ceases to be possible. In modulo 6 arithmetic, 3 ÷ 2 has no answer, while 4 ÷ 2 has the answers 2 and 5. However, some similarities to ordinary arithmetic remain. We can still multiply without restriction. We can divide by 1 and 5, and this means that we can divide by x – a or 5x – a. The remainder theorem, that a polynomial f(x) on division by x – a leaves the remainder f (a ), still makes sense and is true.

  It will be helpful in considering these arithmetics, and other structures that we shall meet, to tabulate their properties. On the left side of our table, we write our statements (1 ) through (12 ). Across the top of the table, we write the names of the structures we plan to "test." If a structure satisfies the tests, or statements, we enter a plus sign in the proper column. If a structure fails to satisfy a test, or statement, we enter a zero. It is often the property that is lacking that gives a peculiar flavor.

  Across the top of our table we have the following structures listed: (i) The rational numbers; (ii) The natural numbers 0, 1, 2, · · ·; (iii) The integers 0, ±l, ±2, · · ·; (iv) The arithmetic modulo 5; (v) The arithmetic modulo 6.

  In future, we shall define various types of structures by saying which tests are passed. A table of this kind gives a convenient way of recording definitions and of classifying any particular structure.

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  The Joy of SET

  The Many Mathematical Dimensions of a Seemingly Simple Card Game

  • Liz McMahon, Gary Gordon, Hannah Gordon, Rebecca Gordon(Authors)
  • 2016(Publication Date)
  • Princeton University Press

    (Publisher)

  4 SET and Modular Arithmetic 4.1 WHAT IS Modular Arithmetic? Three more of your friends, S hamella, E rin, and T yler, heard what everyone else was up to and decided to join the fun and become characters in our book. They have just begun college, and Shamella is eager to tell them about her new math course, number theory. S HAMELLA : Today my math teacher showed us some interesting applications of Modular Arithmetic. E RIN : What is Modular Arithmetic? T YLER : Wait, we saw this in the first chapter! It’s sometimes called clock arithmetic. E RIN : Oh yeah, I remember now! We did a clock problem. We learned how to figure out what time it will be 100 hours from now. Or any number of hours from now. S HAMELLA : Yeah, clocks are the most natural example of Modular Arithmetic. Days of the week can also work, and months, because calendars are cyclic ...and also music scales, because those repeat! But my teacher showed us some uses that answer more abstract questions. Before our group continues, here’s a reminder of the notation we mentioned in chapter 1: we will write a = b (mod c ) if a and b have the same remainder when divided by c . So, as we saw in chapter 1, 110 = 14 (mod 24), because when you divide 110 by 24, you get a remainder of 14. (One quick note: “mod” is short for “modulo.” We also say 24 is the “modulus” we’re working with here.) SET and Modular Arithmetic • 73 4.2 Modular Arithmetic PROBLEMS Our three students find the following problem in Shamella’s homework assignment. Question 1 : What is the last digit of 1987 1987 ? E RIN : I have no idea how to do this problem. T YLER : Me neither! I just typed it into my calculator, and it said “OVERFLOW.” E RIN : Great—I’ll just write that down for the answer. Thanks. S HAMELLA : All right everyone, calm down. This isn’t as hard as it looks. We can start by doing simpler versions of this problem.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Number Systems

  A Path into Rigorous Mathematics

  • Anthony Kay(Author)
  • 2021(Publication Date)
  • CRC Press

    (Publisher)

  [Hints: 9, 999, 999, 999, 999 = 10 13 − 1 ; note that 10 2 = 2 × 53 − 6.] 5.5 Modular Arithmetic Since congruence modulo d is an equivalence relation on ℤ, it partitions ℤ into equivalence classes, known as congruence classes : Definition 5.5.1. For any d ∈ ℕ let r be an allowed remainder on division by d (i.e. r ∈ ℤ with 0 ≤ r < d). Then the congruence class [ r ] d is the set of all integers with remainder r on division by d : [ r ] d : = { n ∈ ℤ : n = q d + r ; q ∈ ℤ }. Thus the members of a congruence class are all the integers that are congruent to r modulo d. Example 5.5.2. (i) [ 3 ] 5 = { …, − 12, − 7, − 2, 3, 8, 13, … } : there are infinitely many positive and negative integers with remainder 3 on division by 5. (ii) We can write the set of all even integers. as [ 0 ] 2 and the set of all odd integers as [ 1 ] 2. For each d ∈ ℕ \ { 1 } we can now define a new number system, ℤ d, in which each number is a congruence class modulo d. [We have done something similar before: Definition 4.1.4 also defines each integer as an equivalence class containing infinitely many objects.] Definition 5.5.3. For each d ∈ ℕ \ { 1 }, ℤ d : = { [ r ] d : r ∈ ℤ, 0 ≤ r < d }. This is a finite number system, since there are d congruence classes modulo d : we could write Definition 5.5.3 as ℤ d = { [ 0 ] d, [ 1 ] d, …, [ d − 1 ] d }. This method of using a finite set of integers to represent quantities that can in principle take infinitely many integer values is common in. our daily lives, particularly in our representation of time. The 12-hour clock is an application of ℤ 12, representing each hour by its “remainder” after noon or midnight when the half-day is divided by 12 – although in the case of zero remainder, we refer to “12 o’clock” rather than “0 o’clock”

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Introduction to Number Theory

  • Mark Hunacek(Author)
  • 2023(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  2 Congruences and Modular Arithmetic

  DOI: 10.1201/9781003318712-3

  Let us begin with a simple motivating problem: If today is Monday, what day will it be 200 days from now? At first glance this seems like a cumbersome problem to answer, until we recognize a simple trick: 7 days from now, it will be Monday again. It will also be Monday 14 days from now, 21 days from now, etc. In particular, it will be Monday 196 days from now, because 196 is a multiple of 7. So, since we “reset the clock” at day 196, the original question posed is equivalent to asking what day it will be 4 days from now, and the answer to that is obvious: Friday.

  The idea here (counting until we get to a certain number, then “equating” that number with 0, and resuming counting from scratch) is simple but very important in number theory. It is formalized in the definition of congruence modulo n, the concept to which we now turn.

  2.1 Basic Definitions and Principles

  Let us begin with a definition that captures the ideas spoken of above.

  Definition 2.1.1

  If a, b and n are integers, with n positive, we say that a is congruent to b, modulo n (written

  a ≡ b

  (mod n)), if n divides a – b.

  So, for example, 200 ≡ 4 (mod 7), which is the point of the motivating example above. Likewise, 10 is not congruent to 3 modulo 5. Question for the reader: why do we not bother defining “congruence modulo 0”?

  The following theorem says, for those who know the terminology from a previous course, that “congruence modulo n” is an equivalence relation.

  Theorem 2.1.2

  Let a, b, c and n be integers, with n positive. Then

  1. a ≡ a (mod n) (reflexivity)
  2. if a ≡ b (mod n), then b ≡ a (mod n) (symmetry)
  3. if a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n) (transitivity)

  Proof. We prove (iii), and leave the similar (but easier) proofs of (i) and (ii) to the reader. To prove (iii), note that we are given that n ∣ a – b and n ∣ b – c. It follows from our basic properties of divisibility that n ∣ (a – b) + (b – c) or, equivalently, n ∣ a – c. But this is precisely the same as saying that a ≡ c (mod n

  Sign up to read

  Learn more about book
• 

  eBook - PDF

  Elementary Number Theory in Nine Chapters

  • James J. Tattersall(Author)
  • 2005(Publication Date)
  • Cambridge University Press

    (Publisher)

  5 Modular Arithmetic Even if you are on the right track, you’ll get run over if you just sit there. Will Rogers 5.1 Congruence In this section, we introduce a concept of fundamental importance that will revolutionize the way we regard problems concerning divisibility. Albeit the underlying ideas have Indian and Chinese origins and Euler investigated some basic properties of remainders, it was Gauss who, in 1801, introduced the modern concepts of congruence and the arithmetic of residue classes to European audiences in Disquisitiones arithmeticae ( Arithmetical Investiga- tions) when he was 24. Gauss considered number theory to be the queen of mathematics. To him, its magical charm and inexhaustible wealth of intriguing problems placed it on a level way above other branches of mathematics. We owe a debt of gratitude to mathematicians such as Euler, Lagrange, Legendre, and Gauss for treating number theory as a branch of mathematics and not just a collection of interesting problems. Given three integers a, b, and m, with m > 2, we say that a is congruent to b modulo m, denoted by a  b (mod m), if a and b yield the same remainder or residue when divided by m. Equivalently, a  b (mod m), if there is an integer k such that a  b ¼ km, that is, their difference is divisible by m. If a is not congruent to b modulo m we write a 6 b (mod m). For example, 52  38 (mod 7) since 52  38 ¼ 14 ¼ 2 . 7. If a ¼ mq þ r, with 0 < r , m, then r is called the least residue of a modulo m. The least residue of 58 modulo 4 is 2 since 58 ¼ 4 . 14 þ 2 and 0 < 2 , 4. If the columns for the residue classes modulo 4 in Table 5.1 below were extended, 58 would appear in the penultimate column. The ability to effectively replace congruences with equalities and vice versa will be of crucial importance in solving problems. For example, 5x  6 (mod 11) if and only if there is an integer k such that 5x ¼ 6 þ 11 k . Similarly, if 3x þ 5 y ¼ 7, then 3x  7 (mod 5) and 5 y  7 (mod 3).

  Sign up to read

  Learn more about book