1.6: Modular Arithmetic

MGF 1131: Mathematics in Context (FSW) · LibreTexts

0%

Contents

    Text

    Size
    100%
    Theme
    Typeface
    Line length
    Spacing

    From LibreTexts, under CC BY 4.0, as the source states it; its equations are written in TeX, which the PDF shows typeset. This page at LibreTexts.

    Three hands are shown. Two are working on a single laptop while a third holds a credit card.
    Figure \(\PageIndex{1}:\) If a credit card number is entered incorrectly, error checking algorithms will often catch the mistake. (credit: modification of work “Senior couple at home checking finance on credit card from above” by Nenad Stojkovic/Flickr, CC BY 2.0)
    Learning Objectives

    After completing this section, you should be able to:

    1. Add, subtract using modulo arithmetic.
    2. Apply modular arithmetic to calculate real-world applications.

    Working with Mod

    Online shopping requires you to enter your credit card number, which is then sent electronically to the vendor. Using an ATM involves sliding your bank card into a reader, which then reads, sends, and verifies your card. Swiping or tapping for a purchase in a brick–and-mortar store is how your card sends its information to the machine, which is then communicated to the store’s computer and your credit card company. This information is read, recorded, and transferred many times. Each instance provides one more opportunity for error to creep into the process, a misrecorded digit, transposed digits, or missing digits. Fortunately, these card numbers have a built-in error-checking system that relies on modular arithmetic, which is often referred to as clock arithmetic. In this section, we explore clock, or modular, arithmetic.

    We want to create a new system of arithmetic based on remainders, always keeping in mind the number we are dividing by, known as the modulus. Modular arithmetic is a system of arithmetic for integers where numbers "wrap around" upon reaching a certain value—the modulus. This concept is often referred to as "clock arithmetic" because it resembles how we tell time on a \(12\)-hour clock.

    For example, in a "days of the week" scenario, the modulus is \(7.\) The possible remainders we can get are \(0, 1, 2, 3, 4, 5,\) and \(6,\) with each remainder representing a different day of the week. Similarly, in a "months of the year" problem, the modulus is \(12.\) We typically assign numbers to days like the following.

     

    Table displaying days of the week with corresponding numbers: starting with Sunday 0.
     

    Figure \(\PageIndex{2}:\) Assigning numbers to days

    What is Mod? Example of Mod

    Let \(a\) be a positive integer. Then \(a\) modulo \(b,\) written \(a\) mod \(b,\) is the remainder when \(a\) is divided by \(b.\)

    \(17 ~\text{mod}~ 5?\)

    To find \(17~\text{mod} ~5\) we divide \(17\) by \(5\) and find the remainder.

    \(17 ÷ 5 = 3~\text{remainder of } 2~\)

    Because \(5\times 3 = 15\) and \(17 - 15 = 2.\) So \(17~\text{mod}~5 = 2\)

    How to Find the Mod of a Negative Number?

    \(-a\) mod \(b\) is same as \([b-(a~\text{mod}~ b)]\)
    For example, \(-12~\text{mod} ~5 = 5-(12 ~\text{mod} ~5) = 5-2=3\)

    When we do arithmetic, numbers can become larger and larger. But when we work with time, specifically with clocks, the numbers cycle back on themselves. It will never be \(49\) o’clock. Once \(12\) o’clock is reached, we go back to \(1\) and repeat the numbers. If it's \(11\) AM and someone says, “See you in four hours,” you know that \(11\)AM plus \(4\) hours is \(3\) PM, not \(15\) AM (ignoring military time for now). Math worked on the clock, where numbers restart after passing \(12,\) is called clock arithmetic.

    Clock arithmetic hinges on the number \(12.\) Each cycle of \(12\) hours returns to the original time Figure \(\PageIndex{3}.\) Imagine going around the clock one full time. Twelve hours pass, but the time is the same. So, if it is \(3:00,\) \(14\) hours later and two hours later, both read the same on the clock, \(5:00.\) Adding \(14\) hours and adding \(2\) hours are identical. As is adding \(26\) hours. And adding \(38\) hours.

    An analog clock with the hour hand pointing to 3.
     
    Figure \(\PageIndex{3}:\) lock showing \(3:00\) o'clock with arrow going around the clock one full time, or \(12\) hours

    What do \(2, 14, 26,\) and \(38\) have in common in relation to \(12?\) When they are divided by \(12,\) they each have a remainder of \(2.\) That's the key. When you add a number of hours to a specific time on the clock, first divide the number of hours being added by 12 and determine the remainder. Add that remainder to the time on the clock to know what time it will be.

    A good visualization is to wrap a number line around the clock, with the \(0\) at the starting time. Then, each time \(12\) on the number line passes, the number line passes the starting spot on the clock. This is referred to as modulo \(12\) arithmetic. Even though the process says to divide the number being added by \(12 \) first, perform the addition; the result will be the same if you add the numbers first, and then divide by \(12\) and determine the remainder

    Example \(\PageIndex{1}\)

    Find the value of the following numbers modulo.

    1. \(88 \;\text{mod} \;7\)
    2. \(539 \;\text{mod}\; 12\)
    3. \(-40 \;\text{mod}\; 7\)
    Answer a

    To find \(88 ~\text{mod} ~7,\) we divide \(88\) by \(7\) and find the remainder. \[88 \div 7=12\)~ \text{remainder of}~ \(4\). So \[88 ~\text{mod} \;7= 4\nonumber\]

    Answer b

    To find \(539 ~\text{mod} ~12\) we divide \(539\) by \(12\) and find the remainder. \[539\div12=44~\text{remainder of}~ 11\] So \[539 ~\text{mod} ~12=11\nonumber\]

    Answer c

    Note that \(-a\) mod \(b\) is same as \(b-(a~\text{mod}~ b)\) So \(-40 ~\text{mod}~ 7 = (7-(40 ~\text{mod}~7) = 7-5=2\)

    Your Turn \(\PageIndex{1}\): Find Mod

    Working with Clock Using Modular Arithmetic

    Clock arithmetic is modulo \(12\) arithmetic, but applied to time. As time is divided into \(12\) hours that repeat a cycle, we use modulo \(12\) for clock arithmetic.

    Example \(\PageIndex{2}\): Find Future Time or Past Time
    1. If it is \(3:00\) o'clock now, what time will it be in \(89\) hours?
    2. If it is \(4:00\) o'clock now, what time was it \(67\) hours ago?
    Answer

    \(1.\) To find that future time, we may determine the value of \(89 \;\text{mod} \;12\)

    \(89\div12=4\; \text{remainder of}\; 5\). So \(89 \;\text{mod} \;12=5.\) Counting \(5\) hours from to \(3:00\) o'clcok results in \(8:00.\)

    \(2.\) To find that past time, we may determine the value of \(67 \;\text{mod} \;12.\)

    \(67\div12=5\; \text{remainder of}\; 7\). So \(67 \;\text{mod} \;12=7.\) Counting \(7\) hours backward from to \(4:00\) o'clcok results in \(9:00.\)We see this in the Figure \(\PageIndex{4}.\)

     

    An analog clock with the hour hand pointing to 4.

    Figure \(\PageIndex{4}:\) Clock showing \(7\) hours subtracted from \(4:00\)

    Your Turn \(\PageIndex{2}\): Find the Time in Past and Future
    \(24\) Hours Clock

    Clock arithmetic in modulo \(24\) (also called mod \(24\) arithmetic ) is used to represent time on a \(24\)-hour clock. It is similar to clock \(12\) arithmetic.

    Modulo \(24\) means we only care about the remainder after dividing by \(24.\) For example:

    1. \(25\;\text{mod} \;24=1\)
    2. \(48\;\text{mod}\; 24=0\)
    Example \(\PageIndex{3}\) Applying Clock Arithmetic
    1. Suppose it is \(3:00,\) and you decide to check your email every \(5\) hours. What time will it be when you check your email the ninth time?
    2. Your family has a cat, and no one wants to empty the litter box. However, it has to be done daily. The six of you agree to take turns, so everyone has to empty the litter box every \(6\) days. You empty the box on a Thursday. What day will you empty the box for the 10th time?
    Answer

    \(1.\) If you check your email every \(5\) hours nine times, that ninth check will occur \(45\) hours after \(3:00,\) which is an addition of \(45\) hours to \(3:00.\) So, we find \(45\) modulo \(12,\) which is \(9.\) Nine hours after \(3:00\) is \(12:00.\) It will be \(12:00\) when you check your email the ninth time.

    \(2.\) The first time you emptied the litter box was on a Thursday. So, the \(10\) th time you empty the litter box will be \(9\) times later (you've already had your first turn, so \(9\) turns left!). This will happen \(54 (9\times 6)\) days later. Finding the value of \(54\) modulo \(7,\) that is \(54\;\text{mod} \;7\) gives the answer \(5.\) Five days after a Thursday is Tuesday.

    Your Turn \(\PageIndex{3}\)

    \(1.\) You have agreed to text your friend every \(3\) hours while driving across the country. You began your trip at \(8\) AM. What time will it be when you text your friend the \(15\)th time?

    \(2.\) Your family shares the cooking duties in the home. You've agreed to prepare the meal every \(5\) days. The last time you prepared dinner was on a Tuesday. What day of the week will it be after you've prepared the meals \(20\) more times?

    Working with Days Using Modular Arithmetic

    Clock arithmetic processes can be applied to days of the week. Every \(7\) days the day of the week repeats, much like every \(12\) hours the time on the clock repeats. The only difference will be that we work with remainders after dividing by \(7.\) In technical terms, this is referred to as modulo \(7.\) More generally, let \(n\) be a positive integer. Then \(n\) modulo \(7,\) written \(n\) mod \(7,\) is the remainder when \(n\) is divided by \(7.\)

    If today is Tuesday, what day will it be in 10 days?

    In Figure \(\PageIndex{2},\) we know Tuesday = \(2\)

    \((2+10) \;\text{mod} \; 7 = 12\;\text{mod} \;7 =5.\) From the table in the Figure \(\PageIndex{1},\) \(5\) corresponds to Friday.

    Example \(\PageIndex{4}\): Find Future Day or Past Days

    \(1.\) If today is Thursday, what day is it \(1000\) days from today?

    \(2.\) If today is Saturday, what day was it \(100\) days ago?

    Answer

    \(1.\) Since there are \(7\) days in a week, every \(7\) days we will return to Thursday, if today is Thursday. If we divide \(1000\) by \(7,\) we get a remainder of \(6.\) This is the same as finding \(1000 \;\text{mod} \;7,\) which is \(6.\) So we count \(6\) days forward starting from Thursday.

    \(1\) day after Thursday is → Friday

    \(2\) days after Thursday is → Saturday

    ..

    ..

    \(6\) days after Thursday is → Wednesday

    There is another way to solve this problem. Thursday is \(4,\) see the above table. Now \(4+1000 =1004.\) \(1004\;\text{mod}\; 7\;\text{ is}\; 3\) (This is the same as saying when we divide \(1004\) by \(7,\) we get a remainder of \(3\)). From table in the Figure \(\PageIndex{2},\) \(3\) corresponds to Wednesday.

    \(2.\) We divide \(100\) by \(7,\) and we get a remainder of \(2.\) This is the same as finding \(100 \;\text{mod} \;7= 2.\) So we count \(2\) days backward starting from Saturday.

    \(1\) day before Saturday → Friday

    \(2\) days before Saturday → Thursday

    There is another way to solve this problem. Thursday is \(6\), see the above table. Now \(6-100 = -94.\)

    Since \(-a\) mod \(b\) is same as \(b-(a\;\text{mod}\; b)\)
    \(-94 \;\text{mod}\; 7 = 7-(94 \;\text{mod} \;7) = 7-3=4\)

    From table in the Figure \(\PageIndex{2},\) the number \(4\) corresponds to Thursday.

    Your Turn \(\PageIndex{4}\): Find the Future and Past Day

    Working with months using Modular Arithmetic

    When working with months of the year, we use modulo \(12\) arithmetic, since there are \(12\) months in a year.

    Note: Assigning Numbers to Months

    We can number the months with our possible remainders, \(0\) through \(11.\) We could start with \(0\) for January, \(1\) for February, etc., but this wouldn’t match up with our standard numbering. Instead, we’ll start with \(1\) for January, \(2\) for February, etc., up to \(11\) for November. We can’t use \(12\) for December because \(12\) isn’t a valid remainder. We’ll use \(0\) for December.

    A table displaying numerical data across multiple columns labeled with months of the year.
    Figure \(\PageIndex{5}\): Assigning numbers to months
    Example \(\PageIndex{5}\): Find the Future and Past Month

    \(1.\) If this month is April, what month will it be \(100\) months from this month?

    \(2.\) If the month is April, what month was it \(27\) months ago?

    Answer

    \(1.\) To find what month it will be \(100\) months from April, we can use modular arithmetic. There are \(12\) months in a year, so:

    \(100 \;\text{mod} \;12= 4.\) This means \(100\) months from now is \(4\) months ahead of April.

    Starting from April and counting \(4\) months forward:

    \(1\) month after April → May

    \(2\) months after April is → June

    \(3\) months after April is → July

    \(4\) months after April is → August

    There is another way to solve this problem. April is \(4,\) see the above table in Figure \(\PageIndex{5}.\) Now \(4+100 =104.\) \(104\;\text{mod}\; 12\;\text{ is}\; 8\) (This is the same as saying when we divide \(104\) by \(12,\) we get a remainder of \(8\)). From the same table, the number \(8\) corresponds to August.

    \(2.\) To find the month that is \(27\) months ago from April, we use modular arithmetic again. There are \(12\) months in a year:

    \(27 \;\text{mod} \;12=3.\) This means \(27\) months ago is \(3\) months before April.

    So, \(27\) months ago is \(3\) months before April.

    Starting from April and counting \(3\) months backward:

    \(1\) month before April → March

    \(2\) months before April is → February

    \(3\) months before April is → January

    There is another way to solve this problem. April is \(4.\) Now \(4-27 = -23.\)

    Since \(-a\) mod \(b\) is same as \(b-(a\;\text{mod}\; b)\)
    \(-23\;\text{mod}\;12= 12-(23 \;\text{mod} \;12) = 12-11=1\)

    From table in the Figure \(\PageIndex{5},\) the number \(1\) corresponds to January.

    Your Turn \(\PageIndex{5}\): Find the Future and Past Month

    Videos

    Content

     

    This page titled 1.6: Modular Arithmetic was last modified on Wed, 29 Apr 2026 18:53:21 GMT and is shared under a CC BY 4.0 license and was authored, remixed, and/or curated by Cheban Acharya via source content that was edited to the style and standards of the LibreTexts platform.